论文标题
通过求解Pell方程来查找双光滑整数
Finding twin smooth integers by solving Pell equations
论文作者
论文摘要
对于给定平滑度绑定B的任何一对连续的B平滑整数都对应于对于某个无正方形的，B-Smooth Integer D和B-Smooth Integer y的方程x^2-2dy^2 = 1的溶液（x，y）。本文介绍了通过使用上述pell方程的结构来找到在给定间隔中的二B-光滑整数的算法。寻找这种双流平滑整数的问题是由于寻求合适的参数有效实例化了最新的基于ISEGEN的密码系统的动机。尽管Twin B-Smooth Integers的Pell方程结构以前已用于描述和计算非常小的B值的完整对成对，但增加B以允许使用密码尺寸的解决方案，使得这种方法完全不可行。我们首先重新访问双光滑整数集的Pell解决方案结构。我们专注于仅识别那些位于给定间隔的人。这种限制使我们能够描述以更具针对性的方式导航大量Pell解决方案的算法。使用这些算法运行的实验提供了比以前报道的对比对的双B-平滑对对且具有较小的平滑度B的示例。不幸的是，这些示例尚未为密码学提供更好的参数，但我们希望我们的方法可以在未来工作中被概括或用作子例程，以实现这一目标。
Any pair of consecutive B-smooth integers for a given smoothness bound B corresponds to a solution (x, y) of the equation x^2 - 2Dy^2 = 1 for a certain square-free, B-smooth integer D and a B-smooth integer y. This paper describes algorithms to find such twin B-smooth integers that lie in a given interval by using the structure of solutions of the above Pell equation. The problem of finding such twin smooth integers is motivated by the quest for suitable parameters to efficiently instantiate recent isogeny-based cryptosystems. While the Pell equation structure of twin B-smooth integers has previously been used to describe and compute the full set of such pairs for very small values of B, increasing B to allow for cryptographically sized solutions makes this approach utterly infeasible. We start by revisiting the Pell solution structure of the set of twin smooth integers. Instead of using it to enumerate all twin smooth pairs, we focus on identifying only those that lie in a given interval. This restriction allows us to describe algorithms that navigate the vast set of Pell solutions in a more targeted way. Experiments run with these algorithms have provided examples of twin B-smooth pairs that are larger and have smaller smoothness bound B than previously reported pairs. Unfortunately, those examples do not yet provide better parameters for cryptography, but we hope that our methods can be generalized or used as subroutines in future work to achieve that goal.
