Re: [PrimeNumbers] Re: GFN testing quickie
- At 02:47 PM 4/18/2002 +0000, jim_fougeron wrote:
> >Typical timing could be:Is it generally accepted that primality testing - even for the 'best'
> >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.
numbers - can never be better than THETA( (lg n)^2) ?
Nathan, whose college doesn't go into detail about these things much at all