Cryptography Reference
In-Depth Information
if (i%2==0) {
g=m[i].subtract(m[i/2]).gcd(n);
if (g.compareTo(ONE)>0&&g.compareTo(n)<0) return g;
}
}
return null;
}
This method is unsatisfactory for integers having truly “large” factors (say, greater than
10
15
). You can verify this by testing the method with numbers having factors of this size;
the method starts to fail at around this point. Recall that the length of the sequence
k
should
be large compared to
√
p
. In the previous case,
k
= 100000, and
√
p
=
√
900383347
30006.39, which is why the method succeeded in finding the factor. But for factors exceed-
ing, say, 2
40
,
k
would need to be at least as high as 2
20
, and will thus require storage space
for around a million BigIntegers. This is already beginning to test the capacity of some
machines, and factors of much larger size are common in modern cryptography.
12.3
THE POLLARD
p
1 METHOD OF FACTORIZATION
This method of factorization was also developed by J. M. Pollard. It can be effective in
finding large factors
p
if the choice of
p
is such that the integer
p
1 consists of only small
prime factors. This is certainly not unusual, and in fact is quite common. It may seem strange
to you that the factorization of
p
1 can help us find the factor
p
, but it can.
Suppose
n
is a large composite integer, and that
n
has a factor
p
such that (
p
1)|
k
! for
some
k
. Now, if the prime factorization of
p
1 consists entirely of small prime factors, this
number
k
will not be excessively large (and
k
! will be computable).
Now, by Fermat's Little Theorem (FLT), we have
2
p
1
1 (mod
p
)
and since (
p
1)|
k
! for some integer
k
, we have
k
! = (
p
1)
q
for some integer
q
. This then
yields
2
k
!
= 2
(
p
1)
q
= (2
(
p
1)
)
q
1
q
= 1 (mod
p
).
(FLT is used here.)
This says that
p
|(2
k
!
1). Now, let
Z
be the least nonnegative residue of 2
k
!
1 mod-
ulo
n
.
(2
k
!
If
n
1)
we have
ni
, for some integer
i
.
Note, now that
p
|
Z
, since it divides both 2
k
!
Z
= (2
k
!
1)
1, and
n
. Thus, we see that a divisor of
n
can be found simply by computing (
Z
,
n
). Should
Z
and
n
not be relatively prime; that is,
(
Z
,
n
) =
d
> 1, then
d
is a nontrivial factor of
n
.
Note that if
n
|(2
k
!
0
(mod
n
), and computing the gcd of
Z
and
n
would only yield the trivial factor
n
since (
Z
,
n
)
1), the
p
1 method will fail, since then we would have
Z
Search WWH ::
Custom Search