mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > And now for something completely different

Reply
 
Thread Tools
Old 2020-09-30, 17:14   #1
hunson
 
Feb 2020
Germany

52 Posts
Default Noob question about primality checking

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

Last fiddled with by hunson on 2020-09-30 at 17:23
hunson is offline   Reply With Quote
Old 2020-09-30, 18:21   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1101101011102 Posts
Default

Quote:
Originally Posted by hunson View Post
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:

Quote:
\\ 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:

Code:
\\  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.

Last fiddled with by paulunderwood on 2020-09-30 at 19:08
paulunderwood is offline   Reply With Quote
Old 2020-10-01, 18:09   #3
hunson
 
Feb 2020
Germany

52 Posts
Default

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
hunson is offline   Reply With Quote
Old 2020-10-01, 18:17   #4
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·17·103 Posts
Default

Quote:
Originally Posted by hunson View Post
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.
paulunderwood is offline   Reply With Quote
Old 2020-10-02, 14:19   #5
hunson
 
Feb 2020
Germany

52 Posts
Default

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.
hunson is offline   Reply With Quote
Old 2020-10-02, 14:52   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·17·103 Posts
Default

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

Last fiddled with by paulunderwood on 2020-10-02 at 14:54
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
checking very large number for primality. WhoCares Math 51 2017-04-20 17:17
Noob Question: What to use bozocv Msieve 36 2015-12-31 00:12
Noob Question Unregistered Information & Answers 11 2013-03-23 01:31
Noob C question nuggetprime Programming 6 2008-08-23 11:09
Noob question xago666 Information & Answers 3 2008-03-11 01:35

All times are UTC. The time now is 19:15.

Sat Nov 28 19:15:20 UTC 2020 up 79 days, 16:26, 3 users, load averages: 1.29, 1.50, 1.55

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.