Primality testing Phi(15091,58729) [N-1, Brillhart-Lehmer-Selfridge] Running N-1 test using base 2 Running N-1 test using base 3 Calling Brillhart-Lehmer-Selfridge with factored part 27.11% Phi(15091,58729) is PRP! (708.1480s+0.0008s)

realprecision = 28012 significant digits (28000 digits displayed) Welcome to the CHG primality prover! ------------------------------------ Input file is: 58729_15091.in Certificate file is: 58729_15091.out Found values of n, F and G. Number to be tested has 71962 digits. Modulus has 19510 digits. Modulus is 27.110156929573823956% of n. NOTICE: This program assumes that n has passed a BLS PRP-test with n, F, and G as given. If not, then any results will be invalid! Square test passed for F >> G. Using modified right endpoint. Search for factors congruent to 1. Running CHG with h = 12, u = 5. Right endpoint has 13436 digits. Done! Time elapsed: 4225491ms. Running CHG with h = 12, u = 5. Right endpoint has 13245 digits. Done! Time elapsed: 4930893ms. Running CHG with h = 12, u = 5. Right endpoint has 13016 digits. Done! Time elapsed: 4527312ms. Running CHG with h = 12, u = 5. Right endpoint has 12778 digits. Done! Time elapsed: 21197217ms. Running CHG with h = 12, u = 5. Right endpoint has 12538 digits. Done! Time elapsed: 30390084ms. Running CHG with h = 11, u = 4. Right endpoint has 12273 digits. Done! Time elapsed: 557686ms. Running CHG with h = 11, u = 4. Right endpoint has 12184 digits. Done! Time elapsed: 677815ms. Running CHG with h = 11, u = 4. Right endpoint has 12076 digits. Done! Time elapsed: 582520ms. Running CHG with h = 11, u = 4. Right endpoint has 11941 digits. Done! Time elapsed: 1576079ms. Running CHG with h = 11, u = 4. Right endpoint has 11772 digits. Done! Time elapsed: 660918ms. Running CHG with h = 11, u = 4. Right endpoint has 11555 digits. Done! Time elapsed: 2282888ms. Running CHG with h = 11, u = 4. Right endpoint has 11290 digits. Done! Time elapsed: 4610192ms. Running CHG with h = 11, u = 4. Right endpoint has 10959 digits. Done! Time elapsed: 25951851ms. Running CHG with h = 11, u = 4. Right endpoint has 10544 digits. Done! Time elapsed: 6946961ms. Running CHG with h = 9, u = 3. Right endpoint has 10027 digits. Done! Time elapsed: 1021963ms. Running CHG with h = 9, u = 3. Right endpoint has 9851 digits. Done! Time elapsed: 1185731ms. Running CHG with h = 9, u = 3. Right endpoint has 9618 digits. Done! Time elapsed: 2959500ms. Running CHG with h = 9, u = 3. Right endpoint has 9306 digits. Done! Time elapsed: 1529306ms. Running CHG with h = 9, u = 3. Right endpoint has 8890 digits. Done! Time elapsed: 2471625ms. Running CHG with h = 9, u = 3. Right endpoint has 8336 digits. Done! Time elapsed: 3313780ms. Running CHG with h = 7, u = 2. Right endpoint has 7598 digits. Done! Time elapsed: 109873ms. Running CHG with h = 7, u = 2. Right endpoint has 7245 digits. Done! Time elapsed: 164172ms. Running CHG with h = 7, u = 2. Right endpoint has 6750 digits. Done! Time elapsed: 212677ms. Running CHG with h = 7, u = 2. Right endpoint has 5684 digits. Done! Time elapsed: 418734ms. Running CHG with h = 5, u = 1. Right endpoint has 4333 digits. Done! Time elapsed: 29826ms. Running CHG with h = 5, u = 1. Right endpoint has 1813 digits. Done! Time elapsed: 46447ms. A certificate has been saved to the file: 58729_15091.out Running David Broadhurst's verifier on the saved certificate... Testing a PRP called "58729_15091.in". Pol[1, 1] with [h, u]=[5, 1] has ratio=1.0134288945207137034 E-1492 at X, ratio=1.9336739991304621642 E-3304 at Y, witness=2. Pol[2, 1] with [h, u]=[4, 1] has ratio=0.9905223921630433171 at X, ratio=2.628753592120217809 E-2520 at Y, witness=17. Pol[3, 1] with [h, u]=[7, 2] has ratio=4.918323052208643000 E-14 at X, ratio=9.546243236195060029 E-2704 at Y, witness=11. Pol[4, 1] with [h, u]=[7, 2] has ratio=1.0000000000000000000 at X, ratio=1.0555632480974689792 E-2131 at Y, witness=2. Pol[5, 1] with [h, u]=[7, 2] has ratio=0.22996920903704090786 at X, ratio=2.167302784231128993 E-991 at Y, witness=7. Pol[6, 1] with [h, u]=[7, 2] has ratio=1.9425517191319906974 E-353 at X, ratio=3.773507181502652473 E-706 at Y, witness=2. Pol[7, 1] with [h, u]=[9, 3] has ratio=0.3132381427483303126 at X, ratio=8.968748868560502876 E-2217 at Y, witness=5. Pol[8, 1] with [h, u]=[9, 3] has ratio=0.2628395406272610382 at X, ratio=9.496915232904930856 E-1663 at Y, witness=23. Pol[9, 1] with [h, u]=[9, 3] has ratio=0.14443748489151425192 at X, ratio=2.6984045950437693532 E-1247 at Y, witness=5. Pol[10, 1] with [h, u]=[9, 3] has ratio=0.024056063875887052616 at X, ratio=1.1220907851245453900 E-935 at Y, witness=2. Pol[11, 1] with [h, u]=[9, 3] has ratio=0.3052823612612857144 at X, ratio=7.384724839947875764 E-702 at Y, witness=5. Pol[12, 1] with [h, u]=[9, 3] has ratio=0.19029304720902164672 at X, ratio=1.3459586941579866787 E-526 at Y, witness=2. Pol[13, 1] with [h, u]=[11, 4] has ratio=0.7988632455445099680 at X, ratio=2.705106191577981777 E-2072 at Y, witness=3. Pol[14, 1] with [h, u]=[11, 4] has ratio=0.5879683733948107924 at X, ratio=5.729182302094451322 E-1658 at Y, witness=7. Pol[15, 1] with [h, u]=[11, 4] has ratio=0.20157952745575956748 at X, ratio=1.5662164538413438264 E-1326 at Y, witness=3. Pol[16, 1] with [h, u]=[11, 4] has ratio=0.03799087820589632892 at X, ratio=2.4037707347372343734 E-1061 at Y, witness=5. Pol[17, 1] with [h, u]=[11, 4] has ratio=6.805870978374302317 E-294 at X, ratio=5.834854748410778662 E-866 at Y, witness=7. Pol[18, 1] with [h, u]=[11, 4] has ratio=0.3855146123056651324 at X, ratio=3.531470981941500048 E-676 at Y, witness=3. Pol[19, 1] with [h, u]=[11, 4] has ratio=0.09645573635074524173 at X, ratio=3.946236461991331100 E-541 at Y, witness=11. Pol[20, 1] with [h, u]=[11, 4] has ratio=0.13115773044762876517 at X, ratio=4.269430608888790155 E-433 at Y, witness=2. Pol[21, 1] with [h, u]=[11, 4] has ratio=0.021979810579158670382 at X, ratio=1.5671279474018330450 E-358 at Y, witness=5. Pol[22, 1] with [h, u]=[12, 5] has ratio=0.11311345155551398115 at X, ratio=4.612269058078487522 E-1324 at Y, witness=2. Pol[23, 1] with [h, u]=[12, 5] has ratio=0.15487399087798378634 at X, ratio=1.0309235804377548964 E-1203 at Y, witness=7. Pol[24, 1] with [h, u]=[12, 5] has ratio=0.04822323993144247014 at X, ratio=7.638143747645795296 E-1189 at Y, witness=5. Pol[25, 1] with [h, u]=[12, 5] has ratio=2.918519001546996623 E-230 at X, ratio=2.4379408198280995110 E-1145 at Y, witness=7. Pol[26, 1] with [h, u]=[12, 5] has ratio=2.5170225595087714496 E-192 at X, ratio=1.4571031045286548121 E-954 at Y, witness=19. Validated in 15 sec. Congratulations! n is prime! Goodbye!A copy of the CHG certificate

`58729_15091.out`

(15MB) is
included in:
`58729_15091.zip`

.
Phi(7545,58729)/(15091*181081) 141518577057991884353412556550774050081 54944547510003975367411457 38969436819363236265199 31309680237291504724127 854537546718984134581 759623187152078440421 39068769655181209291 1174992195772806667 93812539342031 68994834745423 5976689212201 145207292471 417769669 299561651 116657773 61718101 30089461 21803081 606091 241441 214399 181081 138829 125221 28111 16087 15091 12073 7603 3019 839 601 281 211 67 61 37 31 19 11 7 5 5 3 2

`Phi(7545,58729)/(15091*181081)`

(19143 digits): `ecpp19143.zip`

Tom Wu Last modified: Sat Feb 4 10:00:00 PDT 2017