# Re: The time for genertating and testing a prime

"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?

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

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

Phil
--
"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./.
.

## Relevant Pages

• Re: Ask EU - Norton AV 2006
... a password by taking the first letter (or first two or three letters) ... include digits, the number goes up to 36^6. ... punctuation characters increases the number still further. ... An exhaustion attack is one in which the attacker uses a program ...