Cryptography Reference
In-Depth Information
Let
B
={−
1
,
2
,
3
,
5
}
. Taking
x
=
43
,
44
,
45
,
46 one finds the following factorisations
of
x
2
−
N
:
x
2
(mod
N
)
e
2
6
43
−
·
3
(1, 6, 1, 0 )
44
Not 5-smooth
2
4
45
−
(1,4,0,0)
5
2
46
3
·
(0,0,1,2)
Taking
e
=
e
1
+
e
2
+
e
3
=
(2
,
10
,
2
,
2) gives all coefficients even. Putting every-
2
5
thing
together,
we
set
X
=
43
·
45
·
46
≡
1247 (mod
N
)
and
Y
=−
1
·
·
3
·
5
≡
1561 (mod
N
). One can check that
X
2
Y
2
≡
(mod
N
) and that gcd(
X
−
Y,N
)
=
157.
√
kN
Exercise 15.2.10
Show that in the quadratic sieve one can also use values
x
=
+
i
where
k
∈ N
is very small and
i
=
0
,
1
,
−
1
,
2
,
−
2
,....
Exercise 15.2.11
Show that using sieving and fast linear algebra, but not restricting to
values
x
2
(mod
N
)ofsize
N
1
/
2
+
o
(1)
, gives an algorithm with heuristic expected running
±
time of
L
N
(1
/
2
,
√
2
+
o
(1)) bit operations as
N
→∞
.
Exercise 15.2.12
A subexponential algorithm is asymptotically much faster than a
O
(
N
1
/
4
) algorithm. Verify that if
N
2
1024
then
N
1
/
4
2
256
, while
L
N
(1
/
2
,
2)
2
197
=
=
≈
2
98
.
5
.
and
L
N
(1
/
2
,
1)
≈
The best proven asymptotic complexity for factoring integers
N
is
L
N
(1
/
2
,
1
+
o
(1))
bit operations. This result is due to Pomerance and Lenstra [
343
].
15.2.3 Summary
We briefly highlight the key ideas in the algorithms of this section. The crucial concept of
smooth elements of the group (
)
∗
arises from considering an integer modulo
N
as
Z
/N
Z
an element of
Z
. The three essential properties of smooth numbers that were used in the
algorithm are:
1. One can efficiently decompose an element of the group as a product of smooth elements,
or determine that the element is not smooth.
2. The probability that a random element is smooth is sufficiently high.
3. There is a way to apply linear algebra to the relations obtained from smooth elements
to solve the computational problem.
We will see analogues of these properties in the algorithms below.
There are other general techniques that can be applied in most algorithms of this type. For
example, the linear algebra problems are usually sparse and so the matrices and algorithms
should be customised for this. Another general concept is “large prime variation”, which,
