security/nss/lib/freebl/mpi/doc/div.txt@6474c204b198
security/nss/lib/freebl/mpi/doc/div.txt
Wed, 31 Dec 2014 06:09:35 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Wed, 31 Dec 2014 06:09:35 +0100
- changeset 0
- 6474c204b198
- permissions
- -rw-r--r--
Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.
1 Division
3 This describes the division algorithm used by the MPI library.
5 Input: a, b; a > b
6 Compute: Q, R; a = Qb + R
8 The input numbers are normalized so that the high-order digit of b is
9 at least half the radix. This guarantees that we have a reasonable
10 way to guess at the digits of the quotient (this method was taken from
11 Knuth, vol. 2, with adaptations).
13 To normalize, test the high-order digit of b. If it is less than half
14 the radix, multiply both a and b by d, where:
16 radix - 1
17 d = -----------
18 bmax + 1
20 ...where bmax is the high-order digit of b. Otherwise, set d = 1.
22 Given normalize values for a and b, let the notation a[n] denote the
23 nth digit of a. Let #a be the number of significant figures of a (not
24 including any leading zeroes).
26 Let R = 0
27 Let p = #a - 1
29 while(p >= 0)
30 do
31 R = (R * radix) + a[p]
32 p = p - 1
33 while(R < b and p >= 0)
35 if(R < b)
36 break
38 q = (R[#R - 1] * radix) + R[#R - 2]
39 q = q / b[#b - 1]
41 T = b * q
43 while(T > L)
44 q = q - 1
45 T = T - b
46 endwhile
48 L = L - T
50 Q = (Q * radix) + q
52 endwhile
54 At this point, Q is the quotient, and R is the normalized remainder.
55 To denormalize R, compute:
57 R = (R / d)
59 At this point, you are finished.
61 ------------------------------------------------------------------
62 This Source Code Form is subject to the terms of the Mozilla Public
63 # License, v. 2.0. If a copy of the MPL was not distributed with this
64 # file, You can obtain one at http://mozilla.org/MPL/2.0/.
