Introduction
In this article I will review some primality test algorithms, their implementation (in Python), and finally we will test their performance in order to determine which is the fastest. The first part of the article would present the algorithm implementations and the second part would present the performances tests.
We will see three well known primality tests:
- The naive algorithm
- Fermat primality test
- Miller Rabin primality test
Part one - Implementation
def simplePrimaryTest(number):
if number == 2:
return true
if number % 2 == 0:
return False
i = 3
sqrtOfNumber = math.sqrt(number)
while i <= sqrtOfNumber:
if number % i == 0:
return False
i = i+2
return True
def FermatPrimalityTest(number):
''' if number != 1 '''
if (number > 1):
''' repeat the test few times '''
for time in range(3):
''' Draw a RANDOM number in range of number ( Z_number ) '''
randomNumber = random.randint(2, number)-1
''' Test if a^(n-1) = 1 mod n '''
if ( pow(randomNumber, number-1, number) != 1 ):
return False
return True
else:
''' case number == 1 '''
return False
def MillerRabinPrimalityTest(number):
'''
because the algorithm input is ODD number than if we get
even and it is the number 2 we return TRUE ( spcial case )
if we get the number 1 we return false and any other even
number we will return false.
'''
if number == 2:
return True
elif number == 1 or number % 2 == 0:
return False
''' first we want to express n as : 2^s * r ( were r is odd ) '''
''' the odd part of the number '''
oddPartOfNumber = number - 1
''' The number of time that the number is divided by two '''
timesTwoDividNumber = 0
''' while r is even divid by 2 to find the odd part '''
while oddPartOfNumber % 2 == 0:
oddPartOfNumber = oddPartOfNumber / 2
timesTwoDividNumber = timesTwoDividNumber + 1
'''
since there are number that are cases of "strong liar" we
need to check more then one number
'''
for time in range(3):
''' choose "Good" random number '''
while True:
''' Draw a RANDOM number in range of number ( Z_number ) '''
randomNumber = random.randint(2, number)-1
if randomNumber != 0 and randomNumber != 1:
break
''' randomNumberWithPower = randomNumber^oddPartOfNumber mod number '''
randomNumberWithPower = pow(randomNumber, oddPartOfNumber, number)
''' if random number is not 1 and not -1 ( in mod n ) '''
if (randomNumberWithPower != 1) and (randomNumberWithPower != number - 1):
iterationNumber = 1
''' while we can squre the number and the squered number is not -1 mod number'''
while (iterationNumber <= timesTwoDividNumber - 1) and (randomNumberWithPower != number - 1):
''' squre the number '''
randomNumberWithPower = pow(randomNumberWithPower, 2, number)
iterationNumber = iterationNumber + 1
'''
if x != -1 mod number then it because we did not found strong witnesses
hence 1 have more then two roots in mod n ==>
n is composite ==> return false for primality
'''
if (randomNumberWithPower != (number - 1)):
return False
''' well the number pass the tests ==> it is probably prime ==> return true for primality '''
return True
Part two - Performance tests
After we have understood the theory and the implementation, it's time to determine which
is the fastest.
We'll divide the test into two:
- Performance for composite numbers
- Performance for prime numbers
In order to measure the performance, I'll use the "timeit" module and the following code:
while True:
''' get number to test '''
print "Enter the number you want to test:"
number = int(raw_input())
''' break the loop if recived 0 '''
if number == 0:
break
''' test for primility '''
if PrimalityTest.MillerRabinPrimalityTest(number) and PrimalityTest.FermatPrimalityTest(number):
print number, "is prime"
else:
print number, "is not prime"
''' time the algorithms. we repeat the test 100 times in order to get some
significant time. '''
naive = timeit.timeit('import PrimalityTest;PrimalityTest.simplePrimaryTest('+str(number)+');',number=1000)
Fermat = timeit.timeit('import PrimalityTest;PrimalityTest.FermatPrimalityTest('+str(number)+');',number=1000)
MillerRbin = timeit.timeit('import PrimalityTest;PrimalityTest.MillerRabinPrimalityTest('+str(number)+');',number=1000)
''' print result '''
print number, naive, Fermat,MillerRbin
Composite numbers test
Number | Fermat/Naive | Miller-Rabin/Naive |
---|
105 | 3 | 3 |
10053 | 1 | 2 |
1005415 | 2 | 1 |
10054033243 | 2 | 2 |
10054033321154111121 | 13 | 13 |
As you can see, when we try to test composite numbers primality, Miller-Rabin
and Fermat perform almost the same, but the
Naive test is faster than both of them. I was a bit surprised to see this result, but
I think that the next test would show a different perspective.
Prime numbers test
Number | Naive/Fermat | Naive/Miller-Rabin |
---|
997 | 1 | 0 ( Naive is 2 time faster here ) |
40487 | 2 | 2 |
53471161 | 61 | 47 |
1645333507 | 322 | 287 |
188748146801 | 960 | 661 |
99194853094755497 | 313148 | 385993 |
So, when we are testing prime numbers for primality, Miller-Rabin and Fermat are much,
much faster than Naive.
As you can see, the performance difference is getting bigger and bigger with the size of the number.
The last number is not
very big and still it took my computer a few minutes to test it with the naive primality test - that's what made me understand that if
I want to test the primility
of a big number fast, I would stick to the more sophisticated methods.