I am working on 224-bit elliptic curve cryptography. In this 224-bit * 224-bit multiplication results 448-bit output. I am reducing 448-bit into prime field range( prime number $2^{224}-2^{96}+1$) using modulus operation. Can any tell me efficient modulus operation for remainder calculation? I am working on VHDL.


1 Answer 1


See section D.2.2 of FIPS 186-3. The modular reduction can be expressed as two additions and two subtractions of values which are assembled by concatenating selected 32-bit words of the 448-bit value which is to be reduced. Note that these additions and subtractions are modular, so you may have to mind some carries.

  • $\begingroup$ yes. i know that procedure. It is recommended by NIST standard Elliptic Curve. But if the prime number changes that formula won't work. Is any alternative way? In FIPS 186-3 , how can he able to computed the value, could you explain mathematics behind in that method? $\endgroup$
    – venkat
    Mar 18, 2013 at 11:13
  • 1
    $\begingroup$ @venkat Primes in ECC are often specifically chosen so they allow more efficient reductions. $\endgroup$ Mar 18, 2013 at 11:42
  • $\begingroup$ Aninteger c = (c13,..., c2, c1, c0) in base 2^32 with 0 ≤ c < 224-bit*224-bit OUTPUT: c mod p(224-bit) z1 = (c6, c5, c4, c3, c2, c1, c0), z2 = (c10, c9, c8, c7, 0, 0, 0), z3 = (0, c13, c12, c11, 0, 0, 0), z5 = (0, 0, 0, 0, c13, c12, c11), z4 = (c13, c12, c11, c10, c9, c8, c7),= Return(z1 + z2 + z3 − z4 − z5mod p224).this is algorithm what i supposed to explain. after 224-bit * 224-bit multiplication gives 448 -bit output. it will reduce into field range using prime number (2^224-2^96+1) using above algorithm. can you explain mathematical concept behind in this efficient reduction technique? $\endgroup$
    – venkat
    Mar 19, 2013 at 10:53

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.