# Efficient algorithm for remainder calculation over prime field for ECC implementation?

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.

-

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.

-
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? – venkat Mar 18 '13 at 11:13
@venkat Primes in ECC are often specifically chosen so they allow more efficient reductions. – CodesInChaos Mar 18 '13 at 11:42
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? – venkat Mar 19 '13 at 10:53