The following algorithm is for modular multiplication modulo a prime number p, xi represents the bit number "i" of the X input, Y is the second input.
i know how to implement this algorithm but i would like to understand it's functioning on bit level, like why do we check for even or odd and why do we add xiY or xiY +p and divide by 2 (bit-shift) consequently to the condition?
1: procedure R2MM(X, Y, p)
2: S ← 0
3: for i ← 0 to n − 1 do
4: if (S + xiY ) is even then
5: S ← (S + xiY )/2
6: else
7: S ← (S + xiY + p)/2
8: end if
9: end for
10: if S ≥ p then
11: S ← S − p
12: end if
13: end procedure
i did not find any source that explains this algorithm on bit level, only blind implementations of it.
Edit 1: this Paper1 seem to clarify my issue of understanding the algorithm, it enlightened me on some aspects but the mathematical nature of the explanation made it a bit complex to fully comprehend, i got that S is a sort of accumulator and that we add N on the odd case of Si to make it even so the dividing it by 2 makes it an integer, but i still don't get why we divide by 2, the answer is probably that induction proof but i don't see fully how, any explanation would be of great help.