1

我一直在尝试在python中实现Dixon的分解方法，我有点困惑。我知道你需要给出一些界限B和一些数字N，并搜索它们之间的数字sqrtN，N其平方是B-smooth，这意味着它们的所有因子都在小于或等于 的素数集中B。我的问题是，给定N一定的大小，是什么决定B了算法会产生 的重要因素N？这是有关该算法的维基百科文章，如果有帮助，这是我的实现代码：

def factor(N, B):
    def isBsmooth(n, b):
        factors = []
        for i in b:
            while n % i == 0:
                n = int(n / i)
                if not i in factors:
                    factors.append(i)
        if n == 1 and factors == b:
            return True
        return False

    factor1 = 1
    while factor1 == 1 or factor1 == N:
        Bsmooth = []
        BsmoothMod = []
        for i in range(int(N ** 0.5), N):
            if len(Bsmooth) < 2 and isBsmooth(i ** 2 % N, B):
                Bsmooth.append(i)
                BsmoothMod.append(i ** 2 % N)
        gcd1 = (Bsmooth[0] * Bsmooth[1]) % N
        gcd2 = int((BsmoothMod[0] * BsmoothMod[1]) ** 0.5)
        factor1 = gcd(gcd1 - gcd2, N)
        factor2 = int(N / factor1)
    return (factor1, factor2)

也许有人也可以帮我清理一下我的代码？这似乎非常低效。

4

2 回答 2

1

本文讨论了 B 的最佳尺寸：https ://web.archive.org/web/20160205002504/https://vmonaco.com/dixons-algorithm-and-the-quadratic-sieve/ 。简而言之，最佳值被认为是 exp((logN loglogN)^(1/2))。

于 2015-03-31T12:16:04.083 回答
0

[我写这个是为了不同的目的，但你可能会觉得它很有趣。]

给定x 2 ≡ y 2 (mod n ) 且x ≠ ± y，大约一半的时间 gcd( x − y , n ) 是 n 的因数。由 Maurice Kraitchik在 1920 年代观察到的平方的一致是几种分解方法的基础。其中一种方法，由于 John Dixon，在理论上很重要，因为它的次指数运行时间可以被证明，尽管它在实践中太慢而无法使用。

Dixon 的方法首先选择一个边界b ≈ e √(log n log log n )并确定所有小于b的素数的因子基，这些素数是n的二次余数（它们的雅可比符号为 1）。

function factorBase(n, b)
  fb := [2]
  for p in tail(primes(b))
    if jacobi(n, p) == 1
      append p to fb
  return fb

然后在 1 < r < n范围内重复选择一个整数r，计算它的平方模n，如果平方在因子基上是平滑的，则将其添加到关系列表中，当关系多于因子中的因子时停止基数，再加上为那些失败的案例准备的小额储备金。这个想法是使用线性代数来识别一组关系，其中因子基素数组合形成一个正方形。然后取关系中所有因子基素数的乘积的平方根，取相关r的乘积，并计算 gcd 以识别因子。

struct rel(x, ys)

function dixon(n, fb, count)
  r, rels := floor(sqrt(n)), []
  while count > 0
    fs := smooth((r * r) % n, fb)
    if fs is not null
      append rel(r, fs) to rels
      count := count - 1
    r := r + 1
  return rels

一个数n是光滑的，如果它的所有因子都在因子基中，这是由试除法确定的；该smooth函数返回一个因子列表，如果n没有完全覆盖因子基数，则该列表为 null。

function smooth(n, fb)
  fs := []
  for f in fb
    while n % f == 0
      append f to fs
      n := n / f
    if n == 1 return fs
  return []

通过将累积的关系提交给平方同余求解器的线性代数来确定一个因子。

例如，考虑 143 的因式分解。选择r = 17，因此r 2 ≡ 3 (mod 143)。然后选择r = 19，因此r 2 ≡ 75 ≡ 3 · 5 2。这两个关系可以组合为 (17 · 19) 2 ≡ 3 2 · 5 2 ≡ 15 2 (mod 143)，这两个因素是 gcd(17·19 - 15, 143) = 11 和 gcd(17·19 + 15, 143) = 13。这有时会失败；例如，关系 21 2 ≡ 2 2 (mod 143) 可以与关系 19 组合，但产生的两个因子 1 和 143 是微不足道的。

于 2015-03-31T14:46:37.317 回答