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

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 ...
    (uk.media.radio.archers)
  • Re: Generating valid identifiers
    ... Unless an attacker can select the field names, in which case they may be ... collision attacks. ... If the OP sticks with his intention to use CRC32, ... cryptographically random, and only generates eight hex digits, not ten. ...
    (comp.lang.python)
  • Re: encryption with pi
    ... It is as hard for an attacker to generate the digits of pi as ... > it is for the original user. ... That is a bad crypto system. ...
    (sci.crypt)