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

On May 29, 6:32 am, Ertugrul Söylemez <e...@xxxxxxxx> wrote:
Le Chaud Lapin <jaibudu...@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.

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.

Note that the crux of my OP, making sure that the product really does
have 512 bits, is not assured by setting only the highest-order and
lowest-order bits of p and q and hunting for primes from those bases.
It is possible that a p and q, each with 256 bits, will not generate
an n of 512 bits.

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.

And finally AKS, heheh. :)

Some might say it is unecessary, but IMO, a function with the
following signature..

bool Big_Integer::is_prime()

should not be named as such if there is a possibility that it will
return true when false is correct.

[We still keep our ::is_probably_prime (unsigned int)]

-Le Chaud Lapin-
.

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: simple algorithm for finding primes
    ... Well it includes the Sieve of Eratosthenes within the source. ... Your algorithm is a fine, simplistic algorithm, however it really only works ... because you determine the entire sequence of primes one after another. ... for longer and longer sequence of primes it will get slower and slower and ...
    (comp.lang.c)