Cryptography Reference
In-Depth Information
{
*pptr_l = (USHORT)(carry = (ULONG)*bptr_l * (ULONG)*bptr_l +
(ULONG)*pptr_l + (ULONG)(USHORT)(carry >> BITPERDGT));
pptr_l++;
*pptr_l = (USHORT)(carry = (ULONG)*pptr_l + (carry >> BITPERDGT));
}
All the rest follows in analogy to multiplication.
SETDIGITS_L (p_l, DIGITS_L (a_l) << 1);
RMLDZRS_L (p_l);
if (DIGITS_L (p_l) > (USHORT)CLINTMAXDIGIT)
/* overflow ? */
{
ANDMAX_L (p_l);
/* reduce modulo (Nmax + 1) */
OFL = E_CLINT_OFL;
}
cpy_l (pp_l, p_l);
return OFL;
}
The run time for squaring is, with
O
n
2
, likewise quadratic in the number
of digits of the operators, but with
n
(
n
+1)
/
2
elementary multiplications it is
about twice as fast as multiplication.
4.2.3 Do Things Go Better with Karatsuba?
The antispirit of multiplication and division deconstructed everything and
then focused only on a specific part of the whole.
—Sten Nadolny (trans. Breon Mitchell),
God of Impertinence
As announced, we shall now consider a method of multiplication named for the
Russian mathematician A. Karatsuba, who has published several variants of it
(See [Knut], Section 4.3.3). We assume that
a
and
b
are natural numbers with
n
=2
k
digits to base
B
,sothatwecanwrite
a
=(
a
1
a
0
)
B
k
and
b
=(
b
1
b
0
)
B
k
with digits
a
0
and
a
1
, respectively
b
0
and
b
1
, to base
B
k
. Were we to multiply
a
and
b
in the traditional manner, then we would obtain the expression
ab
=
B
2
k
a
1
b
1
+
B
k
(
a
0
b
1
+
a
1
b
0
)+
a
0
b
0
,
