Detecting False Reports In Primality Tests By The Oddcomp(z) Method


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: 18/9/97. revision:20/9.)


Abstract

Public-key algorithms need plenty of prime numbers. There are more primes than the number of atoms in the universe [1,2]. All standing trees on planet Earth will not be sufficient to produce paper pulp to publish all the 512-bit primes in bound volumes. How do we detect false reports by probabilistic primality tests? The author recommends the use of the Oddcomp(z) test method described in this paper. If a primality test reports a probable prime whilst the Oddcomp(z) method reports a composite, then this is classified as a false report. The method is manually tested against Maple V R 3's Isprime( ) probabilistic primality test function. If exhanstive false reports are to be made, the Pentium used by the author will fail to make an impact. A supercomputer will be more suitable. The only tests made are in the zone for integers close to 2^50 in magnitude. No counter-examples have been found. The algorithm will fail to validate a report by a primality test if it fails to generate an odd integer coincident with the one being primality tested. In other words, it is a partial test only.


1. Introduction


There are currently quite a few primality test algorithms available but how do we evaluate the performance? The author suggests that we should measure the false report counts in a chosen integer interval using the Oddcomp(z) method to be described in this paper. The method is a fair one since it measures the density of false reports within a fixed integer interval which are connected with the probablistic property common to primality tests such as Solovay-Strassen, Lehmann, Rabin-Miller and Lucas primality tests. The method is found to be practical although it would be too slow for exhaustive tests conducted with a Pentium. The algorithm is quite straightforward but requires multiple precision arithmetic softwares which are readily available in symbolic packages but not in compiled langauges. The method would be more suitable for use with a supercomputer. Only sample calculations have been made as the author found it too tedious to mount an ambitious numeric project with it.


2. Why RSA needs plenty of primes?


The RSA public key algorithm on which PGP is based makes use of five numbers [1,2]:


p: A very large prime number
q: Another very large prime number
n Their product (n = p * q)
e The encryption key
d: The decryption key


Since n is publicly known, anyone could take a shot at factoring it into p and q in order to find e and d. This paper is not about factoring large integers but the detection of false reports by primality tests. The method uses a conventional primality test to compute probable primes in a finite contiguous Odd(z) sequence and tests the terms against a similar stretch generated by Oddcomp(z). We know that Oddcomp(z) will be sparser than Odd(z) since the latter might contain primes. But we also know that Oddcomp(z), if full expanded, displays all the odd numbers which are composites, i.e., nonprimes. Therefore if a primality test reports an integer as a prime and the Oddcomp(z) method reports it as a composite, then the latter is correct thus revealing a false report by the former. Ideally, one could formulate a determinstic primality test method as outlined in Table 1. This however depends on global expansion of Oddcomp(z) which is not very practical.


Finite overlapping stretches of Odd(z) and Oddcomp(z) are shown in equations (1a) and (1b) where k is an odd integer.

Odd(z) = False/z^(k-2)+ True/z^k + False/z^(k+2)+ False/z^(k+4)+ True/z^(k+6) ......(1a)

Oddcomp(z) = 1/z^(k-2) + 0/z^k + 1/z^(k+2) + 1/z^(k+4) + 1/z^(k+6) ....................(1b)

Table 1 should be studied by referring to correspondingly ordered terms in equations (1a) and (1b). In Oddcomp(z), a zero in the numerator means that this term does not appear in the sequence which indicates that this integer is not a composite. Note that numerators in Oddcomp(z) can be greater than unity due to presence of duplicities of identical terms in expansions. If Oddcomp(z) is to be subtracted from Odd(z) to find Prime(z), then Oddcomp(z) must be normalised by the operator Normc( ). A fully expanded Oddcomp(z) will report all the odd composites and therefore can be described as a determinstic primality test. This is because if an odd integer is a true prime, then no odd composite will be reported by Oddcomp(z). This method is impractical as it takes too much computing resources to perform it.


...............Table 1 - Exhaustive Compositeness Tests On Odd Integers
-------------------------------------------------------------------------------------------------------------------
Terms from Odd(z).......Terms from Oddcomp(z).......Remarks
------------------------------------------------------------------------------------------------------------------
True/z^k.......................(1 or >1)/z^k....................Primality test is wrong.
.............................................................................This is not a prime.
.............................................................................This is one way to find
..............................................................................false reports from primality
..............................................................................tests.
-------------------------------------------------------------------------------------------------------------------
True/z^k......................0/z^k.................................This is a deterministic
..............................................................................primality test! Yes, it
..............................................................................is definitely a premium
..............................................................................grade prime.
-------------------------------------------------------------------------------------------------------------------
False/z^k.....................(1 or > 1)/z^k.....................Yes this is a composite.
..............................................................................Primality test reports
..............................................................................correctly.
--------------------------------------------------------------------------------------------------------------------
False/z^k.....................0/z^k..................................Primality test says False.
..............................................................................Oddcomp(z) test says it is
..............................................................................a prime. The latter
..............................................................................is correct! This is a
..............................................................................prime! Another false report
..............................................................................is weeded out.
--------------------------------------------------------------------------------------------------------------------


