Re: The time for genertating and testing a prime
 From: Phil Carmody <thefatphil_demunged@xxxxxxxxxxx>
 Date: 18 Sep 2006 20:53:35 +0300
"bert" <bert.hutchings@xxxxxxxxxxxxxx> writes:
bobic wrote:
Hi, guys.
I want to know how long the generating a prime take, and how long the
testing a prime take. Can you give me some results or some references?
Thanks in advance!
This construction of an ndigit prime P is almost trivial.
Take a prime Q of more than n/2 digits, using this method
recursively if desired.
Unnecessarily slow. Find 2 primes, Q1 and Q2, of about
n/6 digits, using this method recursively if desired. Use
the CRT to construct P==+1 mod Q1, P==1 mod Q2.
Step through possible primes
P = kQ + 1. Test them with a random number A by
calculating B = A^k mod P.
Unnecessarily slow. Use A << P, such as A=2, so that modular
multiplication by A can effectively be done for free.
If B is 1, try the next P.
If not, calculate U = B^Q mod P. If U is 1, P is prime,
and if not, not. These modular exponentiations are
quicker than one RSA encryption step anyway.
The method is academic, even with a more reasonable
Q of 3n/4 digits,
What's "more reasonable" about using a larger Q?
If you look at the bigOh, you want the smallest Q possible.
because the results are in a very small
subset of the primes around P, which cryptographically
is just a huge blunder in principle, even if you can't see
how an attacker would utilise it.
But it's a subset the attacker doesn't know about.
Using your logic, no prime is safe, as it's in a subset
of size 1 of primes near it, namely the singleton containing
it. It matters not what I see  if the attacker doesn't know
what subset of the primes it's in, the can't use any
information about that subset.
Phil

"Home taping is killing big business profits. We left this side blank
so you can help."  Dead Kennedys, written upon the Bside of tapes of
/In God We Trust, Inc./.
.
 References:
 The time for genertating and testing a prime
 From: bobic
 Re: The time for genertating and testing a prime
 From: bert
 The time for genertating and testing a prime
 Prev by Date: Re: The time for genertating and testing a prime
 Next by Date: Re: CAPTCHA email images
 Previous by thread: Re: The time for genertating and testing a prime
 Next by thread: Re: The time for genertating and testing a prime
 Index(es):
Relevant Pages
