So. Motivated by prior posts by Michael Hamburg and Daniel Bernstein, I made up a list of "good primes" for ECC.
General criteria: 80 <= n = ceil(log2(p)) <= 1024.1 The prime must be 3 mod 4, so that all Montgomery curves are isogenous to an untwisted Edwards curve. (Note: this criterion excludes 2^255-19, which is 1 mod 4.)
I considered all ridinghood primes and all Crandall primes with c < 64 in this range; there are 10 ridinghood primes and 52 Crandall primes with minimal c in this range.
(The choice of nail-length is debatable, of course, as well as considering Ridinghoods that require irrational/split radices relatively quickly.)
The (very messy) script I used to generate these results can be found at: https://gist.github.com/coruus/da494f6b77f65946332b
I calculated the Pareto frontiers2 for security strength versus three quantities:
- number of nailed limbs, as ceil(n / 58)
- number of quadwords in a compressed representation, ceil((n-3)/64)
- number of bytes in a compressed representation, ceil((n-3)/8)
Pareto frontier: n, #limbs=ceil(n/58)
2^114 - 2^57 - 1 #limbs= 2 len= 14
2^174 - 17 #limbs= 3 len= 22
2^226 - 5 #limbs= 4 len= 28
2^285 - 9 #limbs= 5 len= 36
2^336 - 17 #limbs= 6 len= 42
2^389 - 21 #limbs= 7 len= 49
2^450 - 2^225 - 1 #limbs= 8 len= 56
2^521 - 1 #limbs= 9 len= 65
2^563 - 9 #limbs=10 len= 70
2^607 - 1 #limbs=11 len= 76
2^664 - 17 #limbs=12 len= 83
2^729 - 9 #limbs=13 len= 91
2^810 - 5 #limbs=14 len=101
These results lend support to djb's assertion that top performance is a fairly rigid criterion, taking the number of limbs as a rough proxy for performance.
#limbs is obviously a very rough proxy; is there a decent generic formula for number of ops for Crandalls and Ridinghoods?
Pareto frontier: n, ceil((n-3) / 64)
2^130 - 5 #limbs= 3 qrlen= 16 len= 16
2^189 - 25 #limbs= 4 qrlen= 24 len= 24
2^251 - 9 #limbs= 5 qrlen= 32 len= 31
2^322 - 2^161 - 1 #limbs= 6 qrlen= 40 len= 40
2^369 - 25 #limbs= 7 qrlen= 48 len= 46
2^450 - 2^225 - 1 #limbs= 8 qrlen= 56 len= 56
2^489 - 21 #limbs= 9 qrlen= 64 len= 61
2^563 - 9 #limbs=10 qrlen= 72 len= 70
2^607 - 1 #limbs=11 qrlen= 80 len= 76
2^706 - 5 #limbs=13 qrlen= 88 len= 88
2^729 - 9 #limbs=13 qrlen= 96 len= 91
2^810 - 5 #limbs=14 qrlen=104 len=101
This is the Pareto frontier for storing Edward curve keys, assuming a compressed representation, and an 8-byte alignment requirement.
The ridinghood 2^450 - 2^225 - 1 comes out well here as well; I'm curious whether it is any slower than 2^448-2^224-1.
Pareto frontier: n, ceil((n-3)/8)
2^90 - 2^45 - 1 len= 11
2^96 - 17 len= 12
2^107 - 1 len= 13
2^114 - 2^57 - 1 len= 14
2^118 - 5 len= 15
2^130 - 5 len= 16
2^137 - 13 len= 17
2^141 - 9 len= 18
2^152 - 17 len= 19
2^166 - 5 len= 21
2^174 - 17 len= 22
2^189 - 25 len= 24
2^198 - 17 len= 25
2^206 - 5 len= 26
2^216 - 2^108 - 1 len= 27
2^226 - 5 len= 28
2^243 - 9 len= 30
2^251 - 9 len= 31
2^285 - 9 len= 36
2^322 - 2^161 - 1 len= 40
2^336 - 17 len= 42
2^369 - 25 len= 46
2^389 - 21 len= 49
2^416 - 2^208 - 1 len= 52
2^450 - 2^225 - 1 len= 56
2^468 - 17 len= 59
2^480 - 2^240 - 1 len= 60
2^489 - 21 len= 61
2^521 - 1 len= 65
2^537 - 9 len= 67
2^550 - 5 len= 69
2^563 - 9 len= 70
2^607 - 1 len= 76
2^664 - 17 len= 83
2^699 - 9 len= 87
2^706 - 5 len= 88
2^708 - 2^354 - 1 len= 89
2^717 - 25 len= 90
2^729 - 9 len= 91
2^810 - 5 len=101
This is the Pareto frontier for Edwards curve key bytelengths, assuming a compressed representation, and no alignment requirement. (As, e.g., is common for internet protocols.)
This obviously constrains choice of primes relatively little; still, there are only 40 good byte-lengths.
And, finally, a list based on the efficiency with which 58-bit limbs are used for a given quadword-length:
len: prime eff=(n/(ceil(n/58)*58), eff >= 0.9
2*8: 2^114 - 2^57 - 1 (0.98)
3*8: 2^174 - 17 (1.00)
4*8: 2^226 - 5 (0.97)
5*8: 2^285 - 9 (0.98)
6*8: 2^336 - 17 (0.97)
7*8: 2^450 - 2^225 - 1 (0.97)
8*8: 2^489 - 21 (0.94)
9*8: 2^521 - 1 (1.00)
And bytelength:
len: prime eff=(n/(ceil(n/58)*58), eff >= 0.9
13: 2^107 - 1 (0.92)
14: 2^114 - 2^57 - 1 (0.98)
21: 2^166 - 5 (0.95)
22: 2^174 - 17 (1.00)
27: 2^216 - 2^108 - 1 (0.93)
28: 2^226 - 5 (0.97)
36: 2^285 - 9 (0.98)
40: 2^322 - 2^161 - 1 (0.93)
42: 2^336 - 17 (0.97)
46: 2^369 - 25 (0.91)
49: 2^389 - 21 (0.96)
56: 2^450 - 2^225 - 1 (0.97)
60: 2^480 - 2^240 - 1 (0.92)
61: 2^489 - 21 (0.94)
65: 2^521 - 1 (1.00)
Again, further support for performance being a fairly rigid criterion.
The complete list of Crandall and Hamburg primes considered:
Ridinghoods: p = 2^n - 2^n/2 - 1 2^90 - 2^45 - 1 2^100 - 2^50 - 1 2^114 - 2^57 - 1 2^216 - 2^108 - 1 2^322 - 2^161 - 1 2^416 - 2^208 - 1 2^448 - 2^224 - 1 2^450 - 2^225 - 1 2^480 - 2^240 - 1 2^708 - 2^354 - 1
Crandalls: p = 2^n - c, c < 256 && p%4==3, !E(c' < c && is_prime(2^n-c')) 2^89 - 1 2^93 - 25 2^96 - 17 2^104 - 17 2^105 - 13 2^107 - 1 2^110 - 21 2^118 - 5 2^125 - 9 2^127 - 1 2^129 - 25 2^130 - 5 2^137 - 13 2^141 - 9 2^150 - 5 2^152 - 17 2^165 - 25 2^166 - 5 2^174 - 17 2^189 - 25 2^198 - 17 2^206 - 5 2^212 - 29 2^226 - 5 2^243 - 9 2^251 - 9 2^285 - 9 2^321 - 9 2^336 - 17 2^369 - 25 2^389 - 21 2^413 - 21 2^414 - 17 2^444 - 17 2^468 - 17 2^488 - 17 2^489 - 21 2^521 - 1 2^537 - 9 2^550 - 5 2^563 - 9 2^607 - 1 2^664 - 17 2^699 - 9 2^706 - 5 2^717 - 25 2^729 - 9 2^808 - 17 2^810 - 5 2^848 - 17 2^869 - 21