Второй этап алгоритма Полларда p-1 - PullRequest
Новая
       30

Второй этап алгоритма Полларда p-1

1 голос

Я реализую алгоритм Полларда p-1 в Python, как описано в статье Полларда Теоремы о факторизации и проверке на простоту . До сих пор я реализовал первый этап алгоритма следующим образом: 

def factorizePminus1(n, B1, c):
    g = 1
    if(gcd(c,n) != 1):
        return gcd(c,n)
    primesUpToB1 = primes(B1)
    for p in primesUpToB1:
        pp = p
        while pp < B1:
            c = pow(c, p, n)
            pp = pp * p
    g = gcd(c-1, n)
    if(1<g<n):
        return g
    elif(g==n):
        return "Your factors are probably less than " + str(B1)

Я реализовал gcd, используя алгоритм Евклида, и сгенерировал список всех простых чисел меньше B1, используя простые числа ( B1), который использует сито метода Эратосфена. Я выбираю экспоненту P = lcm(1,2,...,B1).

Однако Поллард описывает в своей статье второй этап алгоритма, в котором выбирается вторая граница B2 и вычисляется последовательность чисел F_m = b^m-1 (mod n) для b=a^{lcm(1,2,...,B1)} для простых чисел B1< m < B2 и надеется найти м такой, что gcd(F_m,N)>1.

Предлагаемый в статье способ сделать это - умножить b ^ m на все нечетные целые числа m между B1 и B2, что я сделал так: 

def factorizePminus1(n, B1, B2,c):
   g = 1
   if(gcd(c,n) != 1):
       return gcd(c,n)
   primesUpToB1 = primes(B1)
   for p in primesUpToB1:
       pp = p
       while pp < B1:
           c = pow(c, p, n)
           pp = pp * p
   g = gcd(c-1, n)
   if(1<g<n):
       return g
   elif(g==n):
       return "Your factors are probably less than " + str(B1)

   k = 0
   for q in range(primesUpToB1[-1],B2,2):
       c = pow(c,q,n)
   g = gcd(c-1,n)

   if(1<g<n):
       return g
   else:
       return "no luck"

Есть другой способ в статье предлагается вычислить заранее таблицу остатков b ^ 2, b ^ 4, b ^ (2D) до наибольшей возникающей разности двух последовательных простых чисел p_ {k + 1} -p_k = 2D, но это требует создания списка простых чисел между B1 и B2, что означает, что я должен использовать простые числа (B2), что замедляет мою программу. Мне было интересно, есть ли способ вычислить простые числа между B1 и B2, учитывая, что у меня уже есть все простые числа меньше, чем B1, и насколько это эффективнее, если просто вычислить все нечетные целые числа между B1 и B2?

...