Cryptography Reference
In-Depth Information
Step 1. The decomposition of
n −
1
as
n −
1=2
k
q
with odd
q
is carried out by
the function
twofact_l()
. The value
n −
1
is retained in
d_l
.
cpy_l (d_l, n_l);
dec_l (d_l);
k = (USHORT)twofact_l (d_l, q_l);
p=0;
i=0;
isprime = 1;
do
{
Step 2. The bases
p
are formed from the differences stored in the field
smallprimes[]
. For the exponentiation we use the Montgomery function
wmexpm_l
,
since the base is always of type
USHORT
and, after the pretest with the division sieve
of the prime candidate
n_l
, always odd. If afterwards the power in
x_l
is equal to
1
, then the next test iteration begins.
p += smallprimes[i++];
wmexpm_l (p, q_l, x_l, n_l);
if (!EQONE_L (x_l))
{
j=0;
Step 3. Squaring, as long as
x_l
is different from
±
1
and
k
−
1
iterations have not
yet been executed.
while (!EQONE_L (x_l) && !equ_l (x_l, d_l) && ++j < k)
{
msqr_l (x_l, x_l, n_l);
}
if (!equ_l (x_l, d_l))
{
isprime = 0;
}
}
}
