Re: fooling primality tests

From: Tom St Denis (tomstdenis@yahoo.com)
Date: 03/12/03 

From: tomstdenis@yahoo.com (Tom St Denis)
Date: 12 Mar 2003 06:22:29 -0800

trevp@trevp.net (Trevor Perrin) wrote in message news:<47e891f1.0303101109.66ca5581@posting.google.com>...
> Paul Crowley <paul@JUNKCATCHER.ciphergoth.org> wrote in message news:<87adg3h1os.fsf@saltationism.subnet.hedonism.cluefactory.org.uk>...
> > trevp@trevp.net (Trevor Perrin) writes:
> >
> > > I was wondering, how difficult is it to choose a composite number that
> > > appears prime when run through conventional, probabilistic primality
> > > tests?
> >
> > [...]
> >
> > However, no composite number has more than a 1/4 chance of passing a
> > Miller-Rabin test with random base selection, ever [1].
>
> Thanks Paul, Cristiano, everyone.
>
> Glad to see Miller-Rabin has hard bounds on its "foolability".
>
> Actually, I neglected that this is for a DH protocol where "safe
> primes" are desired, i.e. where I want q=(N-1)/2 to also be prime, but
> I assume in that case I can just repeat the primality test on q.

If all you want todo is make decent DH primes then there are simple
"theoretically" provable algorithms with zero error.

For instance, my paper at

http://iahu.ca:8080/papers/pp.pdf

[which has a few typos that I should go back and fix] describes an
algorithm that can produce primes P such that P-1 contains a very
large prime factor [not a "safe prime" but essentially the same]. For
example, if P were 1028 bits then the largest factor of P-1 would be
around 1000 bits long.

The algorithm [which I didn't invent but merely summarized] is
provably guaranteed to generate a prime at the end.

Tom

Relevant Pages

  • Re: compiler bugs
    ... if you have an algorithm that needs a trick like the above to meet ... The safe subset of the language ... The question then is whether those short-cuts are ...
    (comp.compilers)
  • Re: Problems With Public Key Cryptosystems
    ... Of the form that p-1 should not have certain ... >small prime divisors. ... >couldn't be sure that what seems safe today will be so tomorrow. ... seem to have been an artifact of the old factoring algorithms. ...
    (sci.math)
  • Re: Problems With Public Key Cryptosystems
    ... Of the form that p-1 should not have certain ... >small prime divisors. ... >couldn't be sure that what seems safe today will be so tomorrow. ... seem to have been an artifact of the old factoring algorithms. ...
    (sci.crypt)
  • Re: Prime Numbers and Carmichael Statements
    ... Is every even number the sum of two primes or the ... I interpreted 'directly' to mean a closed form solution with proof. ... is computationally equivalent to running an algorithm to test ... It's safe to say that we can do a lot better at problems 4 to 7 ...
    (sci.math)
  • Re: El Gamal modulus question
    ... There are some attacks on discrete log which retrieve the exponent ... modulo small factors of p-1. ... far as practical security is concerned, knowing that you are safe is at ... It needs not be a generator for the whole Z* group. ...
    (sci.crypt)
Quantcast