Re: fooling primality tests

From: Phil Carmody (thefatphil_demunge@yahoo.co.uk)
Date: 03/13/03 

From: "Phil Carmody" <thefatphil_demunge@yahoo.co.uk>
Date: Thu, 13 Mar 2003 23:45:42 +0200

On Thu, 13 Mar 2003 03:58:47 +0000, Michael Amling wrote:

> Trevor Perrin wrote:
>>
>> Thanks, my particular concern isn't generating primes, but efficiently
>> verifying that a number provided by a 3rd party is, in fact, a "safe
>> prime" (for example, this might be useful for the client to do in the
>> SRP protocol, if the server is supplying the group parameters).
>>
>> The best thing I can think of is 64 iterations of Miller-Rabin with
>> random bases on both N and (N-1)/2 (preceding this with trial
>> division, or other optimizations, don't seem that useful cause N isn't
>> random, but chosen by the server).
>
> Others on this forum have said that no composite is known that passes
> both a single Miller-Rabin and a single
> Lucas-somebodywhosenameescapesme. I expect that a Lucas-som..sme would
> be faster than 63 more Miller-Rabins.

Not so. You're thinking of the $620 PSW challenge, which is to find
a number == +/-2 mod 5 that is a 2-PRP (Fermat Pseudoprime) and also
a (1,-1)-LucasPRP (or Fibonacci) pseudoprime.

There are other 'none known' cases - for example I think that Grantham
(its inventor) has put up $6.20 for a (5,5)-FrobeniusPSP. (I may have a
sign wrong).

Certainly, if you're thinking of doing 63 PRP tests, you'd be far better
doing 21 Frobenius tests at the same cost.

Phil

Relevant Pages

  • Re: How do I find where my application is crashing
    ... obvious when compiled as a Release build because of optimizations and ... Try reducing the compiler and linker optimization settings 1 by 1 ... > simply crashing but with no signs/details on where the crash is occuring. ... > server is running on a Win2K3 host. ...
    (microsoft.public.dotnet.general)
  • Re: fooling primality tests
    ... >> efficiently verifying that a number provided by a 3rd party is, ... but chosen by the server). ... > passes both a single Miller-Rabin and a single ... IIRC my implementation of the SLP takes about 10 iterations of MR. ...
    (sci.crypt)
  • Re: Strings, Arrays, c++ and java
    ... It seems the difference between the two is that client is optimized for VM startup time while server is optimized for execution time. ... The server mode can take more time to figure out optimizations, so it is able to be more aggressive about them. ...
    (comp.lang.java.programmer)
  • Re: Slow Soft-RAID 5 performance
    ... I'm getting a strange slow performance behavior on a recently installed ... Server: Asus AS-TS500-E4A ... With no optimizations with 10 raptors I get 180-200MB/s, with optimizations, 464MB/s write and 622MB/s read. ...
    (Linux-Kernel)
  • Re: Sun Java FYI
    ... Using the client VM or the server VM? ... optimizations and thus used to have slower startup, ... for tiny little apps but faster for longer running or calculation ... almost invisible and for long running biginteger apps the server ...
    (microsoft.public.windowsxp.general)
Quantcast