Simpson, Sam s.simpson at
Sat Feb 12 14:04:23 CET 2000

Hi Brian,

> -----Original Message-----
> From: brian moore [mailto:bem at]
> Sent: 12 February 2000 00:57
> To: s.simpson at
> Subject: Re: RSA
> On Fri, Feb 11, 2000 at 11:03:52AM +0100, Jan Du¹ek wrote:
> > Hi,
> > I'm from Czech Rep. and I'm trying to make an RSA 
> encrypting algorythm. But
> > I have a little problem. I don't know how to generate 
> prime-number. I found
> > some algorythms, but there's another problem with 
> commensurableness numbers.
> > I don't know how to check if two numbers are 
> commensurableness. (I'm sorry
> > about my English :-))
> Well, you can't really generate a random prime.  In order to do that,
> you'd have to be factoring really large numbers, which is generally
> impracticle (the whole point of RSA is based on the hardness of
> factoring).

Not true...It is possible to deterministically check to see if a number is
prime and the workload is FAR less than testing a primes up to the square

> You'll have to do it the way everyone else does: generate a really big
> number, check it against a few low primes (ie, 2,3,5, etc, maybe up to
> 1000 or so) and then use probability to determine whether 
> it's -likely- > to be a prime or not.

Erm, not true.  It is quicker to use probalistic methods, but if 100%
assurance is required then it is still feasible (on a PC - maybe not in
constrained environments) to produce a number that is *certainly* a prime
with a "deterministic method".  See for example Silvermans posts to

> An absolute must-have is Bruce Schneier's Applied Cryptography.  This
> will give you the varying algorithms used to test for primeness.

An even better book (IMHO) for practitioners rather than people with just a
general interest is Handbook of Applied Crypto by 
A.J.Menezes, P.C.van Oorschot and S.A.Vanstone.

> Again, you won't know for certain that 'x' is prime or not... but that
> will have to suffice.  (And as I recall, if the numbers are not prime
> the whole thing doesn't work anyway, so you get an extra 
> check anyway.)


Sam Simpson
Communications Analyst
-- for ScramDisk hard-drive encryption &
Delphi Crypto Components.  PGP Keys available at the same site. 

More information about the Gnupg-devel mailing list