Cryptography Reference
In-Depth Information
Let
a
=(
a
m
+
n
−
1
a
m
+
n
−
2
...a
0
)
B
and
b
=(
b
n
−
1
b
n
−
2
...b
0
)
B
be two
natural numbers, represented to the base
B
, and for
b
n
−
1
, the most-significant
digit of
b
,wehave
b
n
−
1
>
0
. We are looking for the quotient
q
and remainder
r
such that
a
=
qb
+
r
,
0
≤ r<b
.
Following the long division above, for the calculation of
q
and
r
a quotient
digit
q
j
:=
R/b <B
is returned in each step, where in the first step
R
=(
a
m
+
n
−
1
a
m
+
n
−
2
...a
k
)
B
is formed from the most-significant digit of
the dividend with the largest
k
for which
1
≤R/b <B
holds (in the above
example at the start we have
m
+
n −
1=3+3
−
1=5
,
k
=2
, and
R
= 3549
).
Then we will set
R
:=
R − q
j
b
, where as a control for the correctness of the
quotient digit
q
j
the condition
0
≤ R<b
must be satisfied. Then
R
is replaced
by the value
RB
+
(next digit of the dividend), and the next quotient digit is
again
R/b
. The division is complete when all digits of the dividend have been
processed. The remainder of the division is the last calculated value of
R
.
For programming this procedure we must repeatedly determine, for two large
numbers
R
=(
r
n
r
n
−
1
...r
0
)
B
and
b
=(
b
n
−
1
b
n
−
2
...b
0
)
B
R/b
<B
,
with
the quotient
Q
:=
R/b
(
r
n
=0
is a possibility). Here we take from Knuth
the given approximation
q
of
Q
, which is computed from the leading digits of
R
and
b
.
Let
q
:= min
r
n
B
+
r
n
−
1
b
n
−
1
,B−
1
.
(4.1)
If
b
n
−
1
≥R/b
,thenfor
q
(see [Knut], Section 4.3.1, Theorems A and B), we
have
q
q
. Under the favorable assumption that the leading digit of the
divisor is sufficiently large in comparison to
B
, then as an approximation to
Q
,
q
is at most too large by
2
and is never too small.
By scaling the operands
a
and
b
this can always be achieved. We choose
d>
0
such that
db
n
−
1
≥B/
2
−
2
≤
Q
≤
, set
a
:=
ad
=(
a
m
+
n
a
m
+
n
−
1
...a
0
)
B
, and set
b
:=
bd
=
b
n
−
1
b
n
−
2
...b
0
B
. The choice of
d
is then made in such a way that
the number of digits of
b
never increases in comparison to that of
b
. In the above
notation it is taken into account that
a
possibly contains one more digit than
a
(if
this is not the case, then we set
a
m
+
n
=0)
. In any case, it is practical to choose
d
asapowerof
2
, since then the scaling of the operands can be carried out with
simple shift operations. Since both operands are multiplied by a common factor,
the quotient is unchanged; we have
a/b
=
a/b
.
The choice of
q
in (4.1), which we want to apply to the scaled operators
a
, respectively
r
, and
b
, can be improved with the following test to the extent
that
q
=
Q
or
q
=
Q
+1
: If from the choice of
q
we have
b
n
−
2
ˆ
q>
r
n
B
+
r
n
−
1
qb
n
−
1
B
+
r
n
−
2
,then
q
is reduced by
1
and the test is
repeated. In this way we have taken care of all cases in which
q
is too large by
2
at
the outset, and only in very rare cases is
q
still too large by
1
(see [Knut], Section
4.3.1, Exercises 19, 20). The latter is determined from the subtraction of the partial
−
