Cryptography Reference
In-Depth Information
the
ceiling
function, so that you take the integer closest to what is in between them, rounding “up”
(taking the opposite action as the floor function).
(b) Set
P
=
(p
e
)P
- that is, add
P
to itself
p
e
times.
Here,wemightfindafactor,g,ofa.How?Recall calculating theinverseofanumber(say,
x
)modulo
a. We find a number,
x
-1
, such that
x
-1
× +
kn
= 1. But, this operation only succeeds if the numbers
are relatively prime. If we perform the calculation (using one of the Euclidean algorithms), we will
have also calculated the GCD of
x
and a. If the GCD is not 1, then we have a factor of a. In that case,
we terminate the algorithm and return
g
, the GCD.
5. If we have failed to find a factor,
g
(via the GCD above), then we can either fail or try again with a new
curve or point, or both.
Furthermore,
g
is not guaranteed to be prime, but merely a factor.
3.3.6.1 Analysis of ECM
If
p
is the least prime dividing the integer
a
to be factored, then the expected time to find the factor is approx-
imately
The first term in this will typically dominate, giving a number a bit less than
e
p
.
In the worst-case scenario, when
a
is the product of two large and similar magnitude primes, then the running
time is approximately
This is going to be a bit less than
e
n
,
but not so much. In both cases, the average and worst case, these are still
exponential running times.
3.4 Subexponential Factoring Methods
The previous factoring methods were all exponential in running time. There are known methods that operate
much faster (in subexponential time). However, these algorithms are more complicated, since they all use really
nifty, math-heavy tricks to start to chip away at the running time and find factors fast.
Most subexponential factoring algorithms are based on Fermat's difference of squares method, explained
above. A few other important principles are also used.
If
x
,
y
are integers and
a
is the composite number we wish to factor, and
x
2
≡
y
2
(mod
a
) but
x
±
y
(mod
a
), then gcd(
x
-
y
,
a
) and gcd(
x
+
y
,
a
) are factors of
a.
3.4.1 Continued Fraction Factorization
The continued fraction factorization method is introduced in Reference [10]. The following explanation draws
on this paper, as well as the material in References [9] and [15].
Search WWH ::
Custom Search