If the strategy in table 1 can be realised, we have a determinstic primality test method. But Table 1 is not practical as it takes too long to generate integers up to 512-bit key sizes and greater starting from i = 1. Therefore we must compromise but if we do this, we have lost the determinstic method described in Table 1! Yet not all are lost. We can use the Oddcomp(z) method to detect false report in primality tests.


3. The Oddcomp(z) Method

Proceed according to the following steps:

(i) Generate a random number in the form 2^k+ m.

(ii) Using this random number as the starting point for the odd sequence Odd(z), generate a finite odd sequence using the sequence algebraic formula given by equation (2):

Odd(z):=sum(isprime(2*i+1)/z^(2*i+1),i=2^k+m..2^k+m+d); ..............................(2).

where d is the number of contiguous odd integers to be generated starting from the chosen random number. For convenience we use Maple V R 3's Lucas primality testing function called isprime( ) in the numerators of terms generated by the above formula where True means a probable prime and False means a probable composite. You can test this on any other primality test method of interest to you.

(iii) We generate a finite sequence of odd composite numbers with prechosen lower bound of ilowerbound = (2^k+m)/3 and iupperbound of i = (2^k+m+d)/3 using the Oddcomp(z) formula given by equation (3). The recommended range for the outer loop counter j should be set with jlowerbound = 1 and the jupperbound j= d.

Oddcomp(z):=sort(sum(sum(1/(z^(2*i+1)*(z^(2*j*(2*i+1)))),i=(2^k+m)/3..(2^k+m+d)/3),j=1 ..d)); ................................................................................................................(3).

Note that we do not generate Oddcomp(z) exhaustively starting from i = 1 since this will waste too much computing resources. By starting high up, we are taking the risk that some composite numbers with small factors will be missed. Thus a nonreport of an odd composite does not necessary imply that that integer is a prime. This method is only deterministic if an odd composite integer is reported against a probable prime found by a primality test method. This method will be applied to test primality test results in the 2^50 range as described in example 1.

(iv) We compare corresponding terms in Odd(z) and Oddcomp(z) and arrive at the strategy outlined in Table 2.


.............Table 2 - Partial Compositeness Tests On Odd Integers
-------------------------------------------------------------------------------------------------------------------
Terms from Odd(z)....Terms from Oddcomp(z)......Remarks
------------------------------------------------------------------------------------------------------------------
(1)True/z^k .......................(1 or >1)/z^k...............Primality test is wrong.
..............................................................................This is not a prime.
..............................................................................This is one way to find
..............................................................................false report from primality
..............................................................................tests.
-------------------------------------------------------------------------------------------------------------------
(2)True/z^k .......................0/z^k...........................Not deterministic as
..............................................................................there may be small factors
..............................................................................which are not reported by
..............................................................................Oddcomp(z). So the
..............................................................................test is still probablistic.
..............................................................................No improvement.
-------------------------------------------------------------------------------------------------------------------
(3)False/z^k.....................(1 or > 1)/z^k.................Yes, definitely a composite.
--------------------------------------------------------------------------------------------------------------------
(4)False/z^k.....................0/z^k.............................Not deterministic as
..............................................................................there may be small factors
..............................................................................which are not reported by
..............................................................................Oddcomp(z). So the
..............................................................................test is still probablistic.
..............................................................................No improvement.
--------------------------------------------------------------------------------------------------------------------


From Table 2, it can be seen that only test nos. 1 and 3 are deterministc but there is a chance that Oddcomp(z) will miss some small factors which explains why test nos. 2 and 4 do not contribute to improvement. We can also introduce a search at the small end by a Maple line by scanning i from 1 to 1021 as shown in equaiton (4) but there is still a chance that some intermediate factors will be missed unless we do exhaustic global expansion which will be too resource intensive. That is why this is not a determinstic primality test method.


Oddcomp(z):=sort(sum(sum(1/(z^(2*i+1)*(z^(2*j*(2*i+1)))),i=3..1021),j=1..1)); ...........(4).


4. A Worked Example


The worked example demonstrates how the Oddcomp(z) method can be used to detect faulty primality reports or counter-examples by a primality method. In the present example, the isprime( ) function from Maple V R 3 is tested in the range from 2^50 to 2^50+1000 which is equivalent to keysizes of 13 decimal digits. These are not really large integers in the world of encryption. No counter examples have been found in this range using Oddcomp(z) method.


