Cryptography Reference
In-Depth Information
n
(mod
a
2
) given the
solution to the system of congruences via the Chinese remainder theorem, then
Since
b
2
so the first condition is satisfied in (C.6).
≡
a
2
(
b
2
n
), so (
b
2
n
)
/a
2
=
c
a
2
/
2,
−
−
∈
Z
, which is the second condition. If
b
≥
a
2
, and we have
<a
2
/
2, which is the last condition.
then replace
b
by
b
−
|
b
|
−
1
method, which we now present. The following is taken from [170]. The reader
needing a reminder of elliptic curve fundamentals may go to page 498 in Ap-
pendix A.
As mentioned earlier, Lenstra invented a generalization of Pollard's
p
C.7 The Elliptic Curve Method (ECM)
In this algorithm,
n
∈
N
is assumed to be composite, prime to 6, and not a
perfect power, and
r
∈
N
is a parameter. The goal is to split
n
.
(1)
(
Select and elliptic curve
): Choose a random pair (
E,P
) where
E
=
E
(
Z
/n
Z
) is an elliptic curve:
y
2
=
x
3
+
ax
+
b
and
P
is a point on
E.
Check that gcd(
n,
4
a
3
+27
b
2
) = 1. If not, then we have split
n
if 1
<g<n
,
and we may terminate the algorithm. Otherwise, we select another (
E,P
)
pair.
(2)
(
Choosing bounds
): Select
M
∈
N
and bounds
A,B
∈
N
such that the
canonical prime factorization for
M
is
M
=
j
=1
p
a
p
j
for small primes
j
p
1
<p
2
<
···
<p
≤
B
where
a
p
j
=
ln(
A
)
/
ln(
p
j
)
is the largest
exponent such that
p
a
j
j
≤
A
. Set
j
=
k
=1.
(3) (
Calculating multiple points
): Using (A.12) and (A.13) from page 499,
compute
p
j
P
.
(4) (
Computing the gcd
):
(a) If
p
j
P
≡
o (mod
n
), then set
P
=
p
j
P
, and reset
k
to
k
+1.
(i) If
k
a
p
j
, then go to step (3).
(ii) If
k>a
p
j
, then reset
j
to
j
+ 1, and reset
k
to
k
=1. If
j
≤
≤
,
then go to step (3). Otherwise go to step (5).
(b) If
p
j
P
o (mod
n
), then compute gcd(
m
2
,n
) for
m
2
in (A.13). If
n>g
, terminate the algorithm, since we have split
n
.If
g
=
n
,go
to step (5).
≡
(5) (
Selecting a new pair
): Set
r
=
r
−
1. If
r>
0, go to step (1). Otherwise,
terminate with “failure”.
Search WWH ::
Custom Search