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:
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 n-digit 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 big-Oh, 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.
"Home taping is killing big business profits. We left this side blank
so you can help." -- Dead Kennedys, written upon the B-side of tapes of
/In God We Trust, Inc./.
- 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