Re: [Cfrg] Prime 630*(427!+1)+1 for classic DH?

["Anna (Amy) Johnston" <[e-mail]>]

With a prime like this (and with the knowledge that q is prime), a better way (non-probabilistic) is to use Pocklington's theorem.  Two exponentiations with the right base and you've proved primality.  q can also be checked for primality with Pocklington's, but it takes a larger number of much smaller exponentiations.

The SNFS reduces the computation cost of the sieve, but as larger base fields become the norm (at least 2048 bits), the linear algebra, not the sieve will be the problem (see iacr e-print 2017/067, page 8, as well as other discrete logarithm records in the past -- all shift work away from the linear algebra to the sieve).  This means that back doors are not as big a concern.

If sieving attacks are the main concern, then regularly changing  the primes used would be a bigger boost to security.  Fixed primes, uses everywhere, mean that the huge cost of the sieve and solving the system of equations have an even bigger payoff.  Changing primes regularly minimizes an attackers gain from any possible sieve attack -- SNFS, more general, or other index calculus attacks which may be developed. 

Pocklington's theorem is not only an efficient test for this prime, but is a way to efficiently (if q is at least 1/2 the bits, then 2 exponentiations) test primality, but also quickly verify primality AND produces an element of order q (the same two exponentiations).
 
A. Johnston
Sent from my iPad

> On Apr 5, 2017, at 18:54, Travis Finkenauer <[e-mail]> wrote:
> 
> sympy.ntheory.isprime