Re: [Cfrg] Progress on curve recommendations for TLS WG

[Michael Hamburg <[e-mail]>]

> On Aug 16, 2014, at 11:56 PM, Andrey Jivsov <[e-mail]> wrote:
> 
> I looked at my implementation of modp reduction I did a few years ago for a fixed p. I used Barrett reduction.
> 
> At closer look I don't see why multiply+reduction mod p, for a random but fixed p, is 2n^2 + n. I got a corrected value for Barrett reduction below.

You can reduce one digit at a time.  Eg just cancel the top digit at a cost of one multiply to find the approximate factor plus n to multiply by p, then repeat.  It’s a little easier with Montgomery than with Barrett, since Montgomery always cancels the low digit out exactly.

This is why it’s a pain to reduce with Karatsuba, though.  I don’t know an easy way around it: you either reduce by several digits at a time and pay an extra cost like in your calculations, or you do one at a time but can’t use Karatsuba.

— Mike