[curves] The Pareto frontiers of sleeveless primes

[Mike Hamburg]

On 10/30/2014 06:58 AM, David Leon Gil wrote:
> On Thu, Oct 30, 2014 at 12:44 AM, Ben Harris <mail at bharr.is> wrote:
>> Are there recommended
>> limits on the small 'c' in Crandall primes? This list is only up to 32, but
>> many on the SafeCurves list are in the 100s.
> It's purely a matter of speed.
>
> I.e., large values of 'c' are all mainly due to targeting a specific
> field-size, rather than a speed/security-optimal field size.
>
> Most of the Crandalls in SafeCurves with large 'c' are due to Aranha
> et al.: http://eprint.iacr.org/2013/647
If you have more than log2 ((n-1)c + 1) + epsilon bits of headroom in
your n limbs, then you can implement the multiplication and reduction all
in one go without crossing limbs, and then do all the carry propagation.
If you have 2 more bits on top of that, you have to propagate carries
twice.

So to maximize efficiency, you want limbs close to the word size and c
small.

-- Mike