Odd(z):=sort(sum((isprime(2*i+1)-false)/(true- false)/z^(2*i+1),i=3*375299968947500..3*375299 968948000));

.........................1................................1.................................1.................................1
Odd(z) := --------------- + ---------------------- + --------------------- + -----------------
.........2251799813685001....2251799813685011....2251799813685017 ....2251799813685083
.......z..................................z..................................z....................................z

....................1................................1.................................1................................1
+ --------------------- + --------------------- + --------------------- + ---------------------
....2251799813685109....2251799813685119....2251799813685269 ....2251799813685313
..z..................................z...................................z..................................z

......................1.................................1................................1.................................1
+ --------------------- + --------------------- + --------------------- + ---------------------
....2251799813685329....2251799813685349....2251799813685413 ....2251799813685439
..z.................................z...................................z...................................z

.........................1.............................1.................................1.................................1
+ --------------------- + --------------------- + --------------------- + ---------------------
....2251799813685523....2251799813685577....2251799813685581 ....2251799813685613
..z..................................z..................................z.....................................z

............................1..........................1................................1...............................1
+ --------------------- + --------------------- + --------------------- + ---------------------
....2251799813685629....2251799813685641....2251799813685661 ....2251799813685677
..z..................................z..................................z.....................................z

.....................1................................1..................................1..............................1
+ --------------------- + --------------------- + --------------------- + ---------------------
....2251799813685727....2251799813685871....2251799813685881 ....2251799813685889
..z..................................z..................................z....................................z

......................1................................1................................1...............................1
+ --------------------- + --------------------- + --------------------- + ---------------------
....2251799813685893....2251799813685907....2251799813685911 ....2251799813685991
..z..................................z..................................z...................................z

.....................1................................1.................................1...................................1
+ --------------------- + --------------------- + --------------------- + ---------------------
....2251799813686081....2251799813686151....2251799813686169 ....2251799813686211
..z..................................z...................................z..................................z

.....................1..................................1................................1...................................1
+ --------------------- + --------------------- + --------------------- + ---------------------
....2251799813686217....2251799813686229....2251799813686249 ....2251799813686301
..z..................................z..................................z....................................z

....................1...................................1................................1...................................1
+ --------------------- + --------------------- + --------------------- + ---------------------
....2251799813686321....2251799813686337....2251799813686441 ....2251799813686457
..z...................................z..................................z.....................................z

1 1 1 1
+ --------------------- + --------------------- + --------------------- + --------------------- ....2251799813686459....2251799813686513....2251799813686531 ....2251799813686567
..z..................................z..................................z....................................z

1 1 1 1
+ --------------------- + --------------------- + --------------------- + ---------------------
....2251799813686609....2251799813686637....2251799813686639 ....2251799813686663
..z..................................z..................................z....................................z

.....................1.................................1................................1..................................1
+ --------------------- + --------------------- + --------------------- + ---------------------
....2251799813686693....2251799813686723....2251799813686781 ....2251799813686823
..z..................................z..................................z....................................z

......................1.................................1................................1..................................1
+ --------------------- + --------------------- + --------------------- + ---------------------
....2251799813686883....2251799813686903....2251799813686909 ....2251799813686939
..z..................................z..................................z..................................z

......................1................................1.................................1.....................................1
+ --------------------- + --------------------- + --------------------- + ---------------------
....2251799813686981....2251799813687051....2251799813687057 ....2251799813687113
..z..................................z...................................z.....................................z

.....................1.................................1..................................1....................................1
+ --------------------- + -------------------- + --------------------- + ---------------------
....2251799813687173....2251799813687197....2251799813687243 ....2251799813687287
..z..................................z..................................z......................................z

....................1..................................1.................................1.................................1
+ --------------------- + --------------------- + --------------------- + ---------------------
....2251799813687293....2251799813687299....2251799813687309 ....2251799813687311
..z..................................z...................................z.....................................z

....................1..................................1..................................1................................1
+ --------------------- + --------------------- + --------------------- + ---------------------
....2251799813687339....2251799813687377....2251799813687381 ....2251799813687387
..z..................................z..................................z.......................................z

....................1..................................1..................................1..................................1
+ --------------------- + --------------------- + --------------------- + ---------------------
....2251799813687429....2251799813687441....2251799813687503 ....2251799813687561
..z..................................z..................................z......................................z

....................1..................................1..................................1.................................1
+ --------------------- + --------------------- + --------------------- + ---------------------
....2251799813687579....2251799813687621....2251799813687623 ....2251799813687647
..z..................................z...................................z.......................................z

.....................1.................................1..................................1................................1
+ --------------------- + --------------------- + --------------------- + ---------------------
....2251799813687689....2251799813687693....2251799813687747 ....2251799813687759
..z..................................z..................................z.....................................z

