0,0 → 1,42 |
""" fmath.prime |
|
Start of prime number routines. Rabin-miller test works, more to come later. |
|
Copyright © (c) 2002 by Paul A. Lambert |
Read LICENSE.txt for license information. |
""" |
|
def fermat_little_test( p, a ): |
""" Fermat Little Test. Included as a curiosity, not useful for cryptographic use. |
p -> possiblePrime, a -> any integer |
""" |
if pow(a,p-1,p) == 1 : |
return 1 # could be prime |
else: |
return 0 # is NOT prime |
|
def rabin_miller(possiblePrime, aTestInteger): |
""" The Rabin-Miller algorithm to test possible primes |
taken from HAC algorithm 4.24, without the 't' |
""" |
assert( 1<= aTestInteger <= (possiblePrime-1) ), 'test integer %d out of range for %d'%(aTestInteger,possiblePrime) |
#assert( possiblePrime%2 == 1 ), 'possiblePrime must be odd' |
# calculate s and r such that (possiblePrime-1) = (2**s)*r with r odd |
r = possiblePrime-1 |
s=0 |
while (r%2)==0 : |
s+=1 |
r=r/2 |
y = pow(aTestInteger,r,possiblePrime) |
if ( y!=1 and y!=(possiblePrime-1) ) : |
j = 1 |
while ( j <= s-1 and y!=possiblePrime-1 ): |
y = pow(y,2,possiblePrime) # (y*y) % n |
if y==1 : |
return 0 # failed - composite |
j = j+1 |
if y != (possiblePrime-1): |
return 0 # failed - composite |
return 1 # success - still a possible prime |
|
|