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

On 5 Jun., 05:54, Le Chaud Lapin wrote:
I have decided to go with the multiply-and-see algorithm, where n is
calculated from p * q, and the bit count of n is checked to see that
it is sufficient.
good choice - that is a simple and correct method (just slightly
suboptimal)

This algorithm guarantees that all bit states of p and q will be
reachable during the randomization phase of p and q, and also
guarantees that the values will be unbiased, Fermat factoring
threshold notwithstanding.
I agree

It is also simpler and faster than both division and root. [Even
though I had intended to have a root/remainder function anyway].
here I have to disagree, first some facts:
1) multiplication, division and this "special" root function are more
or less equally fast (theoretically speaking O(b^2) for b=log n and
the school methods)
2) testing whether 'p' and 'q' are prime numbers is much more
expensive (theoretically speaking O(b^3) for the usual probabilistic
methods)
this means:
a) the most time consuming part is primality testing, everything else
is negligible
b) if your multiply-and-see algorithm detects that the number of bits
is not sufficient it will restart from the beginning => this will
effectively multiply the loop time by a factor>1 (this is surely
slower than the additional overhead of my pre-computation)
c) good random bits (for 'p' and 'q') are usually also very important
and observation b) also applies to this resource

Christian
.