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


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.

  • $\begingroup$ 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$. $\endgroup$
    – fgrieu
    Commented Mar 5, 2014 at 11:55
  • 1
    $\begingroup$ @fgrieu I bet they want to do whatever Secp256k1 requires. $\endgroup$ Commented Mar 5, 2014 at 12:07
  • $\begingroup$ @CodesInChaos: not unlikely; if that is, no polynomial will be harmed in the making. $\endgroup$
    – fgrieu
    Commented Mar 5, 2014 at 12:40
  • $\begingroup$ 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. $\endgroup$
    – user12230
    Commented Mar 5, 2014 at 13:00
  • $\begingroup$ I can't understand "irreducible" and "weight is 36" in the question. That's a sure sign I should not answer. $\endgroup$
    – fgrieu
    Commented Mar 5, 2014 at 14:56

1 Answer 1


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).

  • $\begingroup$ Thank you. This was very useful and indeed allowed to speed up things a bit. For what it is worth, here is the code: $\endgroup$
    – user12230
    Commented Mar 11, 2014 at 9:21
  • $\begingroup$ Would you have a formal proof which shows this method works? $\endgroup$ Commented Mar 9, 2021 at 23:52
  • $\begingroup$ @HenryDorsettCase: more formal than the observation that $a 2^n + b \equiv ac + b \pmod{2^n-c}$? $\endgroup$
    – poncho
    Commented Mar 9, 2021 at 23:58
  • $\begingroup$ @poncho yes. or is it just observation that follows "Generalized Marsenne numbers" by Solinas? $\endgroup$ Commented Mar 10, 2021 at 7:07
  • $\begingroup$ oh, wait - that's an algorithm given by Crandall in '92, isn't? $\endgroup$ Commented Mar 10, 2021 at 10:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.