Проблема с пониманием алгоритма Монтгомери

Question

Возникла необходимость разобраться в алгоритме Монтгомери. При изучении статьи на википедии (https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9C%D0%BE%D0%BD%D1%82%D0%B3%D0%BE%D0%BC%D0%B5%D1%80%D0%B8) столкнулся с проблемой, конкретно в данном выражении:

Почему данное равенство верно?

Согласно написанному до этого в статье:

Куда пропадает mod n при подстановке в равенство и . Заранее благодарен за ответ

Answer 1

Потому что

((a mod n) * (b mod n)) mod n = (a*b) mod n

mod n - это по сути взятие остатка при делении на n. Если a=kn+q и b=ln+r, то первая часть превращается в

q*r mod n

а вторая

(kn+q)*(ln+r) mod n = (n*(kln+ql+kr)+ q*r) mod n = q*r mod n