Thread: Primes found! View Single Post
2015-02-28, 09:24   #16
paulunderwood

Sep 2002
Database er0rr

393410 Posts

Quote:
 Originally Posted by Batalov Because there was a ton of them, and even more with >29% (which I didn't submit). The comment there says it all (they are a dataset for anyone who wants to learn CHG in practice).
Testing the one I indicated above:-

Factoring N-1:
Code:
 ./pfgw64 -o -f1000 -q"(10^46877-2*10^12568-2)/(2*3*6449*138176897)"
PFGW Version 3.7.7.64BIT.20130722.x86_Dev [GWNUM 27.11]

Factoring numbers to 1000% of normal.

(10^46877-2*10^12568-2)/(2*3*6449*138176897) has no small factor.
Factoring N+1:
Code:
./pfgw64 -o -f1000 -q"5*10^34308-1"
PFGW Version 3.7.7.64BIT.20130722.x86_Dev [GWNUM 27.11]

Factoring numbers to 1000% of normal.

5*10^34308-1 has no small factor.
Helper file chg_helper.6:
Code:
2
3
6449
138176897
2
10^12568
BLS test:
Code:
 ./pfgw64 -tc -hchg_helper.6 -q"10^46877-2*10^12568-1"
PFGW Version 3.7.7.64BIT.20130722.x86_Dev [GWNUM 27.11]

Primality testing 10^46877-2*10^12568-1 [N-1/N+1, Brillhart-Lehmer-Selfridge]
Reading factors from helper file chg_helper.6
Running N-1 test using base 3
Running N+1 test using discriminant 17, base 1+sqrt(17)
10^46877-2*10^12568-1 is Fermat and Lucas PRP! (265.8579s+0.0002s)
File 6.in:
Code:
n=10^46877-2*10^12568-1;
F=2*3*6449*138176897;
G=2*10^12568;
CHG.GP script alterations:-

Code:
allocatemem(128*1024*1024);   \\ Increase stack to 64mb for now
\\ You may have to bump this up to 128M for really
\\ big values of h (say bigger than 12).
Code:
\p28000
(Perhaps a tad too high.)
Code:
worktodofile="TestSuite\/6.in";
certificatefile="TestSuite\/6.out";
Code:
maxh = 20;
Script run:
Code:
 gp < CHG.GP
Reading GPRC: /etc/gprc ...Done.

GP/PARI CALCULATOR Version 2.5.1 (released)
amd64 running linux (x86-64/GMP-5.0.5 kernel) 64-bit version
compiled: Jun  4 2012, gcc-4.7.0 (Debian 4.7.0-11)
(readline v6.2 disabled, extended help enabled)

Copyright (C) 2000-2011 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and comes
WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.

parisize = 8000000, primelimit = 500509
***   Warning: new stack size = 134217728 (128.000 Mbytes).
realprecision = 28012 significant digits (28000 digits displayed)

Welcome to the CHG primality prover!
------------------------------------

Input file is:  TestSuite/6.in
Certificate file is:  TestSuite/6.out
Found values of n, F and G.
Number to be tested has 46877 digits.
Modulus has 12581 digits.
Modulus is 26.837741491697310904% 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 G >> F.  Using modified right endpoint.

Search for factors congruent to 1.
Running CHG with h = 14, u = 6. Right endpoint has 9148 digits.
Done!  Time elapsed:  33937816ms.
Running CHG with h = 14, u = 6. Right endpoint has 8964 digits.
Done!  Time elapsed:  30500403ms.
Running CHG with h = 14, u = 6. Right endpoint has 8599 digits.
Done!  Time elapsed:  30873974ms.
Running CHG with h = 13, u = 5. Right endpoint has 8104 digits.
Done!  Time elapsed:  18542919ms.
Running CHG with h = 13, u = 5. Right endpoint has 7636 digits.
Done!  Time elapsed:  18322641ms.
Running CHG with h = 11, u = 4. Right endpoint has 6893 digits.
Done!  Time elapsed:  6854132ms.
Running CHG with h = 9, u = 3. Right endpoint has 6300 digits.
Done!  Time elapsed:  2077398ms.
Running CHG with h = 9, u = 3. Right endpoint has 5366 digits.
Done!  Time elapsed:  2016787ms.
Running CHG with h = 7, u = 2. Right endpoint has 4025 digits.
Done!  Time elapsed:  391320ms.

Search for factors congruent to n.
Running CHG with h = 14, u = 6. Right endpoint has 9148 digits.
Done!  Time elapsed:  34054669ms.
Running CHG with h = 14, u = 6. Right endpoint has 8964 digits.
Done!  Time elapsed:  31192117ms.
Running CHG with h = 14, u = 6. Right endpoint has 8599 digits.
Done!  Time elapsed:  31922984ms.
Running CHG with h = 13, u = 5. Right endpoint has 8104 digits.
Done!  Time elapsed:  19001912ms.
Running CHG with h = 13, u = 5. Right endpoint has 7636 digits.
Done!  Time elapsed:  18952632ms.
Running CHG with h = 11, u = 4. Right endpoint has 6893 digits.
Done!  Time elapsed:  7182281ms.
Running CHG with h = 9, u = 3. Right endpoint has 6301 digits.
Done!  Time elapsed:  2192084ms.
Running CHG with h = 9, u = 3. Right endpoint has 5366 digits.
Done!  Time elapsed:  2159538ms.
Running CHG with h = 7, u = 2. Right endpoint has 4026 digits.
Done!  Time elapsed:  422691ms.
A certificate has been saved to the file:  TestSuite/6.out

Running David Broadhurst's verifier on the saved certificate...

Testing a PRP called "TestSuite/6.in".

Pol[1, 1] with [h, u]=[7, 2] has ratio=1.4461419357427070131 E-6817 at X, ratio=5.664809224989919335 E-8988 at Y, witness=3.
Pol[2, 1] with [h, u]=[9, 3] has ratio=7.490470065658087023 E-2940 at X, ratio=6.390768475566896671 E-4023 at Y, witness=2.
Pol[3, 1] with [h, u]=[7, 3] has ratio=1.2972540577360267584 E-1584 at X, ratio=5.256884481953367877 E-2804 at Y, witness=6449.
Pol[4, 1] with [h, u]=[9, 4] has ratio=3.145579049895579619 E-593 at X, ratio=9.790444610593665637 E-2371 at Y, witness=3.
Pol[5, 1] with [h, u]=[10, 5] has ratio=1.0320034758398752235 E-2370 at X, ratio=1.2501766403362505471 E-3716 at Y, witness=3.
Pol[6, 1] with [h, u]=[12, 5] has ratio=7.216621710650853283 E-1552 at X, ratio=2.805395746440191462 E-2340 at Y, witness=3.
Pol[7, 1] with [h, u]=[13, 6] has ratio=5.619243606418243319 E-496 at X, ratio=3.1482351295087935110 E-2972 at Y, witness=6449.
Pol[8, 1] with [h, u]=[13, 6] has ratio=3.1482351295087935110 E-2972 at X, ratio=1.5689033180220872231 E-2191 at Y, witness=6449.
Pol[9, 1] with [h, u]=[14, 6] has ratio=1.6317340876422533882 E-1206 at X, ratio=2.4395522529325717148 E-1102 at Y, witness=3.
Pol[1, 2] with [h, u]=[7, 2] has ratio=1.6068243730474522369 E-6818 at X, ratio=1.9558887552173445350 E-8986 at Y, witness=17.
Pol[2, 2] with [h, u]=[9, 3] has ratio=1.0120641581575526988 E-2941 at X, ratio=9.415995163042182551 E-4022 at Y, witness=2.
Pol[3, 2] with [h, u]=[7, 3] has ratio=1.3268475765018631634 E-1584 at X, ratio=2.0407180404974932762 E-2803 at Y, witness=3.
Pol[4, 2] with [h, u]=[9, 4] has ratio=2.430901089616844084 E-593 at X, ratio=3.491959138889946426 E-2371 at Y, witness=3.
Pol[5, 2] with [h, u]=[10, 5] has ratio=3.680848125044162843 E-2371 at X, ratio=2.683030734698952763 E-3716 at Y, witness=3.
Pol[6, 2] with [h, u]=[12, 5] has ratio=2.7782166245229885464 E-1552 at X, ratio=2.2097959611499136744 E-2340 at Y, witness=3.
Pol[7, 2] with [h, u]=[13, 6] has ratio=5.111982063685797886 E-496 at X, ratio=1.7845796163124167244 E-2972 at Y, witness=3.
Pol[8, 2] with [h, u]=[13, 6] has ratio=1.7845796163124167244 E-2972 at X, ratio=7.384962616549326855 E-2191 at Y, witness=3.
Pol[9, 2] with [h, u]=[14, 6] has ratio=1.4706302622525914306 E-1206 at X, ratio=3.827727300991043488 E-1102 at Y, witness=23.

Validated in 6 sec.

Congratulations! n is prime!
Goodbye!
Note: For similarly sized candidates, the closer to a 12.5% factorisation of N^2-1, the longer a CHG test takes

Last fiddled with by paulunderwood on 2015-02-28 at 11:22 Reason: 25% of N^2-1 was the wrong thing to say!