Cryptography Reference
In-Depth Information
The values
(
−
1)
(
a
2
1
)
/
8
in steps 2 and 3 are best
computed with the aid of a prepared table.
1
)
/
8
and
(
−
1)
(
b
2
−
−
•
1)
(
a
−
1)(
b
−
1)
/
4
•
The value
(
k
in step 4 can be efficiently determined with
the C expression
if(a&b&2)k=-k
, where
&
is bitwise AND.
−
·
In both cases the explicit computation of a power can be avoided, which of course
has a positive effect on the total run time.
We would like to clarify the first tip with the help of the following considera-
tions: If
k
in step 2 is set to the value
(
−
1)
(
a
2
−
1
)
/
8
,then
a
is odd. The same holds
for
b
in step 3. For odd
a
we have
2
|
(
a −
1)
4
|
(
a
+1)
and
or
4
|
(
a −
1)
2
|
(
a
+1)
,
and
−
1
.Thus
(
−
1)
(
a
2
1
)
/
8
is an
so that 8 is a divisor of
(
a −
1)(
a
+1) =
a
2
−
integer. Furthermore, we have
(
−
1)
(
a
2
1
)
/
8
=(
−
1)
(
(
a
mod8)
2
1
)
/
8
(this can
−
−
be seen by placing the representation
a
=
k
8+
r
in the exponent). The
exponent must therefore be determined only for the four values
a
mod 8 =
±
1
and
·
±
3
, for which the results are
1
,
−
1
,
−
1
,and
1
. These are placed in a vector
{
0
,
1
,
0
, −
1
,
0
, −
1
,
0
,
1
}
,sothatbyknowing
a
mod 8
one can access the value
of
(
−
1)
(
(
a
mod8)
2
1
)
/
8
. Observing that
a
mod 8
can be represented by the
expression
a&7
, where again
&
is binary AND, then the calculation of the power
is reduced to a few fast CPU operations. For an understanding of the second tip
we note that
(
a
&
b
&
2)
−
=0
if and only if
(
a
−
1)
/
2
and
(
b
−
1)
/
2
, and hence
(
a −
1)(
b −
1)
/
4
, are odd.
Finally, we use the auxiliary function
twofact_l()
, which we briefly introduce
here, for determining
v
and
b
in step 2, for the case that
b
iseven,aswellasin
the analogous case for the values
v
and
a
in step 3. The function
twofact_l()
decomposes a
CLINT
value into a product consisting of a power of two and an odd
factor.
decompose a
CLINT
object
a
=2
k
u
with odd
u
Function:
Syntax:
int twofact_l (CLINT a_l, CLINT b_l);
a_l
(operand)
Input:
b_l
(odd part of
a_l
)
Output:
k
(logarithm to base 2 of the two-part of
a_l
)
Return:
