# [curves] The Pareto frontiers of sleeveless primes

David Leon Gil coruus at gmail.com
Sun Oct 26 14:15:28 PDT 2014

```# Introduction

So. Motivated by prior posts by Michael Hamburg and Daniel Bernstein,
I made up a list of "good primes" for ECC.

## Criteria for primes

General criteria: 80 <= n = ceil(log2(p)) <= 1024.[^bitlen] 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.

[^bitlen]: For regular ECC: need b >> 160; for hyperelliptic crypto:
need b > 80; for some exotic stuff (using, e.g., large cofactors or
constructed curves), the bitlengths > 521 may be of some use.

(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

-dlg

# Results

I calculated the Pareto frontiers[^pareto] 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]: Pareto frontier here means the hull of a two-dimensional
cost function.

## Pareto frontier for strength versus number of 58-bit limbs

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 for strength versus quad-aligned length

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

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 for strength versus length

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.

## Efficiency of used limbs, by byte-length

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.

# Appendix

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
```