1

Dixon の因数分解法を Python で実装しようとしてきましたが、少し混乱しています。B境界と数を指定し、との間の平方数Nを検索する必要があることはわかっています。つまり、すべての因数が より小さいか等しい素数の集合に含まれていることを意味します。私の質問は、特定のサイズが与えられた場合、アルゴリズムが重要な要因を生成するように決定するものは何ですか? これはアルゴリズムに関するウィキペディアの記事です。それが役立つ場合は、実装のコードを次に示します。sqrtNNB-smoothBNBN

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

0

[別の目的でこれを書きましたが、面白いと思うかもしれません。]

x 2 ≡ y 2 (mod n ) でx ≠ ± yの場合、gcd( x − y , n ) の約半分の時間はnの係数です。1920 年代に Maurice Kraitchik によって観察されたこの平方の合同は、いくつかの因数分解法の基礎となっています。これらの方法の 1 つは John Dixon によるもので、実際には遅すぎて役に立たないものの、準指数関数的な実行時間を証明できるため、理論的には重要です。

ディクソンの方法は、範囲b ≈ e √(log n log log n )を選択し、 nの二次留数であるbより小さいすべての素数の因子基数を特定することから始まります(それらのヤコビ記号は 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は、そのすべての因数が試行分割によって決定される因数ベースにある場合、滑らかです。この関数は因子のリストを返します。これは、 nが因子ベースを完全に因子分解していないsmooth場合は 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となります。これらの 2 つの関係は (17 · 19) 2 ≡ 3 2 · 5 2 ≡ 15 2 (mod 143)として組み合わせることができ、2 つの要素は gcd(17·19 − 15, 143) = 11 および gcd(17·19) です。 + 15, 143) = 13. これは時々失敗します。たとえば、関係 21 2 ≡ 2 2 (mod 143) は 19 の関係と組み合わせることができますが、生成される 2 つの因数 1 と 143 は自明です。

于 2015-03-31T14:46:37.317 に答える