FiloSottile / edwards25519

filippo.io/edwards25519 — A safer, faster, and more powerful low-level edwards25519 Go implementation.
https://filippo.io/edwards25519
BSD 3-Clause "New" or "Revised" License
139 stars 30 forks source link

How are 2^168 and 2^336 modulo l computed? #41

Closed DeviPrasad closed 9 months ago

DeviPrasad commented 9 months ago

First of all, thank you very much for the great post "A Wide Reduction Trick". I understood the basic idea, and the "trick". However, I'm not able to see how the 2^168 and 2^336 modulo l are computed. The sequence of four 64-bit values look totally strange when thinking about 1^168 (and of course, 2^336).

I tried many things; it's clear that I'm completely ignorant.

Would you mind describing how the values of scalarTwo168 and scalarTwo336 are worked out?

FiloSottile commented 9 months ago

Take 2^168, multiply by 2^256 to get in the Montgomery domain, reduce by l, split into little-endian 64-bit limbs.

>>> s = 2**168
>>> l = 2**252 + 27742317777372353535851937790883648493
>>> R = 2**256
>>> hex(s * R % l)
'0x6329a7ed9ce5a30a2c131b399411b7c38afddd6de59d5d75b8ab432eac74798'

Same with 2^336.