In Search Of Counter-Examples In Maple's Isprime Function
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: 4/10/97, revision:6/10. )
Abstract
Here is a fast and efficient method of running primality tests through a large number of odd
composites instead of primes using the open form of the Oddcomp(z) function in an attempt
to find counter-examples in Maple's isprime function. We are assured by Prime Number
theorem that the ratios of primes to odd composite will fall as integer n increases. It is
therefore far easier to find odd composites than primes for testing at the large integer end.
The chance of encountering a false report on odd composites is much higher than that on
primes for large integers. The method could also be applied to other primality test methods.
The open form of Oddcomp(z) can generate odd composites deterministically. If a counter-
example is found then it definitely proves that isprime is probabilistic. On the other hand if
no counter example is found, then it proves nothing although one could report that
for the i value randomly chosen, no counter examples have been found in the subsequent
10000 odd composite terms with intervals in multiples of (4*i+2). It does not say anything conclusively about whether
counter-examples could occur in a given integer range if no counter-example has been
found in samples taken.
1. Introduction
The Oddcomp(z) method of testing a primality function for counter-examples was recently
described [3,4,5 ]. The test is conclusive on a primality test if just a single counter-example can
be found but if none are found then it is inconclusive. One can either use primes or odd
composites in the tests but it is far easier to use the latter since the open form of
Oddcomp(z) is already available and is 100% deterministic. Furthermore in the large integer
regions the ratios of odd composites to primes has been proven to increase by Prime
Number theorem. This makes primality tests by odd composites easy in the large integer regions. In this
paper we distinguish between odd composite against nonprimes since the latter include even
composites as well.
The original Maple programe line used for the search for false reports is given by equation
(1):
sum(sum((isprime(2*i+1+j*(4*i+2))-false)/z^(2*i+1+j*(4*i+2)),i=u1..u2+d),j=u1..u2+d);
....(1).
the parameter i represents the ith Z/i-layer selected for computations. The parameter j gives
the integer multiples of even offsets (4*i+2) displaced from the initial odd offset of (2*i+1).
The sum of an odd term with an even term ensures that the offset will always be odd. None
of the integer generated will ever be a prime. That is why the function for generating these
integers is called Oddcomp(z) [2,3,4]. Ideally one should set i = 1..infinity and j = 1..infinity to test
every possible odd composite in the natural number system but that is an impossibility. To
cut down on computational effort, i is set with a single integer value only, e.g., i =
2^512..2^512. This will still generate odd composites but divisors less or greater than 2^512
are excluded. This is not serious as odd composites generated are still deterministic and it
simply means that we are hop-skipping in large intervals along the odd composite number
line. We still will never run short of odd composites by this truncated method and we hope to
hit a counter example somewhere out there if there is one. If there is no hit, then it proves
nothing and all that we can claim is that with a randomly chosen seed value of i, we find no counter
examples.
The Maple line in equation (1) is a memory guzzler since it stores every odd composite
number and sums them. The Maple line in equation (3) fairs much better as we can scan
through in realistic time (say less than several hundred seconds) with the range of j set to
1..10000. The range of j needs not be set too high since it computes integer offsets in
multiples of (4*i+2) which can be very large numbers for large i. i is randomly chosen using
equation (2) and the value is used in equtaion (3) for testing the isprime function. If there is no counter-example, we would
expect the program to output 10000 zeroes. If there is even one counter-example, then we
expected a term such as (true-false)/z^oddcompsite. The outputs will be written on the
computer screen to be checked visually. Since the time taken never exceeds 2000 seconds
the work is not too arduous. For page economy, it is not possible to record the full outputs
but readers could repeat the computations easily using information contained in Table 2. It
may be difficult to get exactly the same random number as the seed is the CPU clock. It is
therefore possible that a reader might hit on a counter-example when the author
claimed there is none since the chance of the reader hitting on the same value of i
is very remote.
i:=rand()^5000; ..............................................................................(2).
for j from 1 to 10000 do (isprime(2*i+1+j*(4*i+2))-false)/z^(2*i+1+j*(4*i+2)) od; ....(3).
2. The Random Number Generator
In this paper, we will use Maple's isprime function to test 10000 "successive" odd composite
terms generated by the open form of Oddcomp(z) of equation (4) with i set to a fixed
randomly generated integer by Maple's rand( ) function using equation (2). The seed in rand( ) is the time
clock and the integer generated never exceeds 12 decimal digits. Since rand( ) cannot
generate random numbers exceeding 12 decimal digits, we will extend this by raising it to an
integer power n. This will compromise the randomness by the coarse intervals introduced between successive
odd composite numbers. Since we only generate one random number i at any one time, this is not
a serious problem. Table 1 summarises some findings on the performance of i=rand( ) and
i=rand( )^n.
Table 1 - Performance of Maple's rand( ) function
===================================
rand( ); 5 samples taken.
...............................628363443011
...............................313746086538
...................................5862664913
.................................74813656220
...............................643842443844
rand( )^n;
Comments: No exact number of decimal digits can be predicted as rand() generates
random numbers ranging from 0 to 12 significant figures.
rand( )^10;.................................~119 decimal digits
rand( )^20;.................................~221 decimal digits
rand( )^50;.................................~521 decimal digits
rand( )^100;.............................~1099 decimal digits
===================================
Thus the Maple program contains two lines given by equations (2) and (3).
Note that n is not a random number. So in
order to select the magnitudes of integers to be tested, one needs to select n manually
based on information from Table 1. j is set to j = 1..10000 so that 10000 odd composite
terms will be generated at any one session. If all the results are zeroes, we know there is no
counter-example. If there is one or more nonzero, then we will zero in to find the specific
values of i and j causing this counter-example. So far since no counter-examples have
been detected, this step has not been taken.
Typical worked example:
i := rand( )^10
i=259576851905612003410134556515554701308935171992746403781468732653983067992
95751163101948108576416266416035210080401
No counter-example is found in the 10000 odd composites terms within the range given below
which took 23 seconds to compute:
155746111143367202046080733909332820785361103195647842268881239592389840795
774506978611688651458497598496211260482409
to
103835932299282913604122025297352191617600247500538416440663122436246306858
5428638026404128239273803489174240473636220803
3. The Search For Counter-Examples
In Table 2 we summarise our findings. For page economy, we will only give essential
information for each, i.e., either (i) no counter-example is found or (ii) counter-example is
found. In the second case, we will also give the specific integer which causes a false report
from isprime( ) function if a counter-example has been found. Only one sample was
taken of each range but future results will be added to this paper when available. Please
watchout for dates of revisions.
Table 2 - Tests On Isprime( ) using equation (3).
(Note: i needs not be odd. The integer Oddcomp(z) computed using it will be odd.)
==============================================================
n=5; i:=rand()^5; ~50 decimal digits.
i := 4791536313137691519757553775531215278380617058599108548257
Time taken = 14 seconds
No counter example found.
n=10; i:=rand()^10;~119 decimal digits.
i :=
575611755685995059461919483012489312420772314284370742530025560008563612790
2569233531192688599083084\
81747033049045849
Time taken = 15 seconds
No counter example found.
n=20; i:=rand()^20;~234 decimal digits.
i :=
414085549194408768063892243201686840253943853523697140915349232733285831184
3223653362407987088853868\
749596410863673842886659634981032257717746209126098175513666630421341785393
4704176780567404582463264\
315208098773570994324071416277601
Time taken = 19 seconds
No counter example found.
n=50; i:=rand()^50 ;~596 decimal digits.
i :=
455903526577623241138744832142406620059348970344292560213908043508456037715
6168270342219609783888233\
541753654255859070532183890627819381764991240673819478765546086078341305137
0597948053088116915197245\
104944245588347044499066650276463037854176846965339951540225545774419291652
8346913096824653002542258\
803961036672793175931000938688264296830433923894010603060656958826379874793
7816396010026821149927523\
076347661222310205910255742282142909618771835311923885141172446736884489358
4781338195330781332605788\
549007985297461856530892233438496802316248372449536365473672279560324928394
9969591162973978624
Time taken = 14 seconds
No counter example found.
n=100; i:=rand()^100 ; ~1199 decimal digits.
i :=
397522578921886754188936277917138073229698730594297980076471106267926691365
9543897906463342054801215\
674965784869313748027932281802507341799349779739737057311278185944922122687
3532173569320217961950169\
...........................................truncated section................................
472588445470899515722747608190057266416653709025510908390420045688627106312
6108049562900568219861044\
015609103687014513894837364205159246921539306640625
Time taken = 31 seconds
No counter example found.
---From here on, the values of i are not shown for page economy-------------------------
n=500; i:=rand()^500 ;
i=5474 decimal digits.
Time taken = 123 seconds
No counter example found.
n=1000; i:=rand()^1000 ;
i=10593 decimal digits.
Time taken = 277 seconds
No counter example found.
n=2000; i:=rand()^2000 ;
i=23804 decimal digits.
Time taken = 418 seconds
Number of terms checked: 10000
No counter example found.
n=5000; i:=rand()^5000;decimal digits.
i = 57458 decimal digits.
Number of terms checked: 10000
Time taken = 1116 seconds.
Memory used = 1.4 Mbytes.
No counter example found.
n=6000; i:=rand()^6000;
i :=69786 decimal digits.
Number of terms checked: 10000
Time taken = 2274 seconds.
Memory used = 1.039 Mbytes.
No counter example found.
n=7000; i:=rand()^7000;
i :=81733 decimal digits.
Number of terms checked: 10000
Time taken = 1571 seconds.
Memory used = 1.193 Mbytes.
No counter example found.
n=8000; i:=rand()^8000;
i := 95417 decimal digits.
Number of terms checked: 10000
Time taken = 1886seconds.
Memory used = 2.229 Mbytes.
No counter example found.
n=9000; i:=rand()^9000;
i := 107091 decimal digits.
Number of terms checked: 10000
Time taken = 1980seconds.
Memory used = 3.176 Mbytes.
No counter example found.
n=10000; i:=rand()^10000;
i := 116309 decimal digits.
Number of terms checked: 10000
Time taken = 2311 seconds.
Memory used = 1.573 Mbytes.
No counter example found.
n>10000;....
Comments: Maple V R 3 shows unpredictable operations
depending on the size of random number i generated.
=====================================================
It was noticed that the time required to compute can vary quite a bit which may be
due to one or more of the following reasons:
(i) Some composites are easy to factor and some are hard. Also the number of
composites in a small interval may be quite variable. Since isprime is invoked every time,
this is the function which consumes most of the time resource. Hence it will have
significant effects on the total time used.
(ii) Since rand( ) may generate anywhere from 1 digit to 12 digits, rand( )^n does not
always generate i with the same number of decimal digits. This will have significant effects on
the time used.
4. Conclusions
The Oddcomp(z) method described in this paper is very suitable for testing most
primality tests since such tests will never falsely indicate that a prime number is
a composite [1]. The confidence level that a number is prime can be set lower by increasing
the number of tests. A primality test such as isprime has already got this confidence
level builtin but the information is not available to the author. If this level is set such
that there is one chance in 10^15 that a test will falsely indicate that a composite
number is prime, then the small samples made in this paper will hardly make any
impression. However, the method described here is basically sound and depends
on how much computing resources can be mustered to detect a false report. A Pentium
would be too slow but if one has the clout, one could orchestrate thousands of
Pentiums across international boundaries to mount such a hunt.
It is realised that one has nothing to say about findings outside the samples given in Table 2.
The universe of odd composites is so immense that increased samplings will not make a dent
on confidence of sampling. At best, one could select a particular range say around the RSA -
129 region and carry out exhaustive tests with up to 10000 samples. Than one might
have some confidence on primality tests in this range.
The author did encounter hangups in computations on some runs which at first he thought
might be due to isprime encountering a prime but its cause was traced to an accidentally corrupted
Maple software when attempting to search beyond n = 5000. After reinstallation, these
phenomena did not surface again.
The amount of search far exceeds what have been reported in this paper.
So far, the author has not encountered any counter-examples when using the
above Oddcomp(z) test method. This is simply due to the fact that no amount of
sampling will make any dent on the universe of odd composite numbers unless
one is unduely lucky to make a hit.
4. Reference:
Reference 2 is not directly relevant but it is included here for readers not
familiar with sequence algebra.
1. Schneier B.: Applied Cryptography, Protocols, Algorithms, and Source Code in C,
Second Edition, U.S.A. pp 258 to 262.
2. Huen Y.K.: Lemmata, Corollaries, And Theorems In Sequence Order Analysis. URL site:
http://web.singnet.com.sg/~huens/ .
3. Huen Y.K.: Detecting False Reports In Primality Tests By The Oddcomp(z) Method, URL
site: http://web.singnet.com.sg/~huens/ .
4. Huen Y.K.: The Throwing Power Of Oddcomp(z), URL site: http://web.singnet.com.sg/
~huens/.
5. Huen Y.K.: Generating Large Odd Composites With Two Prime Factors, URL site:
http://web.singnet.com.sg/ ~huens/.
======================== END OF PAPER ======================