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

*From*: Christian Siebert <iBBiS@xxxxxx>*Date*: Thu, 5 Jun 2008 01:25:54 -0700 (PDT)

On 5 Jun., 05:54, Le Chaud Lapin wrote:

I have decided to go with the multiply-and-see algorithm, where n isgood choice - that is a simple and correct method (just slightly

calculated from p * q, and the bit count of n is checked to see that

it is sufficient.

suboptimal)

This algorithm guarantees that all bit states of p and q will beI agree

reachable during the randomization phase of p and q, and also

guarantees that the values will be unbiased, Fermat factoring

threshold notwithstanding.

It is also simpler and faster than both division and root. [Evenhere I have to disagree, first some facts:

though I had intended to have a root/remainder function anyway].

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

.

**Follow-Ups**:**Re: Algorithm For Ensuring p & q Sufficiently Large For n in RSA***From:*Le Chaud Lapin

**References**:**Re: Algorithm For Ensuring p & q Sufficiently Large For n in RSA***From:*Nelson B

**Re: Algorithm For Ensuring p & q Sufficiently Large For n in RSA***From:*Nelson B

**Re: Algorithm For Ensuring p & q Sufficiently Large For n in RSA***From:*Le Chaud Lapin

- Prev by Date:
**Re: Future safe PK-methods?** - Next by Date:
**XOR as encryption - security considerations** - Previous by thread:
**Re: Algorithm For Ensuring p & q Sufficiently Large For n in RSA** - Next by thread:
**Re: Algorithm For Ensuring p & q Sufficiently Large For n in RSA** - Index(es):