I have an implementation of the Miller-Rabin-Primetest, coded in python3.
Unfortunately I have no idea how "fast" this test should be on my machine.
With my code I can test the number $n = 2^{10^4}+1$ in less than 4 seconds.
But I don't know whether this is a good time.
Can I get a kind of a benchmark?
Here is my code:
Код: Выделить всё
def rab_test(N, rounds = 40):
if N in [2, 3]:
return True
if N % 2 == 0:
return False
n = N // 2
t = 1
while n % 2 == 0:
n = n // 2
t += 1
a = random.randrange(2, N-1)
u = gmpy2.powmod(a, n, N)
if u == 1 or N-u == 1:
return True
for k in range(1, t):
u = gmpy2.powmod(u, 2, N)
if N-u == 1:
return True
return False
Источник: https://stackoverflow.com/questions/781 ... -primetest
