Cryptography Reference
In-Depth Information
modulo
r
(which is the case for a negligible fraction of
x
's),
x
t
!
1 mod
n
will be a
multiple of
p
but not a multiple of
q
, so the gcd is nontrivial. More precisely, this will
always work for integers
n
such that
−
there exists a prime factor
p
of
n
such that all prime factors of
p
−
1 are lesser
than
B
,
there exists a prime factor
q
of
n
such that one prime factor
r
of
q
−
1 is larger
than
B
log
2
n
.
In other cases, the algorithm may never work. For instance, when all prime factors
p
of
n
are such that the largest prime factor
r
of
p
1 is the same,
x
t
!
will certainly
simultaneously vanish modulo all prime factors of
n
. For instance, for
n
−
=
133
×
2
2
331
=
44023,
p
=
133 is such that
p
−
1
=
×
3
×
11 and
q
=
331 is such that
q
−
1
=
2
×
3
×
5
×
11. It is easy to see that the smallest factorial number which is
a multiple of
p
1. This means that for any initial
x
whose
multiplicative orders in
Z
p
and
Z
q
are both multiple of 11 (which is the case for most
of the original
x
),
x
t
!
will simultaneously vanish modulo
p
and modulo
q
, which gives
us no chance to split
n
with this algorithm. These cases are however quite pathological.
−
1 is 11!, just like for
q
−
We give the same example as for the rho method:
n
=
18923. (Note that
p
=
127
3
2
2
2
and
q
=
149 are such that
p
−
1
=
2
×
×
7 and
q
−
1
=
×
37, so
r
=
37 is
large, and
p
−
1is
B
-smooth for
B
=
7.) We pick
x
=
2347. We obtain
i
=
1
x
=
2347
gcd
=
1
i
=
2
x
=
1816
gcd
=
1
i
=
3
x
=
4072
gcd
=
1
i
=
4
x
=
14891
gcd
=
1
i
=
5
x
=
18431
gcd
=
1
i
=
6
x
=
7247
gcd
=
1
i
=
7
x
=
13590
gcd
=
127
which yields
p
.
7.2.3
The Elliptic Curves Method (ECM)
1 algorithm consists of making hidden computations in a
Z
p
group
of smooth order. Computations in this group are hidden by computations in
Z
n
.We
can generalize this algorithm by using other groups, following an idea due to
Hen-
drik Lenstra
(see Ref. [114]). For instance, by picking
a
The Pollard
p
−
Z
n
, we can consider the
elliptic curve
E
a
,
b
in
Z
p
by doing all computations modulo
n
since the modulo
p
computations are just “hidden” in the modulo
n
ones. The order of this group is a
random number within the
p
,
b
∈
2
√
p
range. If this order happens to be
B
-smooth,
we can apply exactly the same algorithm within a complexity of
+
1
±
(
B
) arithmetic op-
erations. The success of this approach thus corresponds to the probability that the
order of the
E
a
,
b
mod
p
group is
B
-smooth for random
a
and
b
, which is estimated to
O
Search WWH ::
Custom Search