Cryptography Reference
In-Depth Information
and define,
v
(
a
−
bm
)=(
b
(0)
,b
(
q
r+1
)
,...,b
(
q
s
)). Finally set
v
(
a,b
)
≡
(
v
(
a
−
bα
)
,v
(
a
−
bm
)) (mod 2)
.
Hence,
v
(
a,b
) is a binary vector of length r + s +2.
For ease of elucidation, we make the simplifying assumption that if we find
a set
such that
(
a,b
)
∈
S
S
{
∈
Z
×
Z
}
=
(
a,b
)
: gcd(
a,b
)=1
v
(
a,b
)isthe
zero vector modulo 2, then both
(
a,b
)
∈
S
(
a
−
bm
) will be a square in
Z
and
(
a,b
)
∈
S
[
α
](see [191]for the means of dealing with
the obstructions when this is not the case). Hence, all we do is to sieve over
coprime integer pairs (
a,b
) with 0
<b
(
a
−
bα
) will be a square in
Z
B
until the above is achieved.
Then we are in the situation (C.9) and we proceed to factor
n
.
≤
B
,
|
a
|≤
Summary
In order not to waste time, we must first ensure that the number
n
that we
are trying to factor is indeed composite. One may apply a strong pseudoprime
test (see Appendix F). Also, see the deterministic primality test by the authors
of [6], which we present in Appendix F.3.
Once convinced of the compositness of
n
, perform trial division up to 10
4
,
then apply Pollard's rho method, which finds small factors rather quickly. Trial
division is applied first since Pollard's method has a slower running time than
trial division for the very small divisors, so it is worthwhile to apply the rho
method to a number whose small prime factors have been removed.
Secondly, many methods fail to detect when
n
is a perfect power, so we
must also rule out that possibility. If
n
=
m
e
, where
m,e
∈
N
and
e>
1, then
we can actually determine
m
and
e
as follows.
For each prime
p
≤
log
2
n
,
satisfying
n
=
r
p
, restricting attention to
do a binary search for
r
∈
N
2
(log
2
n
)
/p
+1
. This calculation may be accomplished in
O
((log
2
n
)
3
(log
2
(log
2
(log
2
n
)))) bit operations. Thus, this is a reasonable pre-
test for ensuring that we do not have such a power.
Once the above has been completed, use Pollard's
p
the range 2
≤
r
≤
1 method, followed
by Lenstra's ECM. The ECM takes more time than Pollard's rho method for
finding relatively small factors, so it may be used to advantage at this juncture.
If all the above fails, the big guns should be brought to bear on the problem.
This includes CFRAC, MPQS, and GNFS. Of course, all of this strategy depends
on the computing power available, the algorithms at hand, and other factors,
but all things being equal and having access to all of the above, then the strategy
should ultimately work modulo a suitable waiting period if the heavy machinery
mentioned here is employed. The running times given in this appendix provide
a good indicator of just how long one should expect to wait as your computer
executes its job.
−
Search WWH ::
Custom Search