RSA
brian moore
bem at cmc.net
Sat Feb 12 14:18:16 CET 2000
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.
More information about the Gnupg-devel
mailing list