Prime searching

[Werner Koch]

On Sat, 19 Jan 2008 11:09, hs2412 at gmail.com 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.


Shalom-Salam,

   Werner



-- 
Die Gedanken sind frei.  Auschnahme regelt ein Bundeschgesetz.