APR-CL as primality proof - Page 2

chris2be8 · 2014-01-09, 17:33

You could patch the program to bypass the PRP tests and always do the trial division. That would test the code reports a number is composite if divisible by one of the trial divisors (given a suitable test case). And you could make it print how many trial divisors it calculated (and list them if not too many). But this would NOT prove the trial divisors were always calculated correctly.

I've done similar things to check "impossible" conditions would in fact be reported. But those conditions were easy to test for.

Or you could be paranoid and run both APR-CL and ECPP against the number.

Chris

R.D. Silverman · 2014-01-09, 17:45

Quote:

Originally Posted by chris2be8

You could patch the program to bypass the PRP tests and always do the trial division. That would test the code reports a number is composite if divisible by one of the trial divisors (given a suitable test case).

No, No, No! If this were possible, it would be a very fast factoring
algorithm! Just pass a composite to the code, bypass the
PRP tests, and have it factored!

f1pokerspeed · 2014-01-09, 20:18

Are these trial divisors different for every number, or are they the same? If the latter is true, you could possibly compute and verify known divisors and store them in a file, to ensure that any issues w.r.t programming error are removed. That would be a step forwards towards a trusted implementation.

R.D. Silverman · 2014-01-09, 21:06

Quote:

Originally Posted by f1pokerspeed

Are these trial divisors different for every number, or are they the same? If the latter is true, you could possibly compute and verify known divisors and store them in a file, to ensure that any issues w.r.t programming error are removed. That would be a step forwards towards a trusted implementation.

They are different.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Prime numbers test primality - with proof written in invisible ink	Godzilla	Miscellaneous Math	40	2018-10-17 00:11
500€ Reward for a proof for the Wagstaff primality test conjecture	Tony Reix	Wagstaff PRP Search	7	2013-10-10 01:23
Proof of Primality Test for Fermat Numbers	princeps	Math	15	2012-04-02 21:49
Primality searches and primality successes	marco_calabresi	Information & Answers	3	2009-04-17 19:44
PRIMALITY PROOF for Wagstaff numbers!	AntonVrba	Math	96	2009-02-25 10:37

2014-01-09, 17:33	#12
chris2be8 Sep 2009 2×1,039 Posts	You could patch the program to bypass the PRP tests and always do the trial division. That would test the code reports a number is composite if divisible by one of the trial divisors (given a suitable test case). And you could make it print how many trial divisors it calculated (and list them if not too many). But this would NOT prove the trial divisors were always calculated correctly. I've done similar things to check "impossible" conditions would in fact be reported. But those conditions were easy to test for. Or you could be paranoid and run both APR-CL and ECPP against the number. Chris

2014-01-09, 20:18	#14
f1pokerspeed Jun 2012 1101010₂ Posts	Are these trial divisors different for every number, or are they the same? If the latter is true, you could possibly compute and verify known divisors and store them in a file, to ensure that any issues w.r.t programming error are removed. That would be a step forwards towards a trusted implementation.