13,350,483 members (70,253 online)
alternative version

#### Stats

34.8K views
11 bookmarked
Posted 2 Dec 2013

# Primality test algorithms - Prime test - The fastest way to check primialty of a number

, 12 Dec 2013
 Rate this:
Review primality test algorithms and test their preformance in order to find out which is the fastest.

## 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

#### Naive primality test

```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  ```

#### Fermat primality test

```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  ```

#### Miller Rabin primality test

```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):
# number of iteration
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)

# inc the number of iteration
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:

```# main loop
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/NaiveMiller-Rabin/Naive
105
10053
1005415
10054033243
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

NumberNaive/FermatNaive/Miller-Rabin
997 10 ( Naive is 2 time faster here )
40487
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.

## Share

 Student Software Engineering Intern Israel
No Biography provided

## You may also be interested in...

 First Prev Next
 Composite number performance test skewed Member 1109989722-Sep-14 0:30 Member 11099897 22-Sep-14 0:30
 My vote of 5 Tesfamichael G.21-Apr-14 7:36 Tesfamichael G. 21-Apr-14 7:36
 My vote of 1 Member 884486027-Dec-13 1:48 Member 8844860 27-Dec-13 1:48
 [My vote of 2] Some serious issues... Matt T Heffron4-Dec-13 9:41 Matt T Heffron 4-Dec-13 9:41
 Re: [My vote of 2] Some serious issues... Shay Margalit4-Dec-13 10:46 Shay Margalit 4-Dec-13 10:46
 Re: [My vote of 2] Some serious issues... Matt T Heffron4-Dec-13 11:10 Matt T Heffron 4-Dec-13 11:10
 Re: [My vote of 2] Some serious issues... Shay Margalit4-Dec-13 11:46 Shay Margalit 4-Dec-13 11:46
 Re: [My vote of 2] Some serious issues... Member 96925308-Dec-13 22:55 Member 9692530 8-Dec-13 22:55
 Re: [My vote of 2] Some serious issues... Shay Margalit11-Dec-13 23:48 Shay Margalit 11-Dec-13 23:48
 Re: [My vote of 2] Some serious issues... Member 969253012-Dec-13 0:33 Member 9692530 12-Dec-13 0:33
 Re: [My vote of 2] Some serious issues... Shay Margalit12-Dec-13 2:03 Shay Margalit 12-Dec-13 2:03
 Number 9 is showing as prime number tanmoysarkar2-Dec-13 23:27 tanmoysarkar 2-Dec-13 23:27
 Re: Number 9 is showing as prime number Shay Margalit3-Dec-13 3:08 Shay Margalit 3-Dec-13 3:08
 Last Visit: 31-Dec-99 19:00     Last Update: 19-Jan-18 8:16 Refresh 1