# How does the code for scalar reduction work?

In this piece of code:

https://github.com/monero-project/monero/blob/master/src/crypto/crypto_ops_builder/ref10CommentedCombined/sc_reduce.c#L35

We reduce a scalar by mod l.

what is the significance of these numbers:

``````  s11 += s23 * 666643;
s12 += s23 * 470296;
s13 += s23 * 654183;
s14 -= s23 * 997805;
s15 += s23 * 136657;
s16 -= s23 * 683901;
``````

The constants 666643,470296...

• I've been trying to actually obtain the values of each limb corresponding to -q0. I can't figure out how this is done. I tried all sorts of tricks. I end up with values that are off-by-one values. For instance, I get 470297 when the expected value is 470296. I tried subtracting from 2^21, and such. Nothing works for me. What is the correct method for computing the limbs of -q0? Feb 9 at 8:52

The magic numbers are best explained here:

``````/**
* Lots of magic numbers :)
* To understand what's going on below, note that
*
* (1) q = 2^252 + q0 where q0 = 27742317777372353535851937790883648493.
* (2) s11 is the coefficient of 2^(11*21), s23 is the coefficient of 2^(^23*21) and 2^252 = 2^((23-11) * 21)).
* (3) 2^252 congruent -q0 modulo q.
* (4) -q0 = 666643 * 2^0 + 470296 * 2^21 + 654183 * 2^(2*21) - 997805 * 2^(3*21) + 136657 * 2^(4*21) - 683901 * 2^(5*21)
*
* Thus
* s23 * 2^(23*11) = s23 * 2^(12*21) * 2^(11*21) = s3 * 2^252 * 2^(11*21) congruent
* s23 * (666643 * 2^0 + 470296 * 2^21 + 654183 * 2^(2*21) - 997805 * 2^(3*21) + 136657 * 2^(4*21) - 683901 * 2^(5*21)) * 2^(11*21) modulo q =
* s23 * (666643 * 2^(11*21) + 470296 * 2^(12*21) + 654183 * 2^(13*21) - 997805 * 2^(14*21) + 136657 * 2^(15*21) - 683901 * 2^(16*21)).
*
* The same procedure is then applied for s22,...,s18.
*/
``````

If it's not yet clear, the constants 666643, 470296, 654183, -997805, 136657, -683901 are the 21-bit limbs of the 125-bit number -q0.

Proof (in python):

``````>>> limbs = [666643<<(0*21), 470296<<(1*21), 654183<<(2*21), -997805<<(3*21), 136657<<(4*21), -683901<<(5*21)]
>>> sum(limbs)
-27742317777372353535851937790883648493L
``````
• Do you also know what is happening on the previous lines, where s0 to s23 are loaded? There is a 5, 2,7,4,1,6,3 pattern of bit shifting to load up the s values Jan 14, 2019 at 9:07
• Yes. Loading 21 bits into each variable. Jan 14, 2019 at 12:39