RSA

[brian moore]

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

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.

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

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

-- 
Brian Moore                       | Of course vi is God's editor.
      Sysadmin, C/Perl Hacker     | If He used Emacs, He'd still be waiting
      Usenet Vandal               |  for it to load on the seventh day.
      Netscum, Bane of Elves.