[Cryptography] IETF discussion on new ECC curves.

[Bear]

On Sat, 2014-07-26 at 14:32 -0400, Phillip Hallam-Baker wrote:

> Curve 25519 is close to 256 and its easy to make the argument. But
> there isn't a convenient prime near to 2^512. When we come to choosing
> curve E521 its a gut check sort of thing...

Hmm, let me monkey together a tiny bit o' code: 
Expmod, in scheme:

(define expmod
  (lambda (base exp mod)
    (remainder
     (cond ((= exp 0) 1)
       ((even? exp) (square (expmod base (/ exp 2) mod)))
       (else (* base (expmod base (- exp 1) mod))))
     mod)))
;Value: expmod

and now that I've got expmod, the Fermat primality test:  (yes, I 
know you have to verify the results to rule out carmichael numbers). 

(define fermat-prime? (lambda (n m)
  (let fermat-tests ((i m))
     (if (= i 0) #t
      (let ( (a (+ 1 (random (- n 1)))) )
        (if (= (expmod a n n) a) (fermat-tests (- i 1))
        #f))))))
;Value: fermat-prime?

And now that I've got fermat-prime, findpr to find the first prime 
less than a given number:  

(define findpr (lambda (x n) 
   (let ((fp (fermat-prime? x n)) 
         (over (> n 100)))
       (if (and fp over) x 
           (if fp (findpr x (* 2 n)) 
                  (findpr (- x 1) n))))))
;Value: findpr

And now that I've got findpr, let me see just how far below 2^512 you 
have to go to find a prime:

(- (expt 2 512) (findpr (expt 2 512) 5))
;Value: 569

So the first fermat-test prime number below 2^512 is 2^512 - 569? It's 
a nice nothing-up-my-sleeve number, anyhow. What's the problem with it?
Are there some requirements I don't know?

			Bear