Cryptography Reference
In-Depth Information
= (0,
has large prime factors (we will not prove
this), but should it happen, we can simply choose a base
n
) =
n
. It turns out that this is unlikely when
n
b
k
!
b
other than 2 when computing
1, and start over.
E
XAMPLE
.
We will attempt to find a factor of
n
= 632887. (Note that 632887 = 769
823,
and that 768 = 2
8
3, so that the smallest value of
k
for which 768|
k
! is
k
= 10. (To see this,
(2
3
)
(2
2
)
note that 10! = 10
9
8
7
6
5
4
3
2
1 = (2
5)
9
7
(2
3)
5
3
2
8
2
768.)
We start by choosing a random base, say
1 = 4275
3 = 4275
b
= 261482. We then proceed to compute the
r
i
b
i
!
modulo
least nonnegative residue
n
, for
i
= 1, 2, 3, . . . . When we have found a non-
trivial gcd of (
r
i
1,
n
), we have found a nontrivial divisor of
n
.
r
1
= 261482 (mod 632887)
r
2
=
r
1
2
155053 (mod 632887)
(
r
2
1,
n
) = 1
r
2
3
r
3
=
386889 (mod 632887)
(
r
3
1,
n
) = 1
r
4
=
r
3
4
r
4
n
181843 (mod 632887)
(
1,
) = 1
r
5
=
r
4
5
293940 (mod 632887)
(
r
5
1,
n
) = 1
r
6
=
r
5
6
630444 (mod 632887)
(
r
6
1,
n
) = 1
r
6
7
r
7
=
249467 (mod 632887)
(
r
7
1,
n
) = 1
r
8
=
r
7
8
234544 (mod 632887)
(
r
8
1,
n
) = 1
r
9
=
r
8
9
422180 (mod 632887)
(
r
9
1,
n
) = 1
r
9
10
) = 769
In the 10
th
step, we find that 769 is a nontrivial divisor of 632887, exactly as we expected,
since 768 divides 10!, but no smaller value of the factorial function.
r
10
=
582903 (mod 632887)
(
r
10
1,
n
E
XAMPLE
.
n
b
Here we try to factor
= 559374799933 starting with the base
= 557566181343.
The values have been placed in Table 12.6.
This says a factor of 559374799933 is found; namely, 740279. Apparently, this also says
559374799933 divides 23!, but no smaller value of the factorial function.
Java Algorithm
A method to extract factors using the
p
1 method follows. It is also
in the BigIntegerMath class.
public static BigInteger pMinusOneFactor(BigInteger n)
throws IllegalArgumentException {
if (n.compareTo(THREE)<=0)
throw new IllegalArgumentException(“Integer must be larger than three!”);
Random rand=new Random();
BigInteger power=BigInteger.valueOf(1);
Search WWH ::
Custom Search