В чем проблема моего основного тестового кода? - PullRequest
Новая
       16

В чем проблема моего основного тестового кода?

2 голосов
/ 26 июня 2011

Я реализовал алгоритм простого теста Миллера-Рабина , найденный в википедии с Python 3.

Кажется, он работает правильно с большинством номеров, но иногда не работает на некоторых номерах.

Например, простое число 99999999999999997 считается НЕ простым.

Я реализовал алгоритм построчно, и я понятия не имею, где проблема. Кто-нибудь может мне помочь?

Вот мой код.

тестовый ввод:

1

99999999999999997

(между двумя строками нет пустой строки).

И ожидаемый результат должен быть ДА, но он дает НЕТ на моей машине. 

import random

def isPrime(n, k = 5):
'''
Primality test using Miller-Rabin method.
n The number to test primality.
k The number of M-R test to perform.
'''
if n == 1:
    return False
if n == 2 or n == 3:
    return True
if n % 2 == 0:
    return False

# Calculate d
nn = n - 1
s = 1
while nn % (2 ** s) == 0:
    s += 1
s -= 1
d = int(nn / (2 ** s))

for i in range(k):
    a = random.randint(2, n - 1)
    x = pow(a,d,n)
    if x == 1 or x == n - 1:
        continue
    flag = True
    for r in range(1, s):
        x = pow(x,2,n)
        if x == 1:
            return False
        if x == n - 1:
            flag = False
            break
    if not flag:
        continue
    return False
return True

count = int(input())
for i in range(count):
    if isPrime(int(input())):
        print('YES')
    else:
        print('NO')

Ответы [ 3 ]

4 голосов
/ 26 июня 2011

Это реализация Миллера-Рабина, которую я написал некоторое время назад.Это никогда не давало мне неожиданного результата - хотя это не значит, что не будет!Он практически идентичен тому, который вы вставили, и объявляет 99999999999999997 простым.Ваш сделал то же самое, когда я проверял это - так что это секунда к мнению Миколы . Но посмотрите ниже на одну возможную проблему, которую я не могу легко проверить ... поцарапайте ее, я проверил ее, и это была проблема .

Когда дело доходит до тестирования простоты, яЯ не эксперт, но я потратил много времени на размышления и понимание Миллера-Рабина, и я уверен, что ваша реализация точная.

def is_prime_candidate(self, p, iterations=7):  
    if p == 1 or p % 2 == 0: return False       
    elif p < 1: raise ValueError("is_prime_candidate: n must be a positive integer")
    elif p < self.maxsmallprime: return p in self.smallprimes

    odd = p - 1
    count = 0
    while odd % 2 == 0:
        odd //= 2
        count += 1

    for i in range(iterations):
        r = random.randrange(2, p - 2) 
        test = pow(r, odd, p)
        if test == 1 or test == p - 1: continue
        for j in range(count - 1):
            test = pow(test, 2, p)
            if test == 1: return False
            if test == p - 1: break
        else: return False
        print i
    return True

Единственное, что я заметил в вашем коде, который показался мне необычным, это: 

d = int(nn / (2 ** s))

Почему int, подумал я про себя.Тогда я понял, что вы должны использовать Python 3. Это означает, что вы выполняете арифметику с плавающей запятой и затем конвертируете в int.Это казалось сомнительным.Поэтому я проверил его на ideone. И вот! результат был False.Поэтому я изменил код, чтобы использовать явное разделение по полу (d = nn // (2 ** s)). И вот! это было True.

2 голосов
/ 26 июня 2011

Я собираюсь повторить свой комментарий, так как мое тестирование показывает, что ваш пример работает. Я сильно подозреваю, что вы просто опечатали свой контрольный пример. Может быть, вы можете попробовать еще раз взглянуть на это? Вот что я получил от этого:

В [12]: millerrabin.isPrime (99999999999999997, 5)

Out [12]: True

РЕДАКТИРОВАТЬ: я только что запустил обновленную версию, и вот вывод из консоли: 

1
99999999999999997
YES

Опять же, это выглядит правильно.

0 голосов
/ 26 июня 2011

Из того, что я вижу, алгоритм Миллера-Рабина только вероятностный. Вы не знали об этом или используете измененную, не вероятностную версию?

...