mersenneforum.org Noob question about primality checking
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2020-09-30, 17:14 #1 hunson   Feb 2020 Germany 37 Posts 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
2020-09-30, 18:21   #2
paulunderwood

Sep 2002
Database er0rr

F8D16 Posts

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

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=....

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

 2020-10-01, 18:09 #3 hunson   Feb 2020 Germany 37 Posts 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
2020-10-01, 18:17   #4
paulunderwood

Sep 2002
Database er0rr

398110 Posts

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

 2020-10-02, 14:19 #5 hunson   Feb 2020 Germany 37 Posts 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.
 2020-10-02, 14:52 #6 paulunderwood     Sep 2002 Database er0rr 398110 Posts 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

 Similar Threads Thread Thread Starter Forum Replies Last Post WhoCares Math 51 2017-04-20 17:17 bozocv Msieve 36 2015-12-31 00:12 Unregistered Information & Answers 11 2013-03-23 01:31 nuggetprime Programming 6 2008-08-23 11:09 xago666 Information & Answers 3 2008-03-11 01:35

All times are UTC. The time now is 04:37.

Sun Jan 23 04:37:55 UTC 2022 up 183 days, 23:06, 0 users, load averages: 1.77, 1.39, 1.29

Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