Can anyone explain why a sloppy modular multiplication is used? The 3rd step is missing, otherwise there exist probability of an incorrect result. Or is it proven that only 2 steps were sufficient (I doubt it)?
Since no one answered, I will assume it's taken for granted that the multiplication used by JLP is correct (2-folding reduction steps). However, according to page 15 of this research paper:
https://eprint.iacr.org/2021/1151.pdfunder the analysis of "Sloppy reduction" it is proven that unless a correctness check is performed, then you need a 3rd reduction step.
Otherwise, the modular multiplication reduction has a chance (around one in 2**193) to be incorrect, because:
Thus, if sloppy reduction is applied to a randomly chosen number in the interval [0, R2 − 1], the probability of an incorrect result is about r(r−1) / 2N
There is a missing potential carry that is assumed it can never happen, after the 2nd reduction. And no one can explain it.I do recall that JLP is using projective coordinates inside his modular multiplication implementation (this is the same for VanitySearch).
In such a coordinate system, a different variable holds the divisor that's accumulated during the multiplication steps of the other two variables, so that reduction can be done much much later (as it is still expensive, even if you use heavily optimized algos like binary GCD and 2x52 legs).