Python Pollard P-1 факторизация

Я пытаюсь реализовать факторизацию Полларда P-1 в Python. Обратите внимание, что метод Rho имеет несколько ответов, но этот p-1 отличается, и лучшее, что я могу вам здесь рассказать о p-1, это вики и Wolfram:

http://en.wikipedia.org/wiki/Pollard's_p_% E2% 88% 92_1_algorithm

http://mathworld.wolfram.com/Pollardp-1FactorizationMethod.html

Это факторизация чего-то из n, но последовательно не находит p. Np и sp от numpy и scipy соответственно. Таким образом, встроенные функции для sp.uint64 имеют длину 64 int без знака (из-за размера ожидаемых целых чисел), а np.prod(p) представляет собой совокупное произведение pi в списке p:

def pm1_attack(n,b):
  p = [2,3,5,7,11,13,17]; i=19; a=2
  while i<b:
    if is_prime(i,10): p.append(i)
    i+=2;
  k = sp.uint64(np.prod(p)); q = power2(a,k,n)
  g = euc_al_i((q-1),n)
  print "product pi: ",k
  print "q: ",q
  print "g: ",g
  #return a

print "pollard_pm1_attack(n,b): ",pollard_pm1_attack(n,2000)

Выход не находит p:

Python 2.7 (r27:82525, Jul  4 2010, 09:01:59) [MSC v.1500 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>> 
p = 1300199 
q = 2063507 

euler_totient = 2682966374188 

common n = 2682969737893 


public key e = 1588051820871 

secret key d = 2410616084843 

cleartext message = test 

encoded message = 1489995542681 

decoded message = test 

check_rsa = Successful encryption and decrytion. Message is authenticated. 

pollard_pm1_attack(n,b):  product pi:  18446744073460481730
q:  2391570546599
g:  1
None
>>>

Я изучаю Python, так что это может быть какая-то простая ошибка. Функция power2() использует возведение в квадрат при возведении в квадрат и, по сути, является сверхзаряженным pow() для очень больших целых чисел. Euc_al_i() - это просто gcd. Вы можете использовать любой gcd ​​(), какой захотите, но так как я учусь, я хотел сделать это сам.

Я пытаюсь выяснить, что здесь произошло так ужасно неправильно, что он не находит p даже из относительно небольшого n (всего 20 бит).

Источник

2 ответа

Решение

Я не знаю, что делают np.prod и sp.uint64, но я могу рассказать вам об алгоритме p - 1, который был изобретен Джоном Поллардом в 1974 году.

Алгоритм Полларда основан на Маленькой теореме Ферма a ^ p == a (mod p), которая, когда a! = 0, может быть задана как a ^ (p - 1) == 1 (mod p) путем деления a через выражение. Как следствие, если p - 1 делит m, то p делит gcd (2 ^ m - 1, n). Алгоритм Полларда p - 1 вычисляет m как наименьшее общее кратное целых чисел, меньших границы b, так что, если все факторы p - 1 меньше, чем b, то gcd (2 ^ lcm (1.. b) - 1, п) является фактором п. Наименьшее общее кратное вычисляется умножением простых чисел, меньших b, на их кратности, меньшие b:

function pminus1(n, b)
    c := 2
    for p in primes(b)
        pp := p
        while pp < b
            c := powerMod(c, p, n)
            pp := pp * p
    g := gcd(c-1, n)
    if 1 < g < n return g
    error "factorization failed"

Необязательный второй этап ищет "большое простое число" между b1 и b2, которое объединяется с наименьшим общим кратным первого этапа, чтобы найти фактор. Второй этап требует только модульного умножения для каждого простого числа, а не модульного возведения в степень, что делает его довольно быстрым, и gcds второго этапа можно вычислять партиями. Кеш небольшой, но важный для эффективности функции.

function pminus1(n, b1, b2)
    c := 2
    for p in primes(b1)
        pp := p
        while pp < b
            c := powerMod(c, p, n)
            pp := pp * p
    g := gcd(c-1, n)
    if 1 < g < n return g
    k := 0
    for q in primes(b1, b2)
        d := q - p
        if d is not in cache
            x := powerMod(c, d, n)
            store d, x in cache
        c := (c * x(d)) % n
        p := q
        k := k + 1
        if k % 100 == 0
            g := gcd(c-1, n)
            if 1 < g < n return g
    g := gcd(c-1, n)
    if 1 < g < n return g
    error "factorization failed"

Возможно, что метод Полларда p - 1 может не найти фактор n; это зависит от факторизации n - 1 и выбранных вами границ. Способ проверки состоит в том, чтобы самостоятельно вычислить множитель n - 1, а затем вызвать метод Полларда с b, который больше, чем наибольший множитель n - 1. Например, если вы хотите множить n = 87463 = 149 * 587, обратите внимание, что n - 1 = 87462 = 2 * 3 * 3 * 43 * 113, поэтому вызовите одноэтапный алгоритм с b = 120 или двухэтапный алгоритм с b1 = 50 и b2 = 120 и посмотрите, найдете ли вы коэффициент.

Я обсуждаю алгоритм факторизации Полларда p - 1, а также несколько других алгоритмов факторизации в моем блоге. Я также даю здесь реализации функций powerMod и gcd, на случай, если у вас возникнут проблемы с вашими реализациями этих функций. И я написал простую реализацию одностадийного алгоритма на Python по http://ideone.com/wdyjxK.

Источник

Вот двухэтапная версия, реализованная на python.

from math import gcd, log

def pminus1(n, B1, B2):
    log_B1 = log(B1)
    M = 1
    primes = prime_sieve()
    for p in primes:
        if p > B1:
            break
        M *= p**int(log_B1/log(p))
    M = pow(2, M, n)
    g = gcd(M-1, n)
    if 1 < g < n:
        return True
    if g == n:
        return False

    # Start part 2.
    cache = {0:M}
    S = (M*M) % n
    for d in range(2, int(log(B2)**2), 2):
        cache[d] = cache[d-2] * S) % n

    HQ = M
    for k, q in enumerate(primes):
        if q > B2:
            break
        d = q - p
        HQ = (HQ * cache[d]) % n
        M = (M * (HQ-1)) % n
        p = q
        if k % 200 == 0:
            if 1 < gcd(M, n) < n:
                return True
    return 1 < gcd(M, n) < n
Источник
Другие вопросы по тегам