How find best evidence N is probably prime ?
- Greetings , all ,
For very large N , possibly too large to prove prime , what is the best
way to exhaust rational hope that N is composite ?
Restated , what method quickly develops the best evidence that N is
very probably prime ?
This question is taken up in C&P , but seems to peter out after section
3.6.5 , "The general Frobenius test" .
( Of course , I don't blame C&P ; their book is already 600 pages ) .
at Chris Caldwell's marvelously informative web site also seems to peter
out after section 2.3 ,
"Strong probable-primality and a practical test" .
There is apparently much more to say , as suggested by Jon Grantham
in "An Unconditional Improvement to the Running Time of the Quadratic
Frobenius Test" ,
and by Martin Seysen in
"A Simplified Quadratic Frobenius Primality Test" ,
Looking on the Web , I see no recent code on the Web for the later
Frobenius test(s) nor M"uller's tests , nor etc.
A C function based on NTL would be a delightfully relevant answer to
this question .
"Huge factors of enormous integers" ,
and the generalized repunit primes based on Fermat prime bases in
the pages just below "sigma ( phi (n) ) = phi ( sigma (n) )" ,
suggest 2 bases for my interest in this question .
Thanks for your attention .