.....................1.................................1..................................1...............................1
+ --------------------- + --------------------- + --------------------- + ---------------------
....2251799813687797....2251799813687873....2251799813687947 ....2251799813687971
..z..................................z..................................z......................................z

....................1
+ --------------------- .........................................................................(5).
....2251799813687987
..z

The Maple line for Oddcomp(z) used to generate odd composite numbers was based on equation (6) given below. Note that the range of j has been set from 1 to 50 for simplicity. As i increases, the number of even intervals will decrease so that a better loop counter for j could be j=1..50-i-1.

Oddcomp(z):=sort(sum(sum(1/(z^(2*i+1)*(z^(2*j*(2*i+1)))),i=375299968947950 ..375299968948000),j=1..50));...........................................(6).

No faulty reports or counter-examples were discovered in the above range of probable primes generated by Maple's isprime( ) function. It has been mentioned that perhaps such counter-examples might surface with very large integers of hundreds of digits (see reference 6(a)). Even computing in the present range of 2^50, it was necessary to break the range into incremental steps of 50 interval units. When testing in the hundred decimal digit region, possibly the incremental step will have to be reduced to 5 or 10 which makes computations by a Pentium impractical. This is the reason why no further tests have been conducted and the present status is that no counter-examples have been found for Maple's isprime( ) function. Oddcomp(z) will yield determistic odd composite values but it will miss those with small factors. This might not be objectionable since public key systems favour the use of strong primes.


5. Conclusions


The Oddcomp(z) method generates odd composites deterministically and wherever these are reported, these can be used to check against probable primality tests. No exhaustive investigations have been conducted since computations using a Pentium becomes too tedious in the high end of the integer number system. However, this method should be suitable using a workstation or a supercomputer. Now that a systematic method is available through the Oddcomp(z) method, one is likely to hear more on counter-examples in primality tests in future. The author suggests that this method might be useful for enhancing the quality of industrial grade primes. Since it is a fast algorithm, it could be incorporated into existing primality tests to weed out faulty primality reports.


6. References:


(a) Brief Information On Maple V R 3's Isprime( ) function, (abstracted from Help menu):


FUNCTION: isprime - primality test

CALLING SEQUENCE:
isprime(n)

PARAMETERS:
n - integer

SYNOPSIS:
- The function isprime is a probabilistic primality testing routine.

- It returns false if n is shown to be composite within one strong pseudo-primality test and one Lucas test and returns true otherwise. If isprime returns true, n is ``very probably'' prime - see Knuth ``The art of computer programming'', Vol 2, 2nd edition, Section 4.5.4, Algorithm P for a reference and H. Reisel, ``Prime numbers and computer methods for factoriza- tion''. No counter example is known and it has been conjectured that such a counter example must be hundreds of digits long.

(b) Published Papers Including Those In The Author's Website:


1. Garfinkel S. (1995): Encryption for Everyone, PGP Pretty Good Privacy, O'Reilly & Associates, Inc., January Edition, March 1995.

2. Schneier B. (1996): Applied Cryptography, Protocols, Algorithms, and Source Code in C, second edition, Wiley, 1996, Oak Park, Illinois.

3. Huen Y.K.: A Simple Introduction To Sequence Algebra, URL site: http://web.singnet.com.sg/~huens/

4. Huen Y.K.: Unsolved Problems In Sequence Algebra, URL site: http://web.singnet.com.sg /~huens/ .

5. Huen Y.K. : Methods Of Developing Sequence Algebraic Formulations For Comp(z) and Prime(z). URL site: http://web.singnet.com.sg /~huens/ .

6. Huen Y.K.: Improved Formulations For Comp(z) and Prime(z). URL site: http://web.singnet.com.sg/~huens/ .

7. Huen Y.K. : Lemmata, Corollaries, And Theorems In Sequence Order Analysis. URL site: http://web.singnet.com.sg/~huens/ .

8. Huen Y.K.: A Matrix Map for Prime and Non-prime Numbers, INT. J. Math. Educ. Sci. Technol., 1994, VOL. 25, NO.6, pp 913-920.

9. Huen Y.K.: Some Interesing Properties Of The Natural Number System, Int. J. Math. Educ. Sci. Technol., 1996, VOL.27, NO. 5, 685-691.

10. Huen Y.K.: Visual algebra and its applications, INT. J. Math. Educ. Sci. Technol.,1997, VOL.28 NO.3, 333-344.

11. Huen Y.K.: Twin-primes revisited. Int. J. Math. Edu. Sci. Technol. 1997, Vol.???. No. ???-???. ( the the press as proof paper mes 100488).

======================== END OF PAPER ======================