Re: fooling primality tests

From: Cristiano (cristiano.pi@nsquipo.it)
Date: 03/15/03 

From: "Cristiano" <cristiano.pi@nsquipo.it>
Date: Sat, 15 Mar 2003 17:18:35 GMT

Tom St Denis wrote:
> "Cristiano" <cristiano.pi@nsquipo.it> wrote in message
> news:voGca.15628$Lr4.481734@twister2.libero.it...
>> Vic Drastik wrote:
>>>
>>> The full M-R test is first trial division of n by all primes less
>>> than 80 followed by M-R of n to all prime bases less than (15*k*k -
>>> 88*k + 130)/10 where k = ln(n).
>>
>> Is ln(n) base 2 or base e?
>
> Even if its base e for a 1024-bit test you have to run the test with
> 750,000 bases. That would take quite some time even if this fact
> were true [and I don't know].

If I understand correctly, are needed "only" the primes from 2 to
750,000 not 750,000 primes.
Anyway the algorithm requires too much time for practical purposes.

>>> For technical details, read Wedeniwski's thesis available online
>>> here
>>>> http://www.zetagrid.net/zeta/dissertation.pdf
>>
>> I get 'Page not found'. Do you have another link?
>
> The link is correct, the file is just missing. [goto the zetagrid
> site and check for yourself!]

I found it, thanks.
Have you found the formula to which Vic is referring to? I not.
Something that can be interesting is at page 97...

Cristiano

Relevant Pages