# Fast modular reduction

I am looking at ways to speed up modular reduction for the polynomial

$$2^{256}-2^{32}-2^9-2^8-2^7-2^6-2^4-1$$

I have read the paper "Generalized Mersenne numbers" by J.A. Solinas, but it does not seem to list this form of polynomial as a candidate for fast modular reduction (see section 10).

Using the definitions in that paper, this polynomial would seem to be a) proper (second largest degree is negative), b) irreducible c) has an odd constant term (-1)

Its weight is 36.

I could not find any other specific reference in the literature.

So my question is: is this a candidate for fast modular reduction using Solinas suggested method?

Other possible reference is this master thesis: https://crysp.uwaterloo.ca/software/gmnt/gmz_mcs_thesis.pdf . However, the examples and explanations appear to be drawn directly from the Paper by Solinas.

• Please confirm you are seeking reduction modulo the (prime) integer $p=2^{256}-2^{32}-2^9-2^8-2^7-2^6-2^4-1$ (and working in $\mathbb Z_p$), rather than considering reduction modulo a polynomial as stated (and working in $\text{GF}({2^{256}})$ with reduction polynomial $p$). I do not use irreducible for prime in the integer context. Hint: $\lfloor x/p\rfloor$ is close to (and can't be less than) $\lfloor x/{2^{256}}\rfloor$. – fgrieu Mar 5 '14 at 11:55
• @fgrieu I bet they want to do whatever Secp256k1 requires. – CodesInChaos Mar 5 '14 at 12:07
• @CodesInChaos: not unlikely; if that is, no polynomial will be harmed in the making. – fgrieu Mar 5 '14 at 12:40
• Trying to lean on elliptic curve crypto using secpk256k1 as an example (why not ?). Indeed, I am searching for a way to speed up modular reduction modulo that prime, not the polynomial as stated. For reference, I have updated the question with the weight of the polynomial. – user12230 Mar 5 '14 at 13:00
• I can't understand "irreducible" and "weight is 36" in the question. That's a sure sign I should not answer. – fgrieu Mar 5 '14 at 14:56

If you want to reduce integers modulo that specific prime (and I assume you have checked whether $$p = 2^{256}-2^{32}-2^9-2^8-2^7-2^6-2^4-1$$ is prime or not), I would suggest you don't use the Solinas algorithms, but instead a different one geared towards modulii of the form $$2^n - c$$ for small $$c$$.

The identity underlying this operation is actually fairly simple:

$$a 2^n + b \equiv ac + b \pmod{2^n-c}$$

For you, $$n=256$$ and $$c = 2^{32} + 2^9 + 2^8 + 2^7 + 2^6 + 2^4 + 1$$

Here is how this would work; you take your 512 bit number $$a2^n + b$$ (and if you do the modulus operation immediately after each internal multiply, you never have to deal with an integer larger than 512 bits), and you compute:

$$a'2^n + b' = ac + b$$

This operation takes the successive words of $$a$$ (scanning from the lsword towards the msword), multiples each word by the 33 bit constant $$c$$, and adds in the corresponding word of $$b$$. You call the first 256 bits of this operation $$b'$$ (remember, this generates results starting at the lsword), and the last 33 bits of the result $$a'$$.

You then do it again, taking $$a'$$, multiplying it by $$c$$ (which results in at most a 66 bit value), and adding it to $$b'$$.

The result of that has a small probability of being greater than $$p$$; check if so, and subtract $$p$$ if necessary.

There, you're done. This would work fairly well on a 64 bit processor; it's less convenient on a 32 bit processor (because $$c$$ doesn't fit in a 32 bit word).

• Thank you. This was very useful and indeed allowed to speed up things a bit. For what it is worth, here is the code: – user12230 Mar 11 '14 at 9:21