Lucas and Perrin Probablistic Prime Tests

Click the arrow to go up a level to the Math Index.

Follow the above link or click the graphic below to visit the Homepage.

Lucas & Perrin
Probablisitic Prime Tests
Jim Cullen

Texas Instruments produces several excellent graphing scientific calculators, among them are the TI-83, TI-84, TI-89 Titanium ( which succeeds the TI-89 ), the TI-92 ( pretty much obsolete now ), the TI-92+, and the TI Voyage 200 PLT. These high-end devices have a function for determining the primality of integers; on the TI-89 and up the function is implemented as ISPRIME( n ) where n is any integer. The calculator returns a boolean value; true if the integer n is prime, and false if the integer n is composite ( has factors besides itself and one ). The internal routine involves trial division up to very large integers and an unknown 'Monte Carlo' technique ( if this is actually a separate part of the test besides trial division ). The ISPRIME() function is not perfect however, and there are integers that are declared 'prime' when in fact they are composite. This is not a 'bug' in the operating system but a demonstration of the nature of probablistic primality testing. All true primes are declared prime but some composites are also declared prime so the mathematical filter is not perfect. No primality testing algorithm is 100% foolproof - yet.

Though the probability of a composite integer being declared prime by the ISPRIME() function is extremely low, examples of such integers are known. The function ISPRIME() by itself is not foolproof but performing multiple tests on an integer makes the determination of primality much more powerful. There are several possible quick routines one can implement in TI-Basic to double-check the calculator's determination of the primality of an integer. Here we will discuss two of them involving recurrent sequences; the Lucas and Perrin Probablistic Prime Tests. Coding for the calculator is provided and should work on the TI-89/92/V200 family of devices.

Lucas Probablistic Prime Test
The Lucas Probablistic Prime Test is based on the fact that the z'th term of the Lucas Sequence is congruent to 1 mod z, if z is prime. The Lucas Sequence is one of the Generalized Fibonacci sequences in which G( 0 ) = a = 2, G( 1 ) = b = 1, and the sequence is defined by taking G( z ) = G( z - 1 ) + G( z - 2 ). In other words, any Lucas Number is simply the sum of the previous two Lucas Numbers, with the intitial values set to 2 and 1. The Lucas sequence begins; 2, 1, 3, 4, 7, 11, 18, 29, ... For more information on the Lucas and other recurrent sequences, see the introduction on the Special Sums of Generalized Fibonacci Sequences page.

The straight-forward Q-Matrix method for calculating the values of a Generalized Fibonacci Sequence G(a,b,z) is:

G( a, b, z ) = [ [ 1 1 ] [ 1 0 ] ]^z * [ [ b ] [ a ] ] = [ [ G( a, b, z + 1 ) ] [ G( a, b, z ) ] ]

We will use the Q-Matrix instead of simple recursion or a variation of Binet's Formula because the matrix method is faster and will return exact integer results for large values of z. Below is the function code for the TI-89/92/V200 family of calculators. The bit of code that looks like \->\ is the right arrow key for the storing of a value to a variable.

Lucas Probablistic Prime Test
Function Code for TI-89/92/V200 Series Calculators

:lucp(z)
:Func : Local a,b,t
:[[1,1][1,0]] \->\ a : z \->\ b : [[1,0][0,1]] \->\ t
:Loop
:If mod(b,2)=1 : mod(t*a,z) \->\ t
:int(b/2) \->\ b
:If b=0 : Exit
:mod(a^2,z) \->\ a
:EndLoop
:if mod(2*t[2,2]+t[1,2],z)=1 : return true
:return false
:EndFunc

Since the results are taken mod z, we can speed up the calculation by using modular exponentiation on the matrix and checking that the result is congruent to 1 mod z. The modular exponentiation is built into the function so no separate routine needs to be called in its place. If the result of the modular exponentiation is congruent to 1 mod z then the function returns 'true', meaning that either z is prime or is a pseudoprime for this test. If the result is NOT congruent to 1 mod z, then z is definitely NOT prime. This is the key for understanding what a probablistic prime test is; if the number fails the test then it is guaranteed to NOT be a prime number... if the number passes the test then it is probably a prime number OR that number may be one of the pseudoprimes for that test. A pseudoprime is a composite number that fools the test; the test passes the pseudoprime off as prime while actually the number has two or more factors.

The format for using the Lucas Prime Test on the calculator is lucp( z ) with z being a positive integer. Here are some examples:

lucp( 13 ) returns 'true'

lucp( 319 ) returns 'false' since ( 319 = 11 * 29 )

