## How find best evidence N is probably prime ?

Expand Messages
• 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
Message 1 of 1 , Nov 13, 2008
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 ) .
http://primes.utm.edu/prove/
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" ,
http://www.pseudoprime.com/pseudo/sermon07-1.pdf
and by Martin Seysen in
"A Simplified Quadratic Frobenius Primality Test" ,
http://eprint.iacr.org/2005/462.pdf
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" ,
http://upforthecount.com/math/nnnp1np1.html
and the generalized repunit primes based on Fermat prime bases in
the pages just below "sigma ( phi (n) ) = phi ( sigma (n) )" ,
http://upforthecount.com/math/sigmaphi.html
suggest 2 bases for my interest in this question .