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

*From*: Le Chaud Lapin <jaibuduvin@xxxxxxxxx>*Date*: Wed, 4 Jun 2008 13:30:34 -0700 (PDT)

On Jun 4, 2:39 pm, David Eather <eat...@xxxxxxxxxx> wrote:

Le Chaud Lapin wrote:

Hi All,

What are the prevaling recommendations for choosing p, q, such that

the product is indeed, say, 512 bits, for a 512-bit modulus.

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.

TIA,

-Le Chaud Lapin-

It's a game of Logs (base 2)

Add P and Q.

If the result is longer than the length of N/2 the product is too big

(just look for the most significant "1"). If less than N/2 -1 the

product will be too small. No division, no multiplication (you already

know the length of N so N/2 is not hard to figure out first)

Somebody else probably got here first.

Hmm...

Let [x] denoting bit-width of x.

I choose [N] to be 8 bits.

I choose P = 11. Then [P] = 4.

I choose Q = 13. Then [Q] = 4.

N = 11*13 = 143. [N] = 8, as expected.

P+Q = 11+13 = 24. [P+Q] = 5.

[N]/2 = 8/2 = 4.

5 is greater than 4.

Since 5 is greater than 4, according to your suggestion, I should

reject P = 11, Q = 13 as candidates for generating an 8-bit N,

because N would be greater than 8 bits, an erroneous conclusion,

unless I misunderstand what you wrote.

-Le Chaud Lapin-

.

**Follow-Ups**:**Re: Algorithm For Ensuring p & q Sufficiently Large For n in RSA***From:*David Eather

**Re: Algorithm For Ensuring p & q Sufficiently Large For n in RSA***From:*David Eather

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

- Prev by Date:
**Re: Algorithm For Ensuring p & q Sufficiently Large For n in RSA** - Next by Date:
**Basic question: Public-key encryption** - 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):