Re: primality
- From: Ertugrul Soeylemez <do-not-spam-me@xxxxxxxx>
- Date: Mon, 2 Apr 2007 02:29:16 +0200
Sebastian Gottschalk <seppi@xxxxxxxxx> (07-04-02 00:08:40):
Normally one would do some quick fermat tests to get a high
probability, and the contrary being proven when the RSA or whatever
crypto scheme fails to work properly.
Rabin-Miller is for ensuring corner cases like Carmichael numbers,
which are unlikely to occur if the number was generated randomly.
Trying whether RSA works is equivalent to Fermat's test. Doing Fermat
tests alone is discouraged. Yes, Carmichael numbers are seldom, but
consider this: Since a Miller-Rabin employs two modular
exponentiations, where Fermat employs only one, a Fermat interation is
twice as fast as a Miller-Rabin iteration.
But on the other hand, each Miller-Rabin iteration with a negative (i.e.
not composite) result lowers the probability of the number being
composite by a factor of 4, where Fermat lowers it only by 2. And as an
extra, it does detect Carmichael numbers.
Regards,
Ertugrul Söylemez.
--
From the fact that this CGI program has been written in Haskell, it
follows naturally that this CGI program is perfectly secure.
.
- Follow-Ups:
- Re: primality
- From: Bryan Olson
- Re: primality
- References:
- primality
- From: Antony Clements
- Re: primality
- From: Ertugrul Soeylemez
- Re: primality
- From: Phil Carmody
- Re: primality
- From: Ertugrul Soeylemez
- primality
- Prev by Date: Re: 4 Simple Function Calls to Factor N
- Next by Date: SOCKET- AN ALGORITHM - repost
- Previous by thread: Re: primality
- Next by thread: Re: primality
- Index(es):
Relevant Pages
|
