RSA

[brian moore]

On Sat, Feb 12, 2000 at 02:04:23PM +0000, Simpson, Sam wrote:
> Hi Brian,

Hello.

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

Got an algorithm?

> > 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
> sci.crypt
> (http://x28.deja.com/[ST_rn=ps]/getdoc.xp?AN=564819271&CONTEXT=950363781.265
> 224197&hitnum=2)

I don't see an algorithm cited there, just "algorithms exist".

(The algorithm at the end of the cited post is not proven -- it's still
a matter of statistics.  There's a huge difference between "well, we
haven't seen a non-prime pass this gauntlet" and "a non-prime cannot
pass this".)

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