Re: Algorithm For Ensuring p & q Sufficiently Large For n in RSA

Le Chaud Lapin <jaibuduvin@xxxxxxxxx> wrote:

What are the prevaling recommendations for choosing p, q, such that
the product is indeed, say, 512 bits, for a 512-bit modulus.

Actually, an N bits long product of two primes doesn't really contain N
bits of entropy. Since there are only pi(2^N) - pi(2^(N-1)) primes of N
bits, with Legendre's approximation, one 512 bits prime contains only
slightly more than 502.5 bits of entropy, so a 1024 bits long RSA
modulus would contain only 1005 bits of entropy.

I don't think that this entropy difference can be exploited in practice,
and honestly, I wouldn't care about it. Just follow Joseph's advice.


There are things that can be done to the bit-pattern of p and q during
randomization phase obviously, and I recall a while back in Coutinho's
there was a recommendation, but I wanted to explore more.

Yes, to generate an N bits prime, first you create a prime sieve using
the sieve of Eratosthenes or the sieve of Atkin. Then repeat the
following, until you have found enough primes: Generate a random number
less than 2^N, then set its lowest and highest bits to 1, then adjust it
according to your sieve, then do a primality test.

The primality test itself consists of trial division by the first few
thousand primes, which are not covered by the prime sieve, and if the
number still passes, then a Miller-Rabin or some other fast test is
done.

In practice though, no sieve is used, because the speed improvement is
neglible for most purposes. Full trial division for the first few
thousand primes is used instead.


Regards,
Ertugrul.


--
http://ertes.de/

.

Relevant Pages

  • Re: greatest multiple algorithm
    ... Bernstein or Galway's quadratic form sieve rather than ... lower or smaller primes in bit sieve. ... slower with larger sieve sizes due to the large number of memory accesses. ... You can use a wheel to decrease the memory requirements. ...
    (comp.lang.asm.x86)
  • Re: greatest multiple algorithm
    ... Bernstein or Galway's quadratic form sieve rather than ... lower or smaller primes in bit sieve. ... slows down based on size memory used ... You can use a wheel to decrease the memory requirements. ...
    (comp.lang.asm.x86)
  • Re: How to write a efficient Sieve of Eratosthenes algorithm in lisp?
    ... the ultimate test is to find primes in range 999900000 - ... Also, my sieve algorithm is n log, so even if the space ... (loop for x from (start-index n) ... Real time: 0.4375 sec. ...
    (comp.lang.lisp)
  • Re: As the Crow flies.
    ... Almost any sieve would do. ... counting primes < 1000000 ... mark.c:50: warning: return type defaults to ?int? ... mark.c:56: warning: format ?%lld? ...
    (talk.origins)
  • Re: Segfault City
    ... C offers no guarantee that there is any character with a code point ... Not those exact words, but yes, it's true that the Standard offers no such ... but I am in the mood to write a Sieve. ... Number of primes in the sieve: ...
    (comp.lang.c)