For multi-digit integers signed magnitude number representation is beneficial. The binary length of the result is also calculated at each operation (without significant extra cost), and pointers show the position of the most and least significant bit in memory.

Addition is done from right to left (from the least- to the most significant bits), the usual way.

Subtraction needs a scan of the operand bits from left to right, to find the first different pair. They tell the sign of the result. The leading equal bits need not be processed again, and the right-to-left subtraction from the larger number leaves no final borrow. This way subtraction is of the same speed as addition, like with 2’s complement arithmetic.

Comparisons can be done by scanning the bits from left to right, too. For uniform random inputs the expected number of bit operations is constant, less than: 1·½+2·¼+3·^{1}/_{8} …= 2.

Comparisons to 0, 1 or 2^{k} take constant time also in the worst case, if the head and tail pointers have been kept updated.

3.Modular Inverse Algorithms

We consider all three Euclidean-type algorithm families commonly used: the extended versions of the right-shift-, the left-shift- and the traditional Euclidean - algorithm. They all gradually reduce the length of their operands in an iteration, maintaining some invariants, which are closely related to the modular inverse.

3.1

U m; V a;

R 0; S 1;

while ( V > 0) {

if (U_{0} = 0) {

U U/2;

if (R_{0} = 0) R R/2;

else R (R+m)/2;

}

else if(V_{0} = 0) {

V V/2;

if (S_{0} = 0) S S/2;

else S (S+m)/2;

}

else // U, V odd

if (U > V) {

U U – V; R R – S;

/**/ if (R < 0) R R + m;}

else {

V V – U; S S – R;

/**/ if (S < 0) S S + m;}

}

if (U > 1) return 0;

while (R > m) R R - m;

while (R < 0) R R + m;

return R; // a^{-1} mod m

Figure 1. Right-shift binary algorithm

Binary Right-shift: Algorithms RS
At the modular inverse algorithm based on the right-shift binary extended GCD (variants of the algorithm of M. Penk, see in [1], exercise 4.5.2.39 and [24]), the modulus m must be odd. The trailing 0-bits from two internal variables U and V (initialized to the input a, m) are removed by shifting them to the right, then their difference replaces the larger of them. It is even, so shifting right removes the new trailing 0-bits (Figure 1.).

Repeat these until V = 0, when U = GCD(m,a). If U > 1, there is no inverse, so we return 0, which is not an inverse of anything.

In the course of the algorithm two auxiliary variables, R and S are kept updated. At termination R is the modular inverse.

3.1.1Modification: Algorithm RS1

The 2 instructions marked with “/**/” in Figure 1. keep R and S nonnegative (unsigned arithmetic) and also assure that they don't grow too large (the subsequent subtraction steps decrease the larger absolute value). These instructions are slow and not necessary otherwise: the intermediate values of R and S do not get too large (at most 1 extra bit), but they make the two final correction while loops unnecessary (R > m or R < 0 are prevented).

Handling negative values and fixing the final result is easy, so it is advantageous if instead of the marked instructions, we only check at the add-halving steps (R^{ }(R+m)/2 and S^{ }(S+m)/2), whether R or S was already larger (or longer) than m, and add or subtractm such that the result becomes smaller (shorter). These steps cost no additional work beyond choosing ‘+’ or ‘−’ and, if |R| ≤ 2m was beforehand, we get |R| ≤ m, the same as at the simple halving of R^{ }^{ }R/2 and S^{ }^{ }S/2. If |R| ≤ m and |S| ≤ m, |R−S| ≤ 2m (the length could increase by one bit) but these instructions are always followed by halving steps, which prevent R and S to grow larger than 2m during the calculations. (See code details at the plus-minus algorithm below.)

3.1.2Even Modulus

This algorithm cannot be used for RSA key generation, because m must be odd (to ensure that either R or R±m is even for the subsequent halving step). We can go around the problem by swapping the role of m and a (amust be odd, if m is even, otherwise there is no inverse). The algorithm returns m^{−1} mod a, such that m·m^{−1} + k'·a = 1, for some negative integer k'. k' ≡ a^{−1} mod m, easily seen if we take both sides of the equation mod m. It is simple to compute the smallest positive k ≡ k' mod m:

k = a^{−1} mod m = m + (1− m·m^{−1})_{/}a.

As we saw before, the division is fast with calculating only the MS half of m·m^{−1}, plus a couple of guard digits to get an approximate quotient, to be rounded to the nearest integer.

Unfortunately there is no trivial modification of the algorithm to handle even moduli directly, because at halving only an integer multiple of the modulus can be added without changing the result, and only adding an odd number can turn odd intermediate values to even. Fortunately, the only time we need to handle even moduli in cryptography is at RSA key generation, which is so slow anyway (requiring thousands of modular multiplications for the primality tests), that this black box workaround does not cause a noticeable difference in processing time.

An alternative was to perform the full extended GCD algorithm, calculating both factors c and d: [g,c,d] = xCGD(m,a), such that the greatest common divisor g = c·m+d·a [10]. It would need extra storage for two factors, which are constantly updated during the course of the algorithm and it is also slower than applying the method above transforming the result of the modular inverse algorithm with swapped parameters.