20070504, 11:39  #1 
Feb 2003
3·5·127 Posts 
false composites with LLR
During my search for high weight k I found a severe problem with LLR:
At least for very small n (n<500) there is a chance for randomly generated "false composites". More or less by accident I'd rerun an input file which had already been tested by LLR. Just out of curiosity I counted the numbers of primes in both output files and found that the counts did not match. By comparing the lresults.txt files I found the following discrepancy: Code:
21375317535*2^471 is prime! Time : 0.811 ms. 21375317535*2^541 is not prime. LLR Res64: A1154AE6B7462DA9 Time : 0.684 ms. 21375317535*2^551 is not prime. LLR Res64: 9380000000066E07 Time : 1.509 ms. 21375317535*2^611 is prime! Time : 0.712 ms. Code:
21375317535*2^471 is prime! Time : 0.610 ms. 21375317535*2^541 is not prime. LLR Res64: A1154AE6B7462DA9 Time : 0.648 ms. 21375317535*2^551 is prime! Time : 0.669 ms. 21375317535*2^611 is prime! Time : 0.722 ms. Also note the "lots of zeros" pattern in the corresponding Res64 value. And there was another one: Code:
9934327416585*2^791 is not prime. RES64: 000000000038AACA. OLD64: 0000000000A A005D Time: 0.709 ms.  9934327416585*2^791 is a probable prime. Time: 0.686 ms. 9934327416585*2^791 is prime! Time : 0.804 ms. However, this time it seems that the false composites turn out completely ramdomly, and there is almost no chance to reproduce this phenomenon for a specific number. I dicided to prepare a large test bench containing 4,000,000 candidates (8000 k with n=1500, completely unsieved), which took less than two hours on my 2GHz Athlon. It yielded 235278 primes (and prp's) in the output file. Then I used that output file as input again for another LLR run. This time 43 of the former primes turned out as composites: Code:
666625245*2^451 is not prime. LLR Res64: 7C9B9FFFFFFFFFFE Time : 0.572 ms. 10446821385*2^511 is not prime. LLR Res64: CCF7FFFFFE5B0199 Time : 0.659 ms. 13947568635*2^61 is not prime. RES64: 000000AF3AD8BEFC. OLD64: 0000006E05093F73 Time: 0.460 ms. 17604081495*2^1511 is not prime. RES64: FFFFFFFFFE0C567F. OLD64: FFFFFFFFFA25037A Time: 0.879 ms. 29069604135*2^1091 is not prime. LLR Res64: FFFFFFFFFED169A6 Time : 0.806 ms. 30067977225*2^161 is not prime. RES64: 0002F51953756EB7. OLD64: 0001DF1B0E574C23 Time: 0.558 ms. 30832176375*2^1051 is not prime. RES64: 0000000000011D4B. OLD64: 00000000000357DE Time: 0.747 ms. 33711967575*2^211 is not prime. RES64: 00429AC4A46104EC. OLD64: 00C7D04DED230EC1 Time: 0.639 ms. 34449023895*2^171 is not prime. RES64: 000B7C0A0CBA0A9E. OLD64: 00025ED497D21FD9 Time: 0.566 ms. 38994969585*2^961 is not prime. LLR Res64: FFFFFFFFFE3CDC30 Time : 0.803 ms. 41855065395*2^501 is not prime. LLR Res64: 933FFFFFFF2DD810 Time : 0.634 ms. 49489163295*2^1091 is not prime. LLR Res64: FFFFFFFFFE9C8644 Time : 0.812 ms. 52690713075*2^1381 is not prime. LLR Res64: 0000000000537817 Time : 0.916 ms. 54574705185*2^681 is not prime. LLR Res64: 0000000000014259 Time : 0.738 ms. 58584259305*2^871 is not prime. RES64: FFFFFFFFFFDA76C4. OLD64: FFFFFFFFFF8F644B Time: 0.694 ms. 63346678395*2^791 is not prime. RES64: 0000000000022B6D. OLD64: 0000000000068246 Time: 0.682 ms. 73924325475*2^1091 is not prime. RES64: FFFFFFFFFF890320. OLD64: FFFFFFFFFE9B095E Time: 0.825 ms. 80621946405*2^721 is not prime. LLR Res64: 0000000000DA34B7 Time : 0.748 ms. 85597136625*2^1041 is not prime. LLR Res64: 0000000000019B0B Time : 0.821 ms. 85686205605*2^641 is not prime. LLR Res64: FFFFFFFFFFF32B0C Time : 0.752 ms. 87029734935*2^831 is not prime. LLR Res64: 0000000003288F4E Time : 0.767 ms. 97886532315*2^141 is not prime. RES64: 0002744E977511E9. OLD64: 0001AA4C49A875B9 Time: 0.559 ms. 99754874505*2^131 is not prime. RES64: 00023B171119AD55. OLD64: 0000E2CE8DAAC7FE Time: 0.546 ms. 104420708535*2^661 is not prime. RES64: FFFFFFFFFFFABC36. OLD64: FFFFFFFFFFF0349F Time: 0.660 ms. 110557596435*2^921 is not prime. RES64: FFFFFFFFFFFEC1C2. OLD64: FFFFFFFFFFFC4544 Time: 0.803 ms. 114971118405*2^861 is not prime. RES64: 00000000002640E5. OLD64: 000000000072C2AE Time: 0.723 ms. 118017194295*2^211 is not prime. RES64: 0234601C7FB1089C. OLD64: 032DD466583319D2 Time: 0.943 ms. 119183229165*2^111 is not prime. RES64: 00005DBAA3A6019E. OLD64: 00003B30ECEA9CD8 Time: 0.537 ms. 124751340285*2^401 is not prime. LLR Res64: B608B9000011A093 Time : 0.575 ms. 127464319125*2^401 is not prime. LLR Res64: 1F596D0000114087 Time : 0.684 ms. 130297851255*2^901 is not prime. RES64: FFFFFFFFFFFDE3F1. OLD64: FFFFFFFFFFF9ABD1 Time: 0.713 ms. 142982793525*2^391 is not prime. LLR Res64: C53D2280000F612F Time : 0.578 ms. 143902440825*2^11 is not prime. RES64: 000000146A84C1FE. OLD64: 0000003D3F8E45F7 Time: 1.085 ms. 149357253045*2^881 is not prime. LLR Res64: 00000000000EB926 Time : 0.794 ms. 183608570145*2^1241 is not prime. RES64: FFFFFFFFFFD017DF. OLD64: FFFFFFFFFF70479A Time: 0.798 ms. 242481123885*2^261 is not prime. RES64: 8849EAC8FFEDDCC1. OLD64: B709BF124BC99641 Time: 0.570 ms. 334983317955*2^71 is not prime. RES64: 0000083688CEFDFD. OLD64: 000018A39A6CF9F4 Time: 0.515 ms. 349610450475*2^141 is not prime. RES64: 0001E7B51664571F. OLD64: 0005B71F432D055A Time: 0.566 ms. 455843900655*2^21 is not prime. RES64: 00000102B0FBC89D. OLD64: 0000015F894BA619 Time: 0.469 ms. 513806395245*2^881 is not prime. RES64: 00000000000223D3. OLD64: 0000000000066B78 Time: 0.695 ms. 686256694695*2^791 is not prime. LLR Res64: FFFFFFFFF9975C43 Time : 0.782 ms. 692050343985*2^781 is not prime. LLR Res64: 00000000065AE795 Time : 0.797 ms. 1009734264825*2^261 is not prime. RES64: 9F0A1B1534045B0C. OLD64: 84577FFFD40D1123 Time: 0.592 ms. Note the occurrence of the "FFFFFF" residuals besides the "000000" ones. And there are some others which do not show these patterns. I repeated this retesting of the 235278 primes on several P4 machines too, using LLR 3.7.0 as well as 3.7.1. In each case it yielded about 4045 "false composites", but each of the sets is different. Having this in mind it wasn't a big surprise that checking the inial lresults.txt file for the occurrence of "000000" and "FFFFFF" revealed another 31 false composites. Since the input file containing the 4 million tests is too big to be posted here (about 65MB) I attached a list of the 8000 kvalues together with a perl script for generating the LLR input file: Code:
make_input.pl k_list.txt > input.txt The ZIP file contains a second perl script (prep_pari.pl) which can be use to generate an pari/gp input file to check whether a composite is prime or not. If you're running Linux then you may use something like the following for detecting false composites in the lresults.txt file: Code:
grep "FFFFFF" lresults.txt > bad_list.txt prep_pari.pl bad_list.txt > pari_input.txt gp < pari_input.txt > pari_output.txt Edit: Note, that a "000000" does not automatically mean a false composite. For small values of n (e.g. n<10) the residuals usually contain lots of zeros... Last fiddled with by Thomas11 on 20070504 at 11:49 
20070504, 12:33  #2 
Sep 2002
Database er0rr
2·1,723 Posts 
I am running the whole set of numbers generated by your Perl script. In the meantime here is one example:
From lresults.txt: 19030751025*2^1011 is not prime. RES64: 000000000039C689. OLD64: 0000000000AD539A Time: 0.803 ms. With PFGW: paul@pp4:~/pfgw$ ./pfgw_ver_12_linux q"19030751025*2^1011" tp PFGW Version 1.2.0 for Pentium and compatibles [FFT v23.8] Primality testing 19030751025*2^1011 [N+1, BrillhartLehmerSelfridge] Running N+1 test using discriminant 7, base 1+sqrt(7) Calling BrillhartLehmerSelfridge with factored part 74.81% 19030751025*2^1011 is prime! (0.0020s+0.0327s) Rerunning LLR: Starting Lucas Lehmer Riesel prime test of 19030751025*2^1011 Using General Mode (Rational Base) : Mersenne fftlen = 32, Used fftlen = 32 V1 = 5 ; Computing U0... V1 = 5 ; Computing U0...done. Starting LucasLehmer loop... 19030751025*2^1011 is prime! Time : 34.379 ms. Hopefully this does not affect the irrational base DWT calculations... Last fiddled with by paulunderwood on 20070504 at 12:37 
20070504, 14:36  #3  
Feb 2003
3·5·127 Posts 
Quote:
The set of false composites for the P4/Opteron(with SSE2) is the following: Code:
146110965*2^1191 is not prime. LLR Res64: FFFFFFFFFF8A6B45 Time : 1.443 ms. 2116838295*2^211 is not prime. RES64: 000CF7B82D4FC4B4. OLD64: 00075C0FA22F4E1B Time: 0.881 ms. 2532474945*2^591 is not prime. LLR Res64: A7FFFFFFFFFC9BAB Time : 1.268 ms. 8866861575*2^371 is not prime. LLR Res64: 5AB5279FF83FF665 Time : 1.067 ms. 10548249855*2^1141 is not prime. LLR Res64: 0000000000341E42 Time : 1.660 ms. 12744043455*2^251 is not prime. RES64: 021B0272489B9368. OLD64: 0061D1FF5BD2BA36 Time: 0.893 ms. 21344712675*2^701 is not prime. LLR Res64: FFFFFFFFFFFF31F3 Time : 1.325 ms. 21371962755*2^991 is not prime. LLR Res64: 0000000000CDC92A Time : 1.569 ms. 21440002155*2^171 is not prime. RES64: 0005756B4D665BC1. OLD64: 00066468F75D1341 Time: 0.877 ms. 27211257645*2^791 is not prime. LLR Res64: 00000000000A1A04 Time : 1.347 ms. 29645918445*2^421 is not prime. LLR Res64: 2AE34FFFFFF6BA5C Time : 1.219 ms. 34502279955*2^651 is not prime. LLR Res64: FFFFFFFFFFE021D8 Time : 1.316 ms. 34947161535*2^901 is not prime. LLR Res64: FFFFFFFFFFF8226C Time : 1.408 ms. 39393823755*2^251 is not prime. RES64: 080345FCC2DF493E. OLD64: 05B1B5DE329DDBB8 Time: 0.895 ms. 45056520795*2^161 is not prime. RES64: 00073EBD03E431B2. OLD64: 0000C10F26F69515 Time: 0.899 ms. 48672677625*2^311 is not prime. RES64: 492552100002D2E1. OLD64: 30E0E6B3800878A1 Time: 0.914 ms. 68626201215*2^81 is not prime. RES64: 00000D91D064CC4E. OLD64: 000008C08FB966E9 Time: 0.776 ms. 69257213025*2^891 is not prime. RES64: 00000000000FE033. OLD64: 00000000002FA097 Time: 1.127 ms. 83747979315*2^1641 is not prime. RES64: FFFFFFFF00000000. OLD64: FFFFFFFCFFFFFFFF Time: 1.487 ms. 86905921245*2^831 is not prime. LLR Res64: FFFFFFFFFE6B24E5 Time : 1.413 ms. 88749432915*2^641 is not prime. RES64: 00000000000C6392. OLD64: 0000000000252AB5 Time: 1.043 ms. 91938430155*2^1121 is not prime. LLR Res64: FFFFFFFFFFF40A70 Time : 1.592 ms. 93717793455*2^1171 is not prime. LLR Res64: 000000002EEDB9E5 Time : 1.675 ms. 98616136905*2^1291 is not prime. LLR Res64: 000000005931FD41 Time : 1.550 ms. 98848114365*2^381 is not prime. LLR Res64: 301918FFFFD381CC Time : 1.108 ms. 102467484405*2^911 is not prime. LLR Res64: 000000000001575E Time : 1.413 ms. 108581712525*2^661 is not prime. RES64: FFFFFFFFFFFD77EE. OLD64: FFFFFFFFFFF867C8 Time: 3.181 ms. 122169592545*2^241 is not prime. RES64: 165F95659F8FFF82. OLD64: 0A3B001B1CAFFE85 Time: 0.894 ms. 126360266175*2^41 is not prime. RES64: 0000018A8B93D371. OLD64: 000000F22DA6C272 Time: 0.749 ms. 136085318655*2^801 is not prime. LLR Res64: FFFFFFFFFFFF7EBA Time : 1.360 ms. 136129188195*2^511 is not prime. LLR Res64: 2168000000204ED1 Time : 1.216 ms. 136690749195*2^1031 is not prime. RES64: FFFFFFFFFFFEFE9A. OLD64: FFFFFFFFFFFCFBCB Time: 1.160 ms. 140303937345*2^691 is not prime. LLR Res64: 0000000003EB170F Time : 1.745 ms. 141673060815*2^891 is not prime. RES64: FFFFFFFFFFF83D36. OLD64: FFFFFFFFFFE8B79F Time: 1.128 ms. 249742686765*2^1151 is not prime. LLR Res64: 0000000023387AC0 Time : 1.479 ms. 279370430625*2^631 is not prime. LLR Res64: FFFFFFFFFFF041DE Time : 1.504 ms. 338164979295*2^571 is not prime. LLR Res64: 4800000003405C24 Time : 1.276 ms. 548433554955*2^311 is not prime. RES64: 853298E484027806. OLD64: DE67DCA28C076811 Time: 0.906 ms. 557484506865*2^61 is not prime. RES64: 000002A7AC26D473. OLD64: 000007F704747D56 Time: 0.812 ms. 650832937755*2^641 is not prime. LLR Res64: 00000000000360F7 Time : 1.363 ms. 845084472375*2^1371 is not prime. LLR Res64: 00000000000A6895 Time : 1.600 ms. 876707254995*2^601 is not prime. LLR Res64: A0000000001410F2 Time : 1.658 ms. 927436552185*2^121 is not prime. RES64: 000C3F5857708809. OLD64: 0009C0182F52781A Time: 0.870 ms. 1141813394865*2^211 is not prime. RES64: 170C0DD186168408. OLD64: 02ADD10526038C17 Time: 0.934 ms. Last fiddled with by Thomas11 on 20070504 at 14:43 

20070504, 14:46  #4  
Sep 2002
Database er0rr
2·1,723 Posts 
Quote:
Quote:


20070504, 14:56  #5 
Feb 2003
3×5×127 Posts 
All but the two nonprimes of Paul's list have been found on the Athlon in the initial LLR run (e.g. they haven't been "false composites" on the Athlon).
Obviously for the two nonprimes the "FFFFFF" pattern in the residuals is quite okay... Paul, what's your total number of primes in the output file (after the inital LLR run)? BTW.: On the Athlon I had "only" 13 "FFFFFF" false composites... Last fiddled with by Thomas11 on 20070504 at 14:59 
20070504, 16:41  #6  
P90 years forever!
Aug 2002
Yeehaw, FL
2·43·83 Posts 
Quote:
I have some QA code that randomly picks numbers 500+ bit numbers to test. I'll modify it to test some tiny numbers to see if the problem is in the gwnum library. 

