## 3.2.1Justification

The reduction of the temporary variables is now done by shifting left the intermediate results U and V, until they have their MS bits in the designated *n*-th bit position (which is the MS position of the larger of the original operands). Performing a subtraction clears this bit, reducing the binary length. The left-shifts introduce spurious factors, 2^{k}, for the GCD, but tracking the number of trailing 0 bits (*u* and *v*) allows the determination of the true GCD. (For a rigorous proof see [12].)
We start with U = *m*, V = *a*, R = 0, S = 1, *u = v = *0. In the course of the algorithm there will be at least *u* and *v* trailing 0-bits in U and V, respectively. In the beginning

GCD(U_{/}2^{min(}^{u,v}^{)},V_{/}2^{min(}^{u,v}^{)}) = GCD(*m*,*a*) (2)

If U or V is replaced by U−V, this relation remains true. If both U and V had their most significant (*n*-th) bit = 1, the above subtraction clears it. We chose the one from U and V to be updated, which had the smaller number of trailing 0-bits, say it was U. U then gets doubled until its most significant bit gets to the *n*-th bit position again, and *u*, the number of trailing 0's, is incremented in each step.

If *u* ≥ *v* was before the doubling, min(*u,v*) does not change, but U doubles. Since GCD(*m*,*a*) is odd (there is no inverse if it is not 1), GCD(2·U_{/}2^{min(}^{u,v}^{)},V_{/}2^{min(}^{u,v}^{)}) = GCD(*m*,*a*) remains true. If* u* < *v* was before the doubling, min(*u,v*) increases, leaving U_{/}2^{min(}^{u,v}^{)} unchanged. The other parameter V_{/}2^{min(}^{u,v}^{)} was even, and becomes halved. It does not change the GCD, either.

In each subtraction-doubling iteration either *u* or *v* (the number of trailing known 0's) is increased. U and V are never longer than *n*-bits, so *u* and *v* ≤ *n*, and eventually a single 1-bit remains in U or V (or one of them becomes 0, showing that GCD(*m,a*) > 1). It guaranties, that the procedure stops in at most ||*a*||+||*m*|| iterations, with U or V = 2^{n}^{−1} or 0.

In the course of the algorithm:

U_{/}2^{min(}^{u,v}^{)} ≡ R*a* mod *m*, V_{/}2^{min(}^{u,v}^{)} ≡ S*a* mod *m*. (3)

At subtraction steps (U−V)_{/}2^{min(}^{u,v}^{)} ≡ (R−S)·*a* mod *m*, so (3) remains true after updating the corresponding variables: U or V ← U−V, R or S ← R−S.

At doubling U and incrementing *u*, if* u* < *v* was before the doubling, min(*u,v*) increases, so U_{/}2^{min(}^{u,v}^{)} and R remains unchanged. V_{/}2^{min(}^{u,v}^{)} got halved, so it is congruent to (S_{/}2)·*a* mod *m*, therefore S has to be halved to keep (3) true. This halving is possible (V is even), because S has at least *v−u* trailing 0's (can be proved by induction).

At doubling U and incrementing *u*, if* u* ≥ *v* was before the doubling, min(*u,v*) does not change. To keep (3) true R has to be doubled, too (which also proves that it has at least *v−u* trailing 0's).

Similar reasoning shows the correctness of handling R and S when V is doubled.

At the end we get either U = 2^{u} or V = 2^{v}, so one of U_{/}2^{min(}^{u,v}^{)} or V_{/}2^{min(}^{u,v}^{)} is 1, and GCD(*m*,*a*) is the other one. If the inverse exists, GCD(*m*,*a*) = 1 and we get from (3) that either 1 ≡ R*a* mod *m* or 1 ≡ S*a* mod *m*. After making R or S of the right magnitude, it is the modular inverse *a*^{−1} mod *m*.

Another induction argument shows that R and S does not become larger than 2*m* in the course of the algorithm, otherwise the final reduction phase of the result to the interval [1, *m*−1] could take a lot of calculation. []

**Share with your friends:**