Проблема с делением длинных строк, а затем правильным моддингом в Python

Я пытаюсь реализовать тест на простоту для реализации RSA, которую я пишу в качестве упражнения. В основном я использую Рабина-Миллера, но у меня есть решето Эратосфена, формулирующее список всех простых чисел до тысячи, чтобы использовать его для быстрого теста, чтобы определить, имеет ли кандидат одно из них в качестве простого множителя.

Соответствующая функция:

def comp_test(to_test, primeList):
    for i in primeList:
        if (to_test / float(i)) % 1 == 0:
            return False
    return True

Где PrimeList — это список простых чисел, сгенерированный решетом. Это отлично работает до значений to_test 2^55 или около того, но после этого значения

(to_test / float(i)) % 1

оператор всегда оценивается как 0,0, даже когда я передаю ему to_test, который Рабин-Миллер определил как простой. Я не уверен, что это может быть. Я не совсем понимаю, как Python обрабатывает очень большие числа, но, насколько мне известно, 2 ^ 55 не похоже на границу переполнения. С Sieve функция работает значительно быстрее, а генерация ключей для 2048-битной реализации, которую я собираюсь использовать, занимает некоторое время, поэтому, хотя это упражнение, я хотел бы посмотреть, смогу ли я заставить Sieve работать.

Заранее спасибо.


python rsa sieve primality-test
person Dr. Dudley Eigenvalue D.D.S.    schedule 24.04.2013    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Python обрабатывает только 53 бита точности для чисел с плавающей запятой (около 16 знаков после запятой), поэтому использование таких больших чисел с плавающей запятой не будет работать очень хорошо.

Вместо этого используйте оператор по модулю:

>>> (2**80 / float(3)) % 1  # Doesn't work
    0.0
>>> 2**80 % 3  # Works
    1L
>>> 2**80 % 2  # Works
    0L

Это также немного быстрее, чем деление:

>>> %timeit (2**40 / float(2)) == 0
1000000 loops, best of 3: 224 ns per loop
>>> %timeit 2**40 % 2 == 0        
10000000 loops, best of 3: 53.5 ns per loop

Если i является фактором n, то n % i == 0 (n конгруэнтно 0 по модулю i).

person Blender    schedule 24.04.2013

arrow_upward
0
arrow_downward

Я бы рекомендовал использовать GMP для ваших нужд большого числа.

Вот некоторые из проектов, связанных с праймом, которые я делал на Python в прошлом:

http://stromberg.dnsalias.org/svn/primes-below
http://stromberg.dnsalias.org/svn/big-prime
http://stromberg.dnsalias.org/svn/huge-prime
http://stromberg.dnsalias.org/svn/sieve
person dstromberg    schedule 24.04.2013