20070504, 17:05  #7 
Nov 2003
2·1,811 Posts 
I just tested 44 numbers from message #1 (there are 44 of them, not 43) and LLR found them all to be either primes or PRPs (when k>2^n). This is an old version of 2004.12.26 which is still the best on my Athlon (no SSE2). results.txt is attached.
In 2004 me and the others from prover's code L97 tested LLR on primes and composites with known residues found by a script written by David Broadhurst in Pari. That version of LLR was later released as ver. 3.6 if I remember correctly. Are you using the latest version 3.7.1? Maybe these small numbers are not handled properly in the latest version? Even so, I beleive large numbers (like those in Top5000) are not affected. Edit: All false composites from message #3 also found by LLR to be either primes or PRPs. The two composites from message #4 found to be composites but that's correct (they are not primes, confiremed by pfgw). Last fiddled with by Kosmaj on 20070504 at 17:15 
20070504, 21:00  #8  
Feb 2003
3·5·127 Posts 
Quote:
So far it seems that both of the newer versions, LLR 3.7.0 and 3.7.1, are identical in that behaviour. BTW.: I count only 43 numbers in post #1 ... Last fiddled with by Thomas11 on 20070504 at 21:50 

20070504, 21:17  #9 
Feb 2003
3561_{8} Posts 
Attached is an input file which contains the first 15000 primes (or PRPs) from my initial Athlon run. Just put it to your machine and run it through LLR (should take about a minute or so). Then check the output for "not prime". Depending on your cpu type you will find the first few "false composites" given in posts #1 or #3.
Then run those "composite" numbers through pari or LLR again... Last fiddled with by Thomas11 on 20070504 at 21:18 
20070504, 21:41  #10 
Feb 2003
3·5·127 Posts 
I just used the input file given in my latest post for some quick checks on the following LLR versions: 3.3, 3.5, 3.6.2, 3.7, and 3.7.1
I found that 3.6.2 (and perhaps 3.6), 3.7, 3.7.1 are producing exactly the same "false composites" (identical Res64's). And it seems, that the earlier versions (e.g. 3.5) do not show any "is not prime" in the output! Back to LLR 3.5 ??? Last fiddled with by Thomas11 on 20070504 at 21:42 
20070504, 22:01  #11 
May 2005
2×809 Posts 
On one of my Core2Duo machines running WindowsXP I've got following false composites:
Code:
973197225*2^1591 is not prime. LLR Res64: FFFFFFFFFFDCB1A7 Time : 1.607 ms. 4985029335*2^241 is not prime. RES64: 01186BDFC6FF2370. OLD64: 00F70099A6FD6A4F Time: 1.006 ms. 6187790895*2^441 is not prime. LLR Res64: B619800000163618 Time : 1.400 ms. 7469291115*2^1151 is not prime. LLR Res64: 0000000000126689 Time : 1.532 ms. Running those 4 numbers alone through LLR reveals all af them to be primes... I really hope that this affects only some small values of n... which I test with PFGW anyway... Last fiddled with by Cruelty on 20070504 at 22:11 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Wieferich related composites  ZetaFlux  Factoring  3  20200309 08:55 
Factorising Mersenne composites  CuriousKit  PrimeNet  7  20151015 19:25 
PRPs that are composites  gd_barnes  Conjectures 'R Us  57  20110912 12:31 
What's the point of factoring known composites?  ixfd64  PrimeNet  4  20110221 11:51 
Primes and composites  mfgoode  Miscellaneous Math  12  20050705 19:19 