From U21453@UICVM.UIC.EDU Tue Jul 29 18:54:23 1997
Date: Tue, 29 Jul 1997 08:21:35 -0400
From: "A.O.L. Atkin" <U21453@UICVM.UIC.EDU>
To: NMBRTHRY@LISTSERV.NODAK.EDU
Subject: Gaps,-plets, and BLS
(BLS = Brillhart, Lehmer, and Selfridge, Math. Comp. 1975)
Since Blair Kelly revived the subject of prime gaps(NMBRTHRY,
March, 1997), I have read the contributions of others and sporadically
thought myself about it; I planned to make a posting some weeks ago
with three components, viz General Speculation, some numbers, and two
theorems. The numbers and theorems were easy enough to set down, but
the speculation refuses to converge. I hope I may be forgiven for
presenting it in a somewhat unfinished and disconnected form. I may
have miscopied some numbers, but correct ones exist. Theorems, as
always, may be false.
* * * *
The various enterprises of gaps, -plets(cf. postings of Tony Forbes),
and "Consecutive primes in A.P." (cf. postings of Harvey Dubner),&c., can
all be regarded as the exhibition of a given set of successive prime gaps.
The successful computational technique is almost always "Format, Sieve,
and Test"; i.e., some general form is prescribed with a number of free
parameters(often 1), the choice of parameters is restricted by (often
extensive) sieving applied to the whole set, and finally individual cases
are successively tested until a desired case is found.
As to what is "desired", this must ultimately depend on the
whim of the number-theoretic public, but I venture here to suggest
a few criteria. In the case of gaps, it is clear that a substantial
collection exhibiting every even gap up to(say) 5000 would be of
value. If however particular gaps are chosen for extensive study,
there should not be too many of them; a new Olympic event of
26 miles 100 yards would generate little enthusiasm. Taking as a
first example the event "one gap of 1000", one might ask
(1)What is the smallest example?
(2)What is the smallest known example?
(3)What is the largest known example?
(4)What is a "best buy" in the sense that it can be found quickly
by some generic (non-deterministic!) algorithm?
One feels that the two end primes must have their primality proved, in
all cases; only the event "largest known string of consecutive composites"
can be exempt from this requirement. (To avoid any possible
misunderstanding, in view of my recent Offer, "proved" means proved,
not "prime but not proved".) Also, of course, if (1) is
answered, then (2) and (4) become vacuous, and we are left with
(3), as in the case of prime twins. I see no prospect of answering (1)
for the 1000-gap except by prohibitive calculation, but offer below
specimen solutions for (2) and (3), and in some sense "the" solution to
(4) for my own machine and software.
I have bowed to the majority and adopted the "even gap" notation,
although Shanks, in his 1964 paper referred to by Weintraub and Wolf,
and Kelly used the odd gap notation. I find it disturbing to have a
gap of 1 between 2 and 3 when there is obviously nothing there; on the
other hand it makes for easier programming to have p and p+g, rather than
p and p+g+1. Perhaps one might complement the infinite prime by a "finite
composite" which lurks between any two different integers, but disappears
by an uncertainty principle if one attempts to observe it.
So far as I can recall the first solution to (2) and (3) together
was given on these screens by Pam Cutter, and Sol Weintraub's more
recent posting was a new solution to (2).
A New Solution to (2) (Smallest known gap of 1000)
The lower prime is:
1045 30915 19339 74876 88717 01343
This was found as a byproduct of the program RUFHEW as follows. Following
the technique of Dubner and Nelson, one finds M=2.3.5.7...p and R so
that of the numbers R+1, R+2, ...,R +850(say) as many as possible have
a factor in common with M(the D/N greedy algorithm does very well). One
then sieves and tests M*L+R for varying L to make M*L+R+r composite
for 1.le.r.le.850, completing the "rough-hew". We now go backwards from
M*L+R and forwards from M*L+R+851 until primes p1 and p2 are reached;
this gives a gap of p2-p1, and there is no reason why divinity should not
shape our two ends so that p2-p1=1000 sometimes( if one's thoughts are
Federally supported, divinity should perhaps be replaced by fate or
chance, to avoid lawsuits). The same technique can be used to
produce relatively large gaps; the gap of 1160 at
7841 77821 04546 94410 59173
has (upper-lower)/log(lower)= 20.99
General-purpose primality proving is here so fast that its
time can be ignored.
A New Solution to (3) (Largest known gap of 1000)
The lower prime is (1019 digits)
3679 60741 47966 50028
40049 31002 54529 26688 00820 05378 69762 49184 76794 36650
74307 18606 26818 35932 10233 55252 89069 41179 65898 98391
92980 92526 64823 69210 10268 78802 05471 24115 88660 88211
08082 67108 73324 56172 32061 06655 30174 09031 38087 51203
06428 30345 65811 67699 01106 61756 91061 50232 57434 55776
14681 74790 50760 17190 09529 26615 20991 32373 99809 80987
54912 11586 88319 99088 05619 77427 07258 61453 37100 54223
91308 02645 89506 81653 12546 24073 15451 96965 07701 63714
73382 96250 97839 20485 11662 05368 27686 73392 00519 24384
37616 44775 88892 65562 66213 05212 88939 16963 52737 63845
05372 23823 11338 37577 81745 99210 49843 64625 56799 17789
63477 41071 50170 75921 95446 17802 28204 88185 02997 24672
34053 90693 91438 81167 41106 15021 65032 08573 36136 00631
27651 58366 05496 97857 14430 68590 72523 99913 38687 39798
20266 18211 88782 36309 86319 67753 44864 57042 22371 61119
10169 51352 69907 31806 52248 02083 07017 49602 72733 68120
83354 15764 61757 95915 38686 09487 19350 81777 14110 55967
27678 24484 84286 38467 18641 69340 73267 54246 80952 59035
07078 66729 06323 38130 81838 02958 44165 33087 74334 35584
97373 52740 86626 49865 95047 55202 29858 52968 92277 55521
This is of course pathetically small by -plet standards; Tony Forbes
has larger prime TRIPLETS, and the prime twin record is 11713 digits.
Here the method is classical(= over 20 years old in this subject); for
size N one makes the lower prime congruent to 1 modulo 2^m, and the upper
prime congruent to 1 modulo (say) P=5.7.11...(omit 37)..., where 2^m is
about N^(2/3) and P is about N^(1/3). Both primes are now BLS-provable
(see below), and almost all the testing time is spent on the lower
prime which enjoys a fast reduction algorithm on a binary machine. One can
effectively ignore the intermediate numbers; if the ends are prime, it
would be most unlucky to find another prime in between at this size. And
if so, try again. The specimen above took a few hours to find.
A Solution to (4) (Best Buy)
This is slightly more interesting. Again following Dubner and Nelson
we now consider a parameter p, and write M=2.3.5.7...p. Using the
greedy algorithm we find R so that R and R+1000 are prime to M, while
as many as possible of the numbers R+r(1.le.r.le.999) have (R+r,M).gt.1.
One then prescribes some sieve-and-test strategy to find M*L+R and
M*L+R+1000 as consecutive primes, and estimates the expected time to
find the smallest viable L, using the prime number theorem and look-up
tables of (i)the cost of a pseudoprime test at size M*100000(say) and
(ii) the cost of an ECPP proof of primality at that size.
By this method I found the 93-digit specimen
178 28825 70838 34017 72253 49467 40063 75777 59483
73301 76330 26649 76872 61299 20336 92347 32504 07196 47521
in 11.7 seconds; two formal proofs of primality took another 6 seconds.
This was not especially lucky; I later did a 90-minute run and
found 482 specimens of gap 1000 with the lower prime between 92 and
99 digits. These were guaranteed prime by my test (13) but not formally
proved; formal proof should again take about 6 seconds per pair.
Some further single gaps.
As one looks for any specimen at all of gaps 2000, 3000, ...,10000(say),
the competition between opposing needs becomes more intense. For primes
of size N one has at one's disposal small auxiliary primes whose
product is N. These have two tasks: to maximize the number of forced
composites, and (when N is "large")to help the primality PROOFs. The
latter is very restrictive, even with BLS-revisited (see below), and
increases the size of N(and thus the time) for a given gap. For a gap
of 5000 I found a 356-digit specimen using the technique of (4) above
which was not BLS-provable; it took longer to find the following
459-digit specimen:
2102 81892
42238 20892 17507 02199 94373 54584 05735 79071 50776 38597
84420 20411 01351 56545 39645 79902 40116 64599 27189 72858
80186 26541 75169 52751 46108 61722 76891 15280 65218 61701
50782 72597 57768 15835 03957 91060 68161 22894 16536 83505
77032 26650 88716 22419 40774 66469 32429 42850 37153 56409
81748 98223 10281 08451 41954 80462 80091 51843 65337 14083
85122 21608 18744 62787 89518 72878 31663 29866 55248 08468
60077 86723 92406 74155 94526 16921 40261 13506 00795 13329
49121 33614 52427 30450 82057 17059 24295 53543 10949 82001
One of the two primes is BLS-provable; the other needs one of the two
BLS-extended theorems below.
I have an unproved 559-digit specimen for gap 10000, which may as
well be suppressed.
Successive gaps.
I shall refer to the triplet p,p+2,p+6 as (0,2,4) .
The most interesting case in some ways is that of two successive gaps;
for the three primes to be BLS-provable we must use all our auxiliary
primes on them. Despite this, the greedy algorithm does do considerably
better on the composites than merely ignoring them. Once we have more than
three primes to consider, we may as well revert to general-purpose
primality proving all round, and use the auxiliary primes solely to
help out the composites. The current program accepts any series of
consecutive gaps, and predicts a total time for one success. A few
specimens follow: the series of successive gaps followed by the lowest
prime followed by three asterisks.
(1002, 1002)
10936 90982
32549 97981 35307 78166 89598 32401 59475 18448 95962 71147
54873 38796 29940 67156 98363 84999 27243 20996 21536 18049
* * *
(1002, 1002, 1002)
1 06266 86018 14197 60134 44219 49253 26838
58349 02649 87245 37249 51747 08834 11605 35026 44346 53262
11685 34510 33515 84235 81354 86139 51854 98704 07248 40800
36369 69203 71199 88899 06571 09388 50377 39320 57896 55977
* * *
(1000, 2, 1000, 2)
7925 08593 11874 06037 34567 25361 21594 13744 40375 11770 17547
71568 59571 07198 91504 77737 91482 91442 29659 01814 07279
* * *
( 100, 200, 300, 400)
3 94781 56218
12659 94963 93437 81912 00531 70947 58470 65365 33727 56541
* * *
(2, 700, 2, 700, 2)
61581 50471 14598 80795 51930
70651 63316 39649 59361 50669 68508 81419 46516 12880 45127
* * *
(2, 598, 2, 598, 2)
37 79323 10668
55145 42796 08510 17279 11444 16000 09876 88246 38974 32251
* * *
Obviously I would have liked to get (2, 1000, 2, 1000, 2) but
Old Faithful refused this jump with an expected time of about 30 hours.
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
Brillhart, Lehmer, and Selfridge, Revisited
by
A.O.L.Atkin
(April 22nd, May 5th, June 3rd, 1997)
Reference: John Brillhart, D.H. Lehmer, and J.L. Selfridge,
New Primality Criteria & Factorizations of 2^n +/-1,
Math. Comp. 29(1975)620-647, (hereafter BLS).
Notation: we write throughout N-1=F1*R1 and N+1=F2*R2, where
N is uneven, F1 and F2 are products of known primes, and
gcd(F1*F2, R1*R2)=1.
Playing the current "Gap" games on NMBRTHRY I was led to the
extensions and variants of BLS described below. The applications
are somewhat factitious, the most plausible one being to find
two successive prescribed gaps of moderate size without spending
a disproportionate amount of time on the proofs of primality.
Following the ideas of Dubner and Nelson, one starts with some
choice of prime P, and with M=2.3.5.7...P one then seeks R(mod M)
such that R,R+gap1,R+gap1+gap2, are all prime to M, while of the
other n in R.lt.n.lt.R+gap1+gap2 as many as possible have
(n,M).gt.1. The greedy algorithm used by Dubner and Nelson
(start at 2, and work upwards along the prime list; for each p
there are three prohibited residues; choose among the others the
"first" one which maximizes the number of new composites)works very well.
However, we may be using numbers of a size where the general-purpose
prime-proving algorithms are expensive or even impracticable.
Thus restricting most of the residues to the six choices
+/-1,+/-gap1,+/-(gap1+gap2), modulo p, while it is less efficient in
maximizing the number of composites, tends with reasonable luck to
produce putative primes N where the product F1*F2 is approximately
equal to cuberoot(N). (The program continues with a sieve and test on
M*L+R+(0,gap1, gap1+gap2) for varying L).
BLS is one of the fundamental papers of the subject, both
as to its new theorems, and as to its codification of then existing
material. (However, I personally find that Lucas sequences are more
perspicuous as extensions of rings, and prefer to use elements of
norm 1). I have to confess that at the time I was content to
program only their Theorems 7 and 19, and when I came to the
"Combined Theorems" in Section 7 I skipped to the more exciting
"Numerical Results" in Section 8. Thus I had never really looked
carefully at their Theorem 20.
When I finally did so this April I was horrified to find that
F1*F2 = (approximately) cuberoot(N) is NOT enough, and that was
what my program had assumed. However "Where the head has gone, the
hindquarters are bound to follow", as in the Chinese proverb, and
I fell back on some results I found 12 years ago, but which immed-
iately became obsolete for general purposes with the invention of
ECPP(cf. A.O.L. Atkin and F. Morain, Math. Comp. 61(1993),29-67).
This mild injection of elliptic curves(described in Section 2
below) can somewhat improve BLS, especially when F1 and F2 are
about equal(and each equal to about N^(1/6)). In the process of
writing the program I was surprised to realize that Theorem 20
itself can also be improved using their own techniques; this is in
Section 1.1 below.
1. With N-1=F1*R1 and N+1=F2*R2 as above, we now suppose that
R1 and R2 have no factors less than a bound B. Define
F12=F1*F2/2. Then BLS shows that one can probably prove N prime
(note the position of the adverb) if any of the following
exceed N (I give order of magnitude rather than exact detail):
B'*B^2*F12^2 ; B*F1^3 ; B*F2^3 ; B^3*F1^2*F2 ; B^3*F2^2*F1 ;
(for judicious constants B and B', perhaps about 10^7) .
I show that, with a little help from elliptic curves, one can in
many cases do better than this. Specifically, one can probably
prove N prime if
min(B'^3*F1^3*F2^3,B''*F1*F2^5). ge . N. (1000)
1.1 First, it seems to me that their Theorem 20 is disappointingly
weak, and that by using their own technique in Theorems 7 and 19
one can do better as follows. Suppose that all prime factors of N
are congruent to 1 modulo F1*u1, and to +/-1 modulo F2*u2, where
u1 divides R1, u2 divides R2, and both u1 and u2 are greater than B.
(This is what comes out of BLS, but I have not managed to take
advantage of the "unknown primes" u1 and u2 in what follows.)
Suppose also that F12*x +N0 does not divide N for x.lt.B1, where
N0 with 1.lt.N0.lt.F12 is congruent to N modulo F12.
(Note that F12*y+1 can divide N only if y.gt.B^2. As a matter
of practical politics one may assume that B1.lt.B^2, even though with
quadratic sieving it should not take too long to get B1 around 10^9.
This assumes that enough square roots are established: see Sec. 1.2.)
First, if B^2*B1*F12^2.gt. N, then N is clearly prime.
Next, if (B1*F12)^3.gt.N and B^4*B1*F12^3.gt.N (Conditions AA)
then N can have at most two prime factors.
Suppose that these are (a*F12 + 1)*(b*F1 +1). Then
(N-1)/F1 = a*b*F12 + (b+ a*F2/2). (1100)
Now divide (N-1)/F1 by F12 to obtain
(N-1)/F1 = q*F12 +r, where 0.lt.r.lt.F12,
so that for some non-negative z we have
b+a*F2/2=r+z*F12, and a*b=q-z.
Suppose now that for all values of z with 0.le.z.le.B3-1
we have proved that (r+z*F12)^2 -2*F2*(q-z) is not a perfect square.
( This is an easy 'quadratic' sieve without side condition, and the
primes dividing F1 can be used: B3=10^9 is quite feasible. )
Then we know that (b+a*F2/2).ge.B3*F12 + r.
Also with B2= min(B^2,B1) we have
(a*F2/2-B2*F2/2)*(b-B2*F2/2).ge.0, whence
a*b*F2/2.ge. (a*F2/2+b)*B2*F2/2-B2^2*F2^2/4.
Combining this with (1100) above and simplifying yields
N.ge. (B2*F12+1)*(F1*F12*B3-B2*F12+1),
so that N is prime if this condition is not satisfied, i.e.,
N is prime if
N.lt.(B2*F12+1)*(F1*F12*B3-B2*F12+1), (Condition BB1).
This condition almost surely implies Conditions AA, and
(apart from constants) allows F1^3*F2^2 to have the order of
magnitude of N, as compared with F1^2*F2^2 in BLS Theorem 20.
1.1.1. We may pursue a precisely similar argument writing the
factorization of N as
N= (a*F12 + 1)*(c*F2 -1 ).
Then (N+1)/F2= a*c*F12 + (c-a*F1/2), and
(N+1)/F2= Q*F12 + R, with 0.le.R.lt.F12,
and for all w with 0.le.abs(w).le.B4 +1 we have proved
that (R+w*F12)^2 +2*F1*(Q-w) is not a perfect square.
This leads to N.le.F12^2*F2*B4*B2 ( Condition BB2)
I cannot see how to combine these, although of course
b*F1+1=c*F2-1.
1.2. Next we note a principle implicit in BLS, though not formally
stated there.
Let p be any prime divisor of N, and let q be a (usually small) prime
with which we have ACTUALLY COMPUTED. Then p is either
(i) a 1-prime, for which (q/p)=1 for all q ,
or (ii)an N-prime, for which (q/p)=(q/N) for all q.
For whenever we have (q/N)=1 and find sqrt(q), we must have (q/p)=1.
If we use two primes (q1/N)=-1 and (q2/N)=-1, then the ACTUAL
CALCULATION of sqrt(q1*q2) is needed to justify (ii).
(If q1 is the first, we find this for each new q2). Our goal is to show
that there are no 1-primes and only one N-prime.
2.0. Assume that we have found a curve modulo N with complex multipli-
cation by -D, where (-D/N)=-1, so that the number of points is (N+1).
Note that one is not confined to class number one, or
even h/g=1, and that there are many precalculated square roots about,
so that finding a value of j should be reasonably easy. Suppose also
that F2 is greater than 2, i.e., that we are not so unlucky as to have
N+1=2*(unknown) . Find (as usual) a point P on our curve y^2=x^3+Ax +B,
and a point P' on -Dy^2=x^3 +Ax +B. Let d be any prime factor of F2
(including the prime 4), and by exponentiation ,repeated if necessary,
find points Q and Q' of order d on E and E' respectively.
Now suppose that p divides N, and (-D/p)=1. Then the reductions
of E and E' modulo p are the same curve, with a canonical isomorphism
x=x', y=cy', where c^2=-D (mod p). Being points of prime order
(ignoring fuss if d^2 divides N+1, or d=4) one is a multiple of the
other, and so not by baby-giant we solve the discrete logarithm problem
in time d, obtaining two values of y (mod N) whose ratio r
is a square root of -D mod p. Thus gcd(N,r^2+D) yields the factor p
(or of course, and most probably, gcd(x-x',N) yields p.)
If(as expected) there is no match, that proves the non-existence of
p, i.e.: There are no 1-primes. Or so I thought for about 24 hours
in early May, 1997.
UNFORTUNATELY the argument breaks down if the d-Sylow part of the
group on the curve modulo p has rank 2. As a consolation prize, any
prime occurring in F2 must appear at least squared in the number of
points modulo p. But we can achieve this much, and more, by another
argument.
2.1. Use of Complex Multiplication with (-D/N)=-1.
Once again find a curve whose number of points is (N+1), and
establish as usual that (most of, unless one wants nasty fuss with
non-first-power divisors)F2 divides the number of points modulo p,
where p is any 1-prime.
(As in BLS, we have already shown, or will show,that F2 and F1 divide
(p-1)).
The we have 4p= a^2 + D*b^2 ,
4(p+1+a)= (a+2)^2 +D*b*2 ,
4(p+1-a)= (a-2)^2 + D*b^2 ,
4(p-1) = (a-2)*(a+2) + D*b^2 .
W.l.o.g. assume that (most of)F2 divides (p+1+a). Then F2 also divides
(a+2)=p+1+a - (p-1), and so F2 divides D*b^2. Hence (most of)F2^2
divides D*b^2 and (a+2)^2, and so (most of)F2^2 divides (p+1+a).
Repeat this argument(and, alas, the work) for a different D'. Then
a' cannot equal a, else D*b^2=D'*b'^2 , so that F2^2 divides (a-a'),
which is less than 4*sqrt(p). Hence p.gt. F2^4 / 16.
Note that we can get (quite cheaply) the BLS-type "unknown" prime
u.gt.B, the sieving bound on (N+/-1). Thus using only one D gives
p.gt. B*F2^2 . At much greater expense( using (log(N/F2)/log(B)) values
of D) we can guarantee that two unknown primes are equal; in this case we
have p.gt. B^2*F2^4/ 16 . Let us summarize this with a bad constant
K for which
p.gt.K*F2^4.
This does not appear to help the argument in Sec. 1.1.
However it does help the gross two-factor argument:
If N.lt. (K*B2/2)*F1*F2^5, (Condition CC)
AND B2*F12.ge. cuberoot(N), (Condition AA rewritten)
then N is prime. (2100)
The loss of constant size in the CM-argument is sufficiently serious
to make this theorem no better than Section 1 if N is small(less than
100 digits), and of course all these results are ineffective for
general-purpose primality proving if N exceeds(say) 150 digits.
However, for very large N with F1 about equal to F2(and so about
N^(1/6)) they are valuable; it turns out that this case does arise
with the artifical primes used in constructing specific prime gaps.
2.2. Use of Complex Multiplication with (-D/N)=1.
With 4*N = A^2 + D*C^2, and two curves with 4*numbers of points:
4*(N+1+ A)= (A+2)^2 +D*C^2 = 4*F3*R3 , and
4*(N+1- A)= (A-2)^2 +D*C^2 = 4*F4*R4,
where F3 and F4 are products of small primes, and R3 and R4 have no
prime factor less than a bound B. All primes p dividing N have (-D/p)=1,
and so the reductions of the two curves modulo p have 4*## of points
4*(p+1+a) = (a+2)^2 +D*b^2 and
4*(p+1-a) = (a-2)^2 +D*b^2,
where 4*p = a^2 +D*b^2.
(Note that p is in the principal class for -D since the CM-curve is
defined mod p).
And as before (p-1) is divisible by F1*F2*u1*u2, where u are
unknown primes greater than B. The usual techniques should now give
(p+1+a) =F3*r3, where some u3 divides r3, and
(p+1-a) =F4*r4, where some u4 divides r4;
u3 divides N+1+A, u4 divides N+1-A; both are greater than B.
Trivially we have p.gt.(B-1)*F3 and p.gt.(B-1)*F4. These are
unlikely to be effective, so we try to combine the information.
We have 2a/(F3*r4) =r3/r4 -F4/F3. Suppose that r3/r4 is
NOT a convergent to the continued fraction of F4/F3; this is easily
checked in logarithmic time. Then 2*abs(a)/(F3*r4).ge. 1/(2*r4^2),
whence 4*sqrt(p).ge.F3/(2*r4), or approximately, since r4*F4~p:
p.ge. (F3*F4)^(2/3)/4. . . . . . . . . . . .
This is not very powerful. One does not use the fact that F3 and F4
come from the "same" -D; any pair can be used, and any F3 can be
used with F4=F1*F2 coming from the p-1 congruence.
Even so, it is very hard to beat the known p.gt. B^2*F1*F2 unless
one gets a fortuitously large F3 and F4.