Loading ...
Sorry, an error occurred while loading the content.

How find best evidence N is probably prime ?

Expand Messages
  • Walter Nissen
    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
    • 0 Attachment
      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 .

      Thanks for your attention .

      Cheers ,

      Walter
      http://upforthecount.com
    Your message has been successfully submitted and would be delivered to recipients shortly.