A Sequence Algebraist's View Of Lehmann's Primality Test
by
Huen Y.K.
CAHRC, P.O.Box 1003, Singapore 911101
http://web.singnet.com.sg/~huens/
email: huens@mbox3.singnet.com.sg
(A short communication - 1st released: 6/10/97 )
Abstract
In sequence algebra, we already know that it is easy to derive the closed form generating
function for composite numbers rather than primes although such functions for Comp(z),
Oddcomp(z) and Prime(z) have already been derived and are globally deterministic [3 to 8].
It seems odd that most primality tests are deterministic only on primes and not on
composites. These tests will never falsely indicate that a prime number is composite but
there is a chance of reporting falsely a composite as a prime although in practice
probability can be set very small by increasing the number of repeat tests[1]. By contrast, the equation
of divisibles in sequence algebra will never make a false report on a composite[3,4].
Lehmann's test on a prime is probabilistic but if p is really a prime, it would confirm it very
fast [1] whereas the equation of divisibles will confirm composites deterministically but not
that fast. The latter can confirm primes deterministically via a longer route but it does not
qualify as a fast primality test in the same class as Lehman's, Solovay-Strassen, and other
primality tests. Generating function such as Oddcomp(z) is suitable for use to calibrate
primality tests failure rates on composites since it is deterministic and therefore should be
used as a standard reference or quality control measure[9].
1. Introduction
Factoring attacks on large numbers have become a popular sport. The inventors of RSA
proposed a challenge based on the RSA-129 number which is equivalent of a 429-bit key [2].
One prerequisite to factoring such a number is that we must be sure that the factors are
primes. But all primality tests are probabilistic even though the chance of a false report can
be set very small by increasing the number of repeat tests[1]. In order to understand this
probabilistic mechanism, Lehmann's algorithm is chosen for study. Here is how Lehmann's method is
used to test if p is prime.
Lehmann [1]
(1) Choose a random number a less than p.
(2) Calculate a^(p-1)/2 mod p.
(3) If a^(p-1)/2 /= 1 or -1 (mod p), then p is definitely not prime.
(4) If a^(p-1)/2 = 1 or -1 (mod p), then the likelihood that p is not prime is no more than 50%.
Maple V R 3's random number generator can generate integers less than p by calling
rand(p) which is the abbreviated form of rand(0..p-1). Here is how we test the rand(p)
function.
die:=rand(23); ...........................................(1).
die := proc()
local t;
global _seed;
_seed := irem(427419669081*_seed,999999999989); t := _seed; irem(t,23)
end
Test by computing ten times:
die(); die(); die(); die(); die(); die(); die(); die(); die(); die();
0
18
5
9
9
0
0
4
22
12
Test 1: The Maple line shown in equation (2) will test the prime p = 23 six times per throw.
Note that the x-variable is only useful if a range of values for p is computed such as
p=3..23 but this feature is retained here in case readers wish to experiment with that
usage. The reason for providing a summation for p even though only one value is used
is because Maple's die( ) does not seem to accept an externally assigned value for p.
eval(sort(sum(sum((die(p)^((p-1)/2) mod p)/(x^i*z^p),p=23..23),i=1..6))); ............(2).
Throw (1):
.............................1..........1.............1............1..........1............1
...........................----- + ------ + ------ + ------ + ------ + ------
............................23........23..2......23..3.....23..4....23...5......23..6
..........................z...x......z...x........z....x......z...x......z....x.......z...x
Throw (2):
............................22.........22............22.........22........22..........22
...........................----- + ------ + ------ + ------ + ------ + ------
............................23........23..2......23..3.....23..4....23...5......23..6
..........................z...x......z...x........z....x......z...x......z....x.......z...x
Throw (3):
.............................1..........1.............1............1..........1............1
...........................----- + ------ + ------ + ------ + ------ + ------
............................23........23..2......23..3.....23..4....23...5......23..6
..........................z...x......z...x........z....x......z...x......z....x.......z...x
Throw (4):
............................22.........22...........22........22.........22..........22
...........................----- + ------ + ------ + ------ + ------ + ------
............................23........23..2......23..3.....23..4....23...5......23..6
..........................z...x......z...x........z....x......z...x......z....x.......z...x
Comments: Throw (2) and throw(4) return numerator coefficients greater than
1 which could indicate that 23 is definitely not a prime by rule 3 above. This
might be caused by missed information in the secondary source [1]. Perhaps the
rule should read: if the numerator is 1 or -1, then accept it as a prime. If it is not,
it might be a composite so reject and try again.
Test 2: The Maple line shown in equation (3) will test the composite p = 22 six times per
throw.
eval(sort(sum(sum((die(p)^((p-1)/2) mod p)/(x^i*z^p),p=22..22),i=1..6))); ............(3).
Throw (1):
................................1/2........1/2..........1/2.......1/2.......1/2.........1/2
............................13.........13...........13........13.........13..........13
...........................----- + ------ + ------ + ------ + ------ + ------
............................22........22..2......22..3.....22..4....22...5......22..6
..........................z...x......z...x........z....x......z...x......z....x.......z...x
Throw (2):
................................1/2........1/2..........1/2.......1/2.......1/2.........1/2
............................19.........19...........19........19.........19..........19
...........................----- + ------ + ------ + ------ + ------ + ------
............................22........22..2......22..3.....22..4....22...5......22..6
..........................z...x......z...x........z....x......z...x......z....x.......z...x
Throw (3):
................................1/2........1/2..........1/2.......1/2.......1/2.........1/2
..............................5...........5.............5..........5...........5..........19
...........................----- + ------ + ------ + ------ + ------ + ------
............................22........22..2......22..3.....22..4....22...5......22..6
..........................z...x......z...x........z....x......z...x......z....x.......z...x
Throw (4):
................................1/2..........1/2............1/2.........1/2............1/2.............1/2
............................14............14............14...........14.............14.............14
......................12----- + 12------ + 12------ +12 ------ +12 ------ +12 ------
..............................22..........22..2.........22..3.........22..4........22...5..........22..6
............................z...x........z...x...........z....x..........z...x..........z....x...........z...x
It can be seen from Test 1 that the numerator coefficients will always be whole integers but
not necessary 1 or -1 as stipulated by rule 3. The likelihood that p is not prime is no more
than 50 percent by rule 4 which seems reasonable for 4 throws. In test 2 for a composite p
= 22, the numerator coefficients will never be integers, therefore p is defintely not a prime
according to rule 3.
2. Generating Function For Prime(z)
Here is a sequence algebraic closed form generating function which will determine primes
and composites deterministically being given by equation (4). Those integers which are not
composites are definitely primes by mutual exclusions.
Primex(z):=series(z/(z^2-1) - sum(sum(1/(z^(2*i+1)*(z^(j*(4*i+2))-
1)),i=1..50),j=1..50),z=infinity,50); ...............................................................(4).
.........................1..................1.......1.........1.......1........1......2......1......1.......2......1......1.......3
Primex(z) := O(---) + 1/z + ---- + ---- + ---- + --- + --- - --- + --- + --- - --- + --- - --- - ---
..........................51................3........5.........7.....11......13....15.....17.....19.....21....23...25.....27
.........................z..................z........z.........z.......z.........z......z......z........z........z......z.......z.......z
..........1......1......2........3.......1.......4.......1.......1.......7........1........1
......+ --- + --- - --- ...- --- + --- - --- + --- + --- - --- +... --- - ---
...........29.....31....33.....35.....37.....39.....41.....43.....45......47......49
..........z......z.......z........z.......z........z.......z........z........z........z........z
In equation (4) if the numerators are unities, these are defintely primes. All composites are
preceded by negative signs with the numerator coefficients greater than unities. Is this not
better than the currently available primality tests? The answer is no. The catch is that you
must expand a series from the very beginning for i and j and these are very resource intensive
for large integers. Expansions of closed forms are memory intensive since all terms must be
stored and summed.
To overcome this limitation, the following general open form is suggested by the author as
shown in equation (5) where ub is the common upperbound control parameter and f1 and f2
have to be found experimentally to optimise the throwing power of this expression [7].
Generally, f1 should be greater than 1 and f2 less than 1.
Prime(z):=sort(sum(1/z^(2*i+1),i=1..f1*ub) - sum(sum(1/z^((2*i+1)+j*(4*i+2)),
i=1..ub),j=1..f2*ub)); .....................................................................................(5).
Equation (6) gives a small example for ub = 25 and for a starter set f1 = f2 = 1. From the
expansions, one notices that all terms with positive signs are definitely primes and the
prediction is correct up to prime of 47 which is about double the range of ub. One recalls that
Comp(z) also has about the same throwing power [7]. In equation (7) we lower the upperbound
of j to half, i.e. making f2 ~= 1/2, and check again. No primes are missing and the numerator
coefficients are unaltered by this modification. Next by retaining f2 = 1/2 and make f1 = 2 in
equation (8), we check the throwing power again. This time it is noticed that the range of
prime is correctly extended to 101 which is doubled that of equation (7), i.e. f1=2. Next we
double f1 again by making f1=4 as shown in equation (9). This time some terms
fail to expand completely! Therefore optimal setting for Prime(z) is f1 = 2 and f2 = 1/2.
Prime(z):=sort(sum(1/z^(2*i+1),i=1..25) -sum(sum(1/z^((2*i+1)+j*(4*i+2)), i=1..25),
j=1..25)); ......................................................................................................(6).
......................1........1.......1.......1.......1.......1........1.......1.....1......1.......1.......1.......1......1
Primex(z) := ---- + ---- + ---- + --- + --- - --- + --- + --- - --- + --- - --- + --- + --- - ---
........................3........5.......7.......11.....13.....15.....17.....19....21....23....27.....29.....31....33
......................z........z........z........z........z.......z........z........z.....z.......z.......z.......z.......z......z
...........1.......1.......1.......1.......1......3......1.......1.....2......2.......4......2......2.....4.....2.....3
.........- --- + --- - --- + --- + --- - --- + --- - --- - --- - --- - --- - --- - --- - --- - --- - ---
.............35.....37.....39.....41.....43....45....47.....51...55....57.....63...65....69...75...77....81
...........z........z.......z........z.......z......z.......z........z......z......z.......z......z......z......z.....z......z
.........-..........................................................................................................
............2..........2..........2..........2..........1..........2..........2..........2..........1..........2..........1
........- -----... - -----. - -----. - -----. - -----. - -----. - ----- - ----- - ----- - ----- - -----
............2107....2115....2193....2205....2209....2295....2303....2397....2401....2499....2601
...........z..........z..........z...........z...........z...........z..........z..........z..........z..........z..........z
Prime(z):=sort(sum(1/z^(2*i+1),i=1..25) - sum(sum(1/z^((2*i+1)+j*(4*i+2)),i=1..25)
,j=1..13)); ....................................................................................................(7).
......................1........1.......1.......1.......1.......1........1.......1.....1......1.......1.......1.......1......1
Primex(z) := ---- + ---- + ---- + --- + --- - --- + --- + --- - --- + --- - --- + --- + --- - ---
........................3........5.......7.......11.....13.....15.....17.....19....21....23....27.....29.....31....33
......................z........z........z........z........z.......z........z........z.....z.......z.......z.......z.......z......z
...........1.......1.......1.......1.......1......3......1.......1.....2......2.......4......2......2.....4.....2.....3
.........- --- + --- - --- + --- + --- - --- + --- - --- - --- - --- - --- - --- - --- - --- - --- - ---
.............35.....37.....39.....41.....43....45....47.....51...55....57.....63...65....69...75...77....81
...........z........z.......z........z.......z......z.......z........z......z......z.......z......z......z......z.....z......z
.........-.............................................................................................................
..............1..........1..........1..........1...........1...........1
........ - -----.. - -----.. - -----.. - -----.. - ----- ..- -----
..............1215....1225....1269....1275.....1323......1377
.............z..........z...........z..........z............z............z
Prime(z):=sort(sum(1/z^(2*i+1),i=1..50) - sum(sum(1/z^((2*i+1)+j*(4*i+2)),i=1..25),
j=1..13)); ....................................................................................................(8).
......................1........1.......1.......1.......1.......1........1.......1.....1......1.......1.......1.......1......1
Primex(z) := ---- + ---- + ---- + --- + --- - --- + --- + --- - --- + --- - --- + --- + --- - ---
........................3........5.......7.......11.....13.....15.....17.....19....21....23....27.....29.....31....33
......................z........z........z........z........z.......z........z........z.....z.......z.......z.......z.......z......z
........1.......1......1.......1.......1......3......1......1.......1......1......1......1......1......3......1.......1
.....- --- + --- - --- + --- + --- - --- + --- - --- + --- - --- - --- + --- + --- - --- - --- + ---
........35.....37.....39.....41.....43....45....47....51.....53....55....57....59.....61....63....65......67
........z.......z.......z.......z........z......z.......z......z........z......z......z.......z.......z.......z.......z......z
........1........1......1......3.......1.......1......2......1.......1......1......1......1......1......2......1
.....- --- + --- + --- - --- - --- + --- - --- + --- - --- + --- - --- - --- + --- - --- + ----
........69.....71......73....75.....77....79....81....83.....85.....89....91....95.....97....99...101
........z.......z.......z.......z.......z......z......z......z.......z.......z......z......z......z......z......z
.........5........1........2........3.........2.........1........1........2........1........2........5.........1.........2
.....- ----. - ---- .- ---- .- ---- .- ----. - ---- - ----. - ---- .- ----. - ----. - ----. - ----. - ----
.........105....111....115....117.....119.....121....123....125....129.....133.....135.....141.....143
.........z........z........z........z.........z..........z........z.........z.........z.........z.........z..........z..........z
.....-.........................................................................................................
...........1
........- -----
...........1377
.........z
Prime(z):=sort(sum(1/z^(2*i+1),i=1..100) - sum(sum(1/z^((2*i+1)+j*(4*i+2)),i=1..25)
,j=1..13)); ...............................................................................................(9).
.........................1............1.......2......2......1......2......2......2.......2......4.......1......2.......2
Primex(z) := ---------- - ---- - --- - --- - --- - --- - --- - --- - --- - --- - --- - --- - ---
.......................2................9.....15.....21.....25....27....33....35....39.....45....49....51.....55
....................(z - 1).........z.......z.......z.......z......z.......z.......z.......z.......z......z.......z........z
........2......4......2......2......4......2......3......2......1......2......1......2......3......5.......1
.....- --- - --- - --- - --- - --- - --- - --- - --- - --- - --- - --- - --- - --- - ---- - ----
........57....63....65....69....75....77....81....85....87....91....93....95....99....105...111
........z......z......z......z......z......z......z......z......z......z......z......z......z......z.......z
........2......3.......2.......1......1.......2........1.......2.......5.......1.......2......1.......3
.....- ---. - --- .- ---. - ---. - ---. - ---. - --- .- ---. - ---. - ---. - --- .- ---. - ---.
........115...117...119...121...123...125...129...133...135...141...143...145...147
........z......z.......z........z........z.......z........z.......z........z.......z........z.......z........z
........3......1.......2......3.......1.......2......3........1........2.............4................3.......1
.....- ---. - ---. - ---. - ---. - ---. - ---.. - ---.. - --- - --- - ------------ - --- - ---
........153...155...161...165...169...171...175...185...187...189.....195.........2......201
........z.......z.......z.......z........z.......z.......z........z........z.......(z....-1)z............z.......z
..... -...........................................................................................................
...........1..........1..........1..........1..........1..........1..........1..........1.........1...........1.........1...........1
.....- -----. - ----- .- -----. - -----. - ----- .- -----. - -----. - -----. - -----. - -----. - -----. - -----
........1081....1107....1125....1127....1161....1173....1175....1215....1225....1269....1275....1323
........z..........z..........z..........z..........z..........z..........z...........z.........z..........z..........z..........z
..........1
.....- -----
..........1377
.........z
3. Conclusions
The open form of Prime(z) can be used to compute to very large integer values but both
Odd(z) and Oddcomp(z) must be computed from the beginning of j = 1..ub. If attempts are
made to use a partial range for i and j starting somewhere high up in the range, composite
predictions will become partial but still stay deterministic. This might appear that it could be
useful in compositeness tests but primes become indeterministic and it would be very difficult to design an algorithm to locate
the exact range which will cover the particular large composite integer to be tested. The
author does not rule out that this could be done. Perhaps someone more perceptive will find
a way of using this property.
The applications of Prime(z) is not in fast primality tests even though it is absolutely
deterministic. The author has been using the Oddcomp(z) generating function to detect false
reports from primality test but so far he has detected none [7]. If one needs 100% confidence of
large primes, then the open form would be appropriate but one pays a price for it. Modular
arithmetic can be very cryptic and recondite. Most theorems based on modular arithmetics
end up looking like the work of magicians. It is not easy for a novice to
understand proofs suing modular arithmetics. By expanding modular arithmetic expressions
into a sequence, one could gain more insight on how it works. This approach might be useful
in classroom teaching.
Sequence algebra does give new insights on properties of number sequences which are not
covered by conventional number theory. In fact as the two disciplines are based on
axiomatic bases which are poles apart, they do not cover exactly the same territories in the
number domain. It is beneficial to accept both disciplines which will greatly augment the
analytical tool kit of a number theorist. Perhaps one day these two disciplines will grow
enough to become well integrated but for the time being the differences between them raise
great excitements. What is the point of finding a new theory which explains essentially the
same thing. It is like someone who has been visiting his local botanical garden for years
suddently being physically transported to an exotic equatorial forest in Kalimantan where
floras and faunas are totally different. What an adventure!
5. Reference:
1. Schneier Bruce: Applied Cryptography, Protocols, Algorithms, and Source Code in C,
Second Edition, Wiley, U.S.A. 1996, pp258 to 259.
2. Garfindkel Simson: Encryption for Everyone, - PGP Pretty Good Privacy, O'Reilly &
Associates, Inc. January Ed.: 1995.
3. Huen Y.K.: A matrix map for primes and nonprimes, Int. J. Math.Educ.Sci.Technol., 1994,
Vol.25, No.6, pp 913 - 920.
4. Huen Y.K..: Visual algebra and its applications, Int. J. Math. Educ. Sci. Technol., 1997,
Vol.28, No.3, 333-344.
5. Huen Y.K. Lemmata, Corollaries, And Theorems In Sequence Order Analysis. URL site:
http://web.singnet.com.sg/~huens/ .
6. Huen Y.K.: Detecting False Reports In Primality Tests By The Oddcomp(z) Method, URL
site: http://web.singnet.com.sg/~huens/ .
7. Huren Y.K.: The Throwing Power Of Oddcomp(z), URL site: http://web.singnet.com.sg/
~huens/
8. Huen Y.K.: Generating Large Odd Composites With Two Prime Factors, URL site:
http://web.singnet.com.sg/ ~huens/
9. Huen Y.K.: In Search Of Counter-Examples In Maple's Isprime Function, URL site:
http://web.singnet.com.sg/ ~huens/
======================== END OF PAPER ======================