Cryptography Reference
In-Depth Information
FIGURE 12.2
//Next approximation is computed by taking r-f(r)/f'(r)
r=r.subtract(r.multiply(r).subtract(n).divide
(r.multiply(two),BigDecimal.ROUND_UP));
//As long as our new approximation squared exceeds m, we continue to approximate
while (r.multiply(r).compareTo(n)>0) {
r=r.subtract(r.multiply(r).subtract(n).divide
(r.multiply(two),BigDecimal.ROUND_UP));
}
return r.toBigInteger(); //Method truncates any fractional part of a BigDecimal
}
We will test the method with the following applet, TestSQRTApplet, from the topic's
website. (See Figure 12.2.)
Once we have this square root finding method, writing a program to find factors using
Femat's method should be simple.
12.2
MONTE CARLO FACTORIZATION
Another method of factoring was developed by J. M. Pollard, who called it the Monte Carlo
method, due to the type of numbers generated in the method. Here we will not prove that
this works; we will only describe the algorithm.
Say
n
is composite, and that
p
is its smallest prime divisor. We wish to choose a sequence
of integers, say
m
0
,
m
1
,
m
2
, . . .,
m
k
such that their lnr's are distinct modulo
n
, but not all dis-
tinct modulo
. Though we will not prove the following, this happens when
•
k
is large compared to
√
p
,
•
k
is small compared to
√
n
, and
• the
m
i
(where 0
≤
i
≤
k
) are chosen randomly.
p
Search WWH ::
Custom Search