lucp( 651693055693681 ) returns 'false' in 5.37 sec

lucp( 705 ) returns 'true' though 705 is obviously NOT a prime number since ( 705 = 3 * 5 * 47 )

lucp( 2465 ) returns 'true' though again 2465 is NOT a prime number since ( 2465 = 5 * 17 * 29 ). These last two examples should be enough to demonstrate the fact that there are numbers that fool this test.

The number 651693055693681 is a Carmichael Number, a composite integer that passes the simple Fermat Test to any base besides one of its prime factors: 72931, 87517, or 102103. ( The Fermat Test is another probablistic prime test that checks whether b ^ ( n - 1 ) mod n is equal to 1. If it is then n is probably prime. ) Numbers such as these may fool the Fermat test but won't fool both the Lucas and Fermat test.

One last note. Don't confuse this simple Lucas probable prime test with the more comprehensive Lucas-Lehmer test that is based on the same principles.

Perrin Probablistic Prime Test
The Perrin Prime test is based on a property of another recurrent sequence. The terms of the Perrin Sequence have the special property such that P( z ) is congruent to 0 mod z, if z is a prime number (or is a pseudoprime as in the Lucas Test). For a given integer z the function returns 'true' if z is determined to be prime and returns 'false' if z is composite.

The Perrin Sequence is similiar to the Fibonacci and Lucas Sequences. In the case of the Perrin Sequence, we set P( 0 ) = 3, P( 1 ) = 0, P( 2 ) = 2 and then define the sequence as P( z ) = P( z - 2 ) + P( z - 3 ). The Perrin Sequence begins 3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, ... and can also be expressed in matrix form:

P( z ) = [ [ 0 1 1 ] [ 1 0 0 ] [ 0 1 0 ] ]^{( z - 2 )} * [ [ P( 2 ) ] [ P( 1 ) ] [ P( 0 ) ] ] = [ [ P( z + 2 ) ] [ P( z + 1 ) ] [ P( z ) ] ]

Again, since we are also taking terms of the sequence mod z, we can use modular exponentiation to speed up the calculation. This is built into the function code itself so no external powermod function file is required.

Just as in the Lucas test, if the function returns 'false' then the argument is definitely NOT prime. If the function returns 'true' then z is PROBABLY prime. Actually, z is extremely likely to be a prime number since the Perrin pseudoprimes are so extremely rare.

Perrin Pseudoprimes are composite numbers that pass the Perrin Test; the function returns 'true' when the number is actually NOT a prime number. Perrin Pseudoprimes are very rare, fewer are found for this test than is found for many other tests. The only two Perrin Pseudoprimes found less than a million are 271,441 and 904,631. Contrast this with the two lowest pseudoprimes for the Lucas test - 705 and 2465.

Below is the function code for the TI-89/92/V200 family of calculators:

Perrin Probablistic Prime Test
Function Code for TI-89/92/V200 Series Calculators

:perrp(z)
:Func : Local a,b,t
:[[0,1,1][1,0,0][0,1,0]] \->\ a : z-2 \->\b
:[[1,0,0][0,1,0][0,0,1]] \->\ t
:Loop
:If mod(b,2)=1 : mod(t*a,z) \->\ t
:(b-mod(b,2))/2 \->\ b
:If b=0 : Exit
:mod(a^2,z) \->\ a
:EndLoop
:if mod((t*[[2][0][3]])[1,1],z)=0 : return true
:return false
:EndFunc

The format for this test is perrp( z ) with z a positive integer. Here are some examples:

perrp( 41 ) returns 'true'

perrp( 93 ) returns 'false' ( 93 = 3 * 31 )

perrp( 651693055693681 ) returns 'false' in 9.11 sec so our example Carmichael Number didn't fool the Perrin test either. Notice that it took the Perrin test longer to run due to a larger matrix but the Perrin test is also more powerful.

perrp( 271441 ) returns 'true' in 3.00 sec

perrp( 904631 ) returns 'true' in 3.47 sec

The above two examples demonstrate the existence of Perrin Pseudoprimes - integers that fool the Perrin test. Both 271441 and 904631 are composite integers, not prime. Their factorizations are; ( 271441 = 521 * 521 ) and ( 904631 = 7 * 13 * 9941 ).

TITLE: Lucas and Perrin Probablistic Prime Tests
URL: https://jcullen88.github.io/CullenGenealogyHomepage/Math4.html
© October 12, 2006 - Jim Cullen - all rights reserved.

Use your Back Button or click here to go to the Math Index