Higher Level Algorithms
This chapter discusses the various higher level algorithms that are required to complete a well-rounded multiple precision integer package. These routines are less performance oriented than the algorithms in Chapters 5, 6, and 7, but are no less important.
The first section describes a method of integer division with remainder that is universally well known. It provides the signed division logic for the package. The subsequent section discusses a set of algorithms that allow a single digit to be the 2nd operand for a variety of operations. These algorithms serve mostly to simplify other algorithms where small constants are required. The last two sections discuss how to manipulate various representations of integers; for example, converting from an mp_int to a string of character.
8.1 Integer Division with Remainder
Integer division aside from modular exponentiation is the most intensive algorithm to compute. Like addition, subtraction, and multiplication, the basis of this algorithm is the long–hand division algorithm taught to schoolchildren. Throughout this discussion several common variables will be used. Let x represent the divisor and y represent the dividend. Let q represent the integer quotient 
y/x
and let r represent the remainder r=y – x y/x. The following simple algorithm will be used to start the discussion (Figure 8.1).
As children we are taught this very simple algorithm for the case ofβ=10. Almost instinctively, several optimizations are taught for which their reason of existing are never explained. For this example, let y=5471 represent the dividend and x=23 represent the divisor.
To find the first digit of the quotient the value of k must be maximized such that kxβt is less than or equal to y, and simultaneously (k+1)xβt is greater than y. Implicitly,k is the maximum value the t′th digit of the quotient may have. The habitual method used to find the maximum is to “eyeball” the two numbers, typically only the leading digits, and quickly estimate a quotient. By only using leading digits, a much simpler division may be used to form an educated guess at what the value must be. In this case,k=54/23=2 quickly arises as a possible solution. Indeed, 2xβ2=4600 is less than y=5471, and simultaneously (k+1)xβ2=6900 is larger than y. As a result,kβ2 is added to the quotient which now equals q=200, and 4600 is subtracted from y to give a remainder of y=841.
This process is repeated to produce the quotient digit k=3, which makes the quotient q=200+3β=230 and the remainder y=841 −3xβ=181. Finally, the last iteration of the loop produces k=7, which leads to the quotient q=230+7=237 and the remainder y=181 −7x=20. The final quotient and remainder found are q=237 and r=y=20, which are indeed correct since 237 · 23 + 20 = 5471 is true.
8.1.1 Quotient Estimation
As alluded to earlier, the quotient digit k can be estimated from only the leading digits of both the divisor and dividend. When p leading digits are used from both the divisor and dividend to form an estimation, the accuracy of the estimation rises as p grows. Technically speaking, the estimation is based on assuming the lower ||y||− p and ||x||− p lower digits of the dividend and divisor are zero.
The value of the estimation may off by a few values in either direction and in general is fairly correct. A simplification [1, pp. 271] of the estimation technique is to use t+1 digits of the dividend and t digits of the divisor, particularly when t=1. The estimate using this technique is never too small. For the following proof, let t=||y|| −1 and s=||x||−1 represent the most significant digits of the dividend and divisor, respectively.
Theorem. The quotient 
is greater than or equal to 
Proof. Adapted from [1, pp. 271]. The first obvious case is when 
, in which case the proof is concluded since the real quotient cannot be larger. For all other cases 
and 
. The latter portion of the inequality – xs + 1 arises from the fact that a truncated integer division will give the same quotient for at most xs −1 values. Next, a series of inequalities will prove the hypothesis.
This is trivially true since x ≥ xsβs. Next, we replace 
by the previous inequality for 
.
By simplifying the previous inequality the following inequality is formed.
which proves that 
and by consequence 
which concludes the proof.
8.1.2 Normalized Integers
For the purposes of division, a normalized input is when the divisor’s leading digit xn is greater than or equal toβ/2. By multiplying both x and y by 
, the quotient remains unchanged and the remainder is simply j times the original remainder. The purpose of normalization is to ensure the leading digit of the divisor is sufficiently large such that the estimated quotient will lie in the domain of a single digit. Consider the maximum dividend (β −1) · β + (β −1) and the minimum divisorβ/2.
At most, the quotient approaches 2β; however, in practice this will not occur since that would imply the previous quotient digit was too small.
8.1.3 Radix-β Division with Remainder
Algorithm mp_div. This algorithm will calculate the quotient and remainder from an integer division given a dividend and divisor. The algorithm is a signed division and will produce a fully qualified quotient and remainder (Figure 8.2).
First, the divisor b must be non-zero, which is enforced in step 1. If the divisor is larger than the dividend, the quotient is implicitly zero and the remainder is the dividend.
After the first two trivial cases of inputs are handled, the variable q is set up to receive the digits of the quotient. Two unsigned copies of the divisor y and dividend x are made as well. The core of the division algorithm is an unsigned division and will only work if the values are positive. Now the two values x and y must be normalized such that the leading digit of y is greater than or equal toβ/2. This is performed by shifting both to the left by enough bits to get the desired normalization.
At this point, the division algorithm can begin producing digits of the quotient. Recall that maximum value of the estimation used is 2β − 2/β, which means that a digit of the quotient must be first produced by another means. In this case,y is shifted to the left (step 10) so that it has the same number of digits as x. The loop in step 11 will subtract multiples of the shifted copy of y until x is smaller. Since the leading digit of y is greater than or equal toβ/2, this loop will iterate at most two times to produce the desired leading digit of the quotient.
Now the remainder of the digits can be produced. The equation 
is used to fairly accurately approximate the true quotient digit. The estimation can in theory produce an estimation as high as 2β − 2/β, but by induction the upper quotient digit is correct (as established in step 11) and the estimate must be less thanβ.
Recall from section 8.1.1 that the estimation is never too low but may be too high. The next step of the estimation process is to refine the estimation. The loop in step 13.5 uses xiβ2 + xi–1β + xi–2 and qi–t–1(ytβ+ yt–1) as a higher order approximation to adjust the quotient digit.
After both phases of estimation the quotient digit may still be off by a value of one1. Steps 13.6 and 13.7 subtract the multiple of the divisor from the dividend (similar to step 3.3 of algorithm 8.1)and then add a multiple of the divisor if the quotient was too large.
Now that the quotient has been determined, finalizing the result is a matter of clamping the quotient, fixing the sizes, and de-normalizing the remainder. An important aspect of this algorithm seemingly overlooked in other descriptions such as that of Algorithm 14.20 HAC [2, pp. 598] is that when the estimations are being made (inside the loop in step 13.5), that the digits yt–1,xi–2 and xi–1 may lie outside their respective boundaries. For example, if t= 0 or i = 1 then the digits would be undefined. In those cases, the digits should respectively be replaced with a zero.
The implementation of this algorithm differs slightly from the pseudo-code presented previously. In this algorithm, either of the quotient c or remainder d may be passed as a NULL pointer, which indicates their value is not desired. For example, the C code to call the division algorithm with only the quotient is
Lines 109 and 113 handle the two trivial cases of inputs, which are division by zero and dividend smaller than the divisor, respectively. After the two trivial cases all of the temporary variables are initialized. Line 148 determines the sign of the quotient, and Line 148 ensures that both x and y are positive.
The number of bits in the leading digit is calculated on Line 151. Implicitly, an mp_int with r digits will require lg(β)(r−1) + k bits of precision that when reduced modulo lg(β) produces the value of k. In this case,k is the number of bits in the leading digit, which is exactly what is required. For the algorithm to operate,k must equal lg(β) −1, and when it does not, the inputs must be normalized by shifting them to the left by lg(β) −1 − k bits.
Throughout, the variables n and t will represent the highest digit of x and y, respectively. These are first used to produce the leading digit of the quotient. The loop beginning on Line 184 will produce the remainder of the quotient digits.
The conditional “continue” on Line 187 is used to prevent the algorithm from reading past the leading edge of x, which can occur when the algorithm eliminates multiple non-zero digits in a single iteration. This ensures that xi is always non-zero since by definition the digits above the i′th position x must be zero for the quotient to be precise2.
Lines 215, 216, and 223 through 225 manually construct the high accuracy estimations by setting the digits of the two mp_int variables directly.
1.1 Single Digit Helpers
This section briefly describes a series of single digit helper algorithms that come in handy when working with small constants. All the helper functions assume the single digit input is positive and will treat them as such.
8.2.1 Single Digit Addition and Subtraction
Both addition and subtraction are performed by “cheating” and using mp_set followed by the higher level addition or subtraction algorithms. As a result, these algorithms are substantially simpler with a slight cost in performance.
Algorithm mp_add_d. This algorithm initiates a temporary mp_int with the value of the single digit and uses algorithm mp_add to add the two values together (Figure 8.3).
Unlike the simple description in Figure 8.3, the implementation is more complicated. This is because we want to avoid the cost of building a new mp_int temporary variable just for a simple addition.
First, we handle the case of negative numbers (Line 33). If the number is negative, and sufficiently large, then we subtract instead. After this point, we are going to add a single digit (Line 66), and then propagate the carry upwards (lines 71 through 78).
8.2.2 Single Digit Multiplication
Single digit multiplication arises enough in division and radix conversion that it ought to be implemented as a special case of the baseline multiplication algorithm. Essentially, this algorithm is a modified version of algorithm s_mp_mul_digs where one of the multiplicands only has one digit.
Algorithm mp_mul_d. This algorithm quickly multiplies an mp_int by a small single digit value. It is specially tailored to the job and has minimal overhead. Unlike the full multiplication algorithms, this algorithm does not require any significant temporary storage or memory allocations (Figure 8.4).
In this implementation, the destination c may point to the same mp_int as the source a, since the result is written after the digit is read from the source. This function uses pointer aliases tmpa and tmpc for the digits of a and c, respectively.
8.2.3 Single Digit Division
Like the single digit multiplication algorithm, single digit division is also a fairly common algorithm used in radix conversion. Since the divisor is only a single digit, a specialized variant of the division algorithm can be used to compute the quotient.
Algorithm mp_div_d. This algorithm divides the mp_int a by the single mp_digit b using an optimized approach. Essentially in every iteration of the algorithm another digit of the dividend is reduced and another digit of quotient produced. Provided b <β, the value of 
after step 7.1 will be limited such that 
(Figure 8.5).
If the divisor b is equal to three a variant of this algorithm is used, which is mp_div_3. It replaces the division by three with a multiplication by β/3 and the appropriate shift and residual fixup. In essence, it is much like the Barrett reduction from Chapter 7.
Like the implementation of algorithm mp_div, this algorithm allows either the quotient or remainder to be passed as a NULL pointer to indicate the respective value is not required. This allows a trivial single digit modular reduction algorithm, mp_mod_d, to be created.
The division and remainder on lines 85 and 86 can be replaced often by a single division on most processors. For example, the 32-bit x86 based processors can divide a 64-bit quantity by a 32-bit quantity and produce the quotient and remainder simultaneously. Unfortunately, the GCC compiler does not recognize that optimization and will actually produce two function calls to find the quotient and remainder, respectively.
8.2.4 Single Digit Root Extraction
Finding the n′th root of an integer is fairly easy as far as numerical analysis is concerned. Algorithms such as the Newton-Raphson approximation (8.6) series will converge very quickly to a root for any continuous function f(x).
In this case, the n′th root is desired and f(x) =xn – a, where a is the integer of which the root is desired. The derivative of f(x) is simply f′(x) =nxn–1. Of particular importance is that this algorithm will be used over the integers, not over a more continuous domain such as the real numbers. As a result, the root found can be above the true root by few and must be manually adjusted. Ideally, at the end of the algorithm the n′th root b of an integer a is desired such that bn ≤ a.
Algorithm mp_n_root. This algorithm finds the integer n′th root of an input using the Newton-Raphson approach. It is partially optimized based on the observation that the numerator of 
can be derived from a partial denominator.
That is, at first the denominator is calculated by finding xb−1. This value can then be multiplied by x and have a subtracted from it to find the numerator. This saves a total of b −1multiplications by t1 inside the loop (Figure 8.6).
The initial value of the approximation is t 2 = 2, which allows the algorithm to start with very small values and quickly converge on the root. Ideally, this algorithm is meant to find the n′th root of an input where n is bounded by 2 ≤ n ≤ 5.
8.3 Random Number Generation
Random numbers come up in a variety of activities, from public key cryptography to simple simulations and various randomized algorithms. Pollard-Rho factoring, for example, can make use of random values as starting points to find factors of a composite integer. In this case, the algorithm presented is solely for simulations and not intended for cryptographic use.
Algorithm mp_rand. This algorithm produces a pseudo-random integer of b digits. By ensuring that the first digit is non-zero, the algorithm also guarantees that the result has at least b digits. It relies heavily on a third-part random number generator, which should ideally generate uniformly all of the integers from 0 toβ −1 (Figure 8.7).
8.4 Formatted Representations
The ability to emit a radix-n textual representation of an integer is useful for interacting with human parties. For example, the ability to be given a string of characters such as “114585” and turn it into the radix-β equivalent would make it easier to enter numbers into a program.
8.4.1 Reading Radix-n Input
For the purposes of this text we will assume that a simple lower ASCII map (Figure 8.8) is used for the values of from 0 to 63 to printable characters. For example, when the character “N” is read it represents the integer 23. The first 16 characters of the map are for the common representations up to hexadecimal. After that, they match the “base64” encoding scheme suitably chosen such that they are printable. While outputting as base64 may not be too helpful for human operators, it does allow communication via non–binary mediums.
Algorithm mp_read_radix. This algorithm will read an ASCII string and produce the radix-β mp_int representation of the same integer. A minus symbol “-” may precede the string to indicate the value is negative; otherwise, it is assumed positive. The algorithm will read up to sn characters from the input and will stop when it reads a character it cannot map. The algorithm stops reading characters from the string, which allows numbers to be embedded as part of larger input without any significant problem (Figure 8.9).
8.4.2 Generating Radix-n Output
Generating radix-n output is fairly trivial with a division and remainder algorithm.
Algorithm mp_toradix. This algorithm computes the radix-r representation of an mp_int a. The “digits” of the representation are extracted by reducing successive powers of 
the input modulo r until rk > a. Note that instead of actually dividing by rk in each iteration, the quotient 
is saved for the next iteration. As a result, a series of trivial n × 1 divisions are required instead of a series of n × k divisions. One design flaw of this approach is that the digits are produced in the reverse order (see 8.11). To remedy this flaw, the digits must be swapped or simply “reversed” (Figure 8.10).
Figure 8.11 is an example of the values in algorithm mp_toradix at the various iterations.
