Answer: My ring R contains 2255×10 − 19, which represents 0 in Z/(2255 − 19).
I will reduce polynomial products modulo 2255×10 – 19 to eliminate the coefficients of x10, x11, etc.
With radix 225 , the coefficient of x10 could not be eliminated.
With radix 226, coefficients would have to be multiplied by 2519 rather than just 19, and the results would not fit into an fp register.
There are a few things to unpack here.
Remember that we’re turning polynomials in to numbers by evaluating them at 1.
So when x = 1, 2255×10 – 19 = p = 2255 – 19, which is the zero in the integers mod 2255 – 19.
If we were using base (radix) 225 , the largest number we could represent with a 9th degree polynomial with the restrictions above would be 2250 , so we’d need a 10th degree polynomial; we couldn’t eliminate terms containing x10.
I don’t yet see why working with radix 226 would overflow an fp register.
If you do see why, please leave an explanation in the comments.
Related postsNaming elliptic curvesCurve1174Curve secp256k1[1] When a cryptographic method has an unjustified parameter, it invites suspicion that the parameter was chosen to create an undocumented back door.
This is not the case with Curve25519.
For example, why does it use p = 2255 – 19?.It’s efficient to use a prime close to a large power of 2, and this p is the closes prime to 2255.
The coefficient 486662 is not immediately obvious, but Bernstein explains in his paper how it was the smallest integer that met his design criteria.
.. More details