Cryptography Reference
In-Depth Information
Example C.6
Let
n
= 923
and select
(
E,P
)=(
y
2
=
x
3
+2
x
+9
,
(0
,
3))
. Then
gcd(4
9
2
,
923) = 1
, so we choose
B
=4
, based upon
(C.7)
, and let
A
=3
,M
=6=2
2
3
+27
·
·
·
3=
p
1
·
p
2
. Now, using
(A.12)-(A.13)
, with
p
1
=2
,we
calculate
(9
−
1
,
27
−
1
)
p
1
P
= 2(0
,
3)
≡
−
82
·
≡
(718
,
373)
≡
o (mod
n
)
.
Thus we set
P
= (718
,
373)
and compute
p
2
P
=3
P
≡
2
P
+
P
≡
(505
,
124) + (718
,
373)
≡
o (mod
n
)
.
Thus, we have that a denominator in
(A.13)
is not prime to
n
. In fact, the
calculation of
m
for
4
P
+2
P
yields
m
= (124
−
373)
/
(505
−
718) = 83
/
71
, and
gcd(923
,
71)=71
. Indeed,
n
=13
·
71
, and we have split
n
.
What Example C.6 illustrates is that the failure of the existence of a modular
inverse for some
m
in the calculations may lead to a factor of
n
. Another way
of saying this is that the group law for multiplication actually fails in
Z
since
n
is not prime and this allows us to get the factor. Indeed, it is somewhat
inaccurate in the ECM algorithm to say that
p
j
P
Z
/n
≡
o (mod
n
), when in fact it
is
p
j
P
≡
o (mod
p
) where
p
is the factor for which we were searching. However,
this is legitimate since we were, in a sense, assuming
n
to be prime and doing
the calculations as if it were so, in the
hope
that the calculations would “break
down” with an undefined denominator for some value of
m
in (A.13).
A significant advantage of the ECM is that its running time is highly reliant
on the factor,
p
n
, found. Hence, one of the most useful means of employing
the ECM is for finding “small” prime factors in a number
n
, which is too large
to find
all
its factors. The reasons behind this are as follows. Assuming that
p
is the smallest prime dividing
n
, the expected running time of the ECM is
known (under certain plausible assumptions) to be
O
(exp(
(2 +
o
(1)) ln
p
(ln ln
p
))
ln
2
n
)
.
·
This may be used in practice to select a smoothness bound
B
in step (2) of the
algorithm as
B
= exp(
ln
p
(ln ln
p
)
/
2)
.
(C.7)
Sin
c
e we do not know
p
in advance, we may nevertheless select (for
p
) the value
√
n
. In this case, it is estimated that one out of every
B
iterations will be
successful in splitting
n
.
The worst-case scenario for the ECM is when
n
is an RSA modulus, in which
case we have that the expected running time is
O
exp(
(2 +
o
(1)) ln
n
(ln ln
n
)
=
O
n
√
(2+
o
(1))(ln ln
n
)
/
ln
n
.
This being said, it is not surprising that ECM is most successful at splitting
non
-RSA moduli,
usually
finding prime factors of less than 40 decimal digits in
large composite numbers.
Search WWH ::
Custom Search