LL question

ZachB · 2004-08-26, 06:36

Just wondering, when Prime95 is testing a number for primality, is it possible for it to discover that it's not prime partway through its testing, or does it have to test the number all the way to the end before it can be called a prime or not?

S80780 · 2004-08-26, 10:28

As for the LL-Test, yes, it has to be passed completely, before you can say anything about the tested number being prime or not.
As for Trial-Factoring, no, each candidate can be a factor thus stopping the test nearly instantly (as far as I know, the actual bit-level will be finished before).
As for P-1, no, the test can stop at any time a GCD is computed. Prime95 computes (up to) two GCDs, one for each stage of the P-1-Test.

2004-08-26, 06:36	#1
ZachB Aug 2004 2 Posts	LL question Just wondering, when Prime95 is testing a number for primality, is it possible for it to discover that it's not prime partway through its testing, or does it have to test the number all the way to the end before it can be called a prime or not?

2004-08-26, 10:28	#2
S80780 Jan 2003 far from M40 5³ Posts	As for the LL-Test, yes, it has to be passed completely, before you can say anything about the tested number being prime or not. As for Trial-Factoring, no, each candidate can be a factor thus stopping the test nearly instantly (as far as I know, the actual bit-level will be finished before). As for P-1, no, the test can stop at any time a GCD is computed. Prime95 computes (up to) two GCDs, one for each stage of the P-1-Test.