Prime searching

Werner Koch wk at
Sat Jan 26 17:59:09 CET 2008

On Sat, 19 Jan 2008 11:09, hs2412 at said:

> Could any one tell me the high-level prime search method employed by
> GPG? Is it something like this:
> - generate a random number
> - is it prime? if yes, use it
> - if not, continue adding ones to it until a prime number is found

Well adding two of course.

> Also, which algorithm is used by GPG for testing primality?

Rabin Miller as usual.  See also Lim and Lee in the CRYPTO '97
proceedings (ISBN3540633847) page 260.



Die Gedanken sind frei.  Auschnahme regelt ein Bundeschgesetz.

More information about the Gnupg-users mailing list