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

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-
.