Cryptography Reference
In-Depth Information
The prime numbers are computed by successive addition of the numbers stored
in
smallprimes[]
and stored in
bv
. The first prime that serves as a divisor is
3
. We
use the code of the fast routine for division by a
USHORT
(see Section 4.3).
rv = 0;
bv += smallprimes[i];
for (aptr_l = MSDPTR_L (a_l); aptr_l >= LSDPTR_L (a_l); aptr_l--)
{
qv = (USHORT)((rhat = ((((ULONG)rv) << BITPERDGT) + (ULONG)*aptr_l)) / bv);
rv = (USHORT)(rhat - (ULONG)bv * (ULONG)qv);
}
}
while (rv != 0 && ++i <= no_of_smallprimes);
If an actual divisor was found (
rv == 0
and
bv
=
a_l
; otherwise,
a_l
itself is
prime!), this is returned. If
a_l
is itself a small prime, then 1 is returned. Otherwise,
0 is returned.
if (0 == rv)
}
if (DIGITS_L (a_l) == 1 && *LSDPTR_L (a_l) == bv)
}
bv = 1;
}
/* else: result in bv is a prime factor of a_l */
}
else /* no factor of a_l was found */
}
bv = 0;
}
return bv;
}
The function
sieve_l()
can be used for splitting off prime factors under
65536 from
CLINT
objects. To enable this, the macro
SFACTOR_L(n_l)
is defined
in
flint.h
, which uses the call
sieve_l(n_l, NOOFSMALLPRIMES)
to test divide
n_l
by the primes stored in
smallprimes[]
;
SFACTOR_L()
returns the same value
as
sieve_l()
. By repeated calls to
SFACTOR_L()
with subsequent division by the
factors found, integers below
2
32
, that is, integers that can be represented by the
standard integer types, can be completely factored. If no factor is found, then we
are dealing with a prime number.
