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" 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.