Proven Primes

[Anton Stiglic]

----- Original Message -----
From: "tom st denis" <tomstdenis at yahoo.com>
To: "Cryptography" <cryptography at wasabisystems.com>
Sent: Tuesday, March 11, 2003 11:28 AM
Subject: Re: Proven Primes


>
> --- Tero Kivinen <kivinen at iki.fi> wrote:
> > SOPHIE GERMAIN PRIME SEARCH
> > FIXED 64 bits.
> > INDEX 0:
> > PRIME (bits 512), index = 131, 0.989151 seconds:
> >
>
0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b
139b22514a08798e3404ddef9519b3cd3a439dffffffffffffffff
>
> What is the benefit of having leading/trailing bits fixed?  As far as I
> know it doesn't make any form of index calculus attack any harder to
> apply.

No, but you can speed up modulo multiplication.  The OAKLEY RFC
says:
   The high order 64 bits are forced to 1.  This helps the
   classical remainder algorithm, because the trial quotient digit can
   always be taken as the high order word of the dividend, possibly +1.
   The low order 64 bits are forced to 1.  This helps the Montgomery-
   style remainder algorithms, because the multiplier digit can always
   be taken to be the low order word of the dividend.

At one point in time some of my colleagues got the optimization with the
high order bits set to 1 in C code going on very well, I don`t remember if
we implemented the optimization with the low order bits set to 1.

--Anton



---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com