Noob question about primality checking

[hunson]

Hi everyone,

I have a noob question about the pari scripts that are used to test primes that can not be factored / certified by primo that easily.
I would like to do these tests in addition to the N-1/N+1 tests that pfgw does with my candidates.
Currently I am a bit obsessed with general repunit primes and I came across the additional information (http://xenon.stanford.edu/~tjw/pp/index.html) on C. Caldwell's prime page of these numbers. There CHG, KP and BLS scripts where used to check for primality. I already downloaded the 'Coppersmith - Howgrave-Graham Primality Prover' as pari script and the 'Coppersmith - Howgrave-Graham Primality Prover' script.
I have a good understanding of programming/scripts but here I have no clue how to feed my candidates/factors into those scripts. The thread ' If you find a prime...' (https://www.mersenneforum.org/showthread.php?t=19118) unfortunally did not help.

Could someone please explain to me how to use them, do the nessesary preperatory work and where the input files come from or point me to a documentation I have missed ?

kind regards

hunson

[paulunderwood]

Originally Posted by hunson

Hi everyone,

I have a noob question about the pari scripts that are used to test primes that can not be factored / certified by primo that easily.
I would like to do these tests in addition to the N-1/N+1 tests that pfgw does with my candidates.
Currently I am a bit obsessed with general repunit primes and I came across the additional information (http://xenon.stanford.edu/~tjw/pp/index.html) on C. Caldwell's prime page of these numbers. There CHG, KP and BLS scripts where used to check for primality. I already downloaded the 'Coppersmith - Howgrave-Graham Primality Prover' as pari script and the 'Coppersmith - Howgrave-Graham Primality Prover' script.
I have a good understanding of programming/scripts but here I have no clue how to feed my candidates/factors into those scripts. The thread ' If you find a prime...' (https://www.mersenneforum.org/showthread.php?t=19118) unfortunally did not help.

Could someone please explain to me how to use them, do the nessesary preperatory work and where the input files come from or point me to a documentation I have missed ?

kind regards

hunson

Pari uses two functions: isprime() and ispseudoprime(). They are about the same for n<2^64. The latter is a probablistic test that since its conception in the '80's has no known counterexample -- I should say Pari/GP uses a simplified version of Baillie-PSW.

For CHG you need "known factors" of n-1 and n+1:

\\ three definitions:
\\ - n is the number being factored.
\\ - F is the factored portion of n-1.
\\ - G is the factored portion of n+1.
\\ The factored portions should be given as numbers, not lists of factors.
\\ There is currently no functionality for queuing multiple jobs in the same
\\ todo file.
\\
\\ Sample input file:
\\
\\ n = 1488565707357402911845015158554633286356257506687627387456491927921949262
0\
\\ 56238946972039271873205763810089323298099420163474825226464788481;
\\ F = 43556142965880123323311949751266331066368;
\\ G = 1;

Make a directory called TestSuite and in put a ".in" extension file containing three lines: n=..., F=..., G=....

Adjust the script:

\\  PROGRAM INPUT
\\  -------------

worktodofile="TestSuite\/_09.in";
certificatefile="TestSuite\_09.out";

and run the whole program like this: gp CHG.GP. This will produce the .out file.

The proof assumes you have run PFGW with the know factors in a helper file. Just list known factors in a file called something like "helper.txt" and run ./pfgw64 -hhelper.txt -tc <input_file_with_n_in_it> (or the number). PFGW64 is required to say it is Fermat-PRP and Lucas-PRP.

[hunson]

Thank you for the explanation.
I have one further question regarding the ~33 % factorisation of the numbers listed at http://xenon.stanford.edu/~tjw/pp/index.html . Can I assume numbers this big are factored on big clusters / universities to finish in a reasonable amount of time ?

If so, I might refrain to persue to search for those numbers since I only have one machine to check.


kind regards


hunson

[paulunderwood]

Originally Posted by hunson

Thank you for the explanation.
I have one further question regarding the ~33 % factorisation of the numbers listed at http://xenon.stanford.edu/~tjw/pp/index.html . Can I assume numbers this big are factored on big clusters / universities to finish in a reasonable amount of time ?

If so, I might refrain to persue to search for those numbers since I only have one machine to check.


kind regards


hunson

There is the rub. Factorisation, usually ECM, of larger factors of large numbers is CPU intensive. I have no figures on the CPU days required. I suggest you email Tom Wu for more information.

[hunson]

Again, thanks for the reply.
I tried to contact T. Wu, but it seems that the email addres no longer works.
Ok, lets not get to off topic.
I will try to set up the software to do a test.


Thanks.

[paulunderwood]

There may be some low hanging fruit in the masses of data in factorDB, for you to practice some ECM/CHG/KP on. Perhaps some one else can give pointers to likely numbers