Certificate : For all indents and purposes

[pakaran]

Now caught up to 1200 digits (though both verification workers are busy with larger numbers). I am now working on the following:

1100000000804064323 	6106991767...83     1214
1100000000804080571 	(2^4423-2^4277*3-2)/30     1330
1100000000804065308 	2^4423-2^757*3-1                1332
1100000000804065548 	2^4423-2^1205*3-1       	1332
1100000000804065560 	2^9689-2^1828*3-1       	2917
1100000000804065535 	2^9689-2^202*3-1         	2917

[paulunderwood]

Originally Posted by pakaran

1100000000804065548 2^4423-2^1205*3-1 1332

./pfgw64 -V -i -tc -q"2^4423-2^1205*3-1" -h"helper_09"
PFGW Version 3.4.4.64BIT.20101104.x86_Dev [GWNUM 26.4]


CPU Information (From Woltman v25 library code)
Intel(R) Core(TM) i7-4770K CPU @ 3.50GHz
CPU speed: 3500.00 MHz, 4 cores
CPU features: RDTSC, CMOV, Prefetch, MMX, SSE, SSE2, SSE4.1, SSE4.2
L1 cache size: unknown
L2 cache size: 256 KB, L3 cache size: 8 MB
L1 cache line size: unknown
L2 cache line size: 64 bytes
TLBS: 64

Primality testing 2^4423-2^1205*3-1 [N-1/N+1, Brillhart-Lehmer-Selfridge]
Reading factors from helper file helper_09
Running N-1 test using base 3                                                  
Generic modular reduction using generic reduction FFT length 448 on A 4425-bit number
Running N+1 test using discriminant 13, base 2+sqrt(13)
Generic modular reduction using generic reduction FFT length 448 on A 4425-bit number
Calling N+1 BLS with factored part 27.68% and helper 0.23% (83.29% proof)
2^4423-2^1205*3-1 is Fermat and Lucas PRP! (0.1944s+0.0257s)

_09.in:

n=2^4423-2^1205*3-1
F=1
G=2^1205*11*67033

 gp < CHG.GP
Reading GPRC: /etc/gprc ...Done.

                  GP/PARI CALCULATOR Version 2.7.2 (released)
          amd64 running linux (x86-64/GMP-6.0.0 kernel) 64-bit version
          compiled: Sep 19 2014, gcc version 4.9.1 (Debian 4.9.1-14) 
                           threading engine: pthread
                (readline v6.3 disabled, extended help enabled)

                     Copyright (C) 2000-2014 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 = 500000
  ***   Warning: new stack size = 134217728 (128.000 Mbytes).
   realprecision = 15008 significant digits (15000 digits displayed)

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

Input file is:  TestSuite/_09.in
Certificate file is:  TestSuite_09.out
Found values of n, F and G.
    Number to be tested has 1332 digits.
    Modulus has 369 digits.
Modulus is 27.684648779108303772% 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 = 10, u = 4. Right endpoint has 226 digits.
        Done!  Time elapsed:  17748ms.
    Running CHG with h = 10, u = 4. Right endpoint has 213 digits.
        Done!  Time elapsed:  15741ms.
    Running CHG with h = 9, u = 3. Right endpoint has 190 digits.
        Done!  Time elapsed:  12148ms.
    Running CHG with h = 7, u = 2. Right endpoint has 157 digits.
        Done!  Time elapsed:  8517ms.
    Running CHG with h = 7, u = 2. Right endpoint has 116 digits.
        Done!  Time elapsed:  4680ms.
A certificate has been saved to the file:  TestSuite_09.out

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

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

Pol[1, 1] with [h, u]=[7, 2] has ratio=4.670568865392464778 E-251 at X, ratio=8.148375158710707375 E-240 at Y, witness=5.
Pol[2, 1] with [h, u]=[7, 2] has ratio=0.5573927723486209173 at X, ratio=2.3698841451812667437 E-82 at Y, witness=5.
Pol[3, 1] with [h, u]=[8, 3] has ratio=1.0000000000000000000 at X, ratio=9.829104895076774857 E-100 at Y, witness=7.
Pol[4, 1] with [h, u]=[9, 4] has ratio=1.0425340086454014303 E-99 at X, ratio=3.140269697688937236 E-94 at Y, witness=11.
Pol[5, 1] with [h, u]=[10, 4] has ratio=9.359357312492652555 E-26 at X, ratio=3.489446171608562181 E-53 at Y, witness=7.

Validated in 1 sec.


Congratulations! n is prime!
Goodbye!

This is probably less CPU intensive than Primo.

[axn]

Originally Posted by paulunderwood

This is probably less CPU intensive than Primo.

Considering that this is not accepted by factordb, it is entirely wasted CPU.

[pakaran]

Taking everything through 2384 digits.

[schickel]

Incoming certificate.

Also, Matthew posted a much bigger one.

[pakaran]

Nice!

I'm working on clearing up the 62 PRPs not significantly over 1k dd. I'll post again if I decide to do anything higher, and would ask others to do the same.

[pakaran]

Taking the bottom 128 (through 1200 dd).

[pakaran]

And I'm done for now.

[pakaran]

Taking 135 smaller numbers, through 1191 dd.

[pakaran]

Taking the 450 (!) smallest numbers.

[chris2be8]

I've spotted a couple of shortcuts:

1100000000804637633 	((61^1019-59^1019)/2+1)/199822
1100000000804637626 	(61^1019-59^1019)/2

1100000000804638204 	((13^2099-11^2099)/2-1)/302256
1100000000804638199 	(13^2099-11^2099)/2

After proving the smaller one of each pair you can quickly prove the larger by N+1 or N-1. Which should save you the time needed to create a certificate.

Chris