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

Re: [PrimeNumbers] Re: GFN testing quickie

Expand Messages
  • Nathan Russell
    ... Is it generally accepted that primality testing - even for the best numbers - can never be better than THETA( (lg n)^2) ? Nathan, whose college doesn t
    Message 1 of 5 , Apr 18, 2002
    • 0 Attachment
      At 02:47 PM 4/18/2002 +0000, jim_fougeron wrote:
      > >Typical timing could be:
      > >for 131072: ~ 12 hours
      > >for 262144: ~ 2 days
      > >for 524288: ~ 1 week
      > >for 1048576: ~ 1 month
      > >for 2097152 : ~ 4 months
      > >
      > > Yves
      >
      >These timings are about identical (in pattern) to what I have also
      >seen. Each level higher takes almost exactly four times as long
      >to perform a single full test in Proth as the level below it. The
      >above "timings" show the +1 size == 4x time very well. The 4x is
      >perfectly expected also. Twice as many FFT limbs and twice as many
      >squarings to complete a test.

      Is it generally accepted that primality testing - even for the 'best'
      numbers - can never be better than THETA( (lg n)^2) ?

      Nathan, whose college doesn't go into detail about these things much at all
    Your message has been successfully submitted and would be delivered to recipients shortly.