Более быстрый побитовый модуль для теста первичности Лукаса-Лемера - PullRequest
Новая
       22

Более быстрый побитовый модуль для теста первичности Лукаса-Лемера

4 голосов
/ 22 марта 2011

Тест простоты *1001* Лукаса * Лемера проверяет простые числа, чтобы определить, являются ли они также простыми числами Мерсенна .Одним из узких мест является операция модуля при расчете (s**2 − 2) % (2**p - 1).

Использование побитовых операций может значительно ускорить процесс (см. Ссылку LL), лучшее, что у меня пока есть: 

def mod(n,p):
    """ Returns the value of (s**2 - 2) % (2**p -1)"""
    Mp = (1<<p) - 1
    while n.bit_length() > p: # For Python < 2.7 use len(bin(n)) - 2 > p
        n = (n & Mp) + (n >> p)
    if n == Mp:
        return 0
    else:
        return n

В простом тестовом примере p имеет 5-9 цифр, а s имеет 10 000+ цифр (или больше; не важно, что они есть).Решения могут быть проверены mod((s**2 - 2), p) == (s**2 - 2) % (2**p -1).Имейте в виду, что в тесте LL требуются p - 2 итерации этой операции модуля, каждая с экспоненциально возрастающим s, следовательно, требуется оптимизация.

Есть ли способ ускорить это, используячистый Python (включая Python 3)?Есть ли лучший способ?

Ответы [ 2 ]

1 голос
/ 23 марта 2011

Лучшее улучшение, которое я смог найти, - это полное удаление Mp = (1<<p) - 1 из функции модуля и предварительное вычисление его в функции L-L перед началом итераций теста L-L. Использование while n > Mp: вместо while n.bit_length() > p: также сэкономило время.

0 голосов
/ 22 марта 2011

В случае, когда n намного длиннее 2 ^ p, вы можете избежать некоторой боли в квадратичном времени, выполнив что-то вроде этого: 

def mod1(n,p):
    while n.bit_length() > 3*p:
        k = n.bit_length() // p
        k1 = k>>1
        k1p = k1*p
        M = (1<<k1p)-1
        n = (n & M) + (n >> k1p)
    Mp = (1<<p)-1
    while n.bit_length() > p:
        n = (n&Mp) + (n>>p)
    if n==Mp: return 0
    return n

[отредактировано, потому что я испортил форматирование раньше; спасибо Бенджамину за указание на это. Мораль: не копируйте и не вставляйте из неактивного окна в SO. Извините!]

(Примечание: критерий уменьшения длины n вдвое, а не снятия p, и точный выбор k1 оба немного ошибочны, но это не имеет значения, поэтому я не стал их исправлять.)

Если я беру p = 12345 и n = 9 ** 200000 (да, я знаю, что p тогда не простое число, но здесь это не имеет значения), то это примерно в 13 раз быстрее.

К сожалению, это не поможет вам , потому что в тесте L-L n никогда не больше, чем примерно (2 ^ p) ^ 2. К сожалению.

...