Cryptography Reference
In-Depth Information
= 173) such that
t
∈
S
v
i,t
≡
√
n
0 (mod 2) for each
i
=0
,
1
,
2
,...,
11 is
S
=
{
0
,
18
,
−
23
. Thus,
}
x
t
=2
2
3
2
5
4
173
2
191
2
9062
2
x
2
(mod 30167)
,
≡
≡
t
∈
S
and
y
t
=2
2
7
2
11
2
17
2
41
2
16837
2
y
2
(mod 30167)
,
≡
≡
t
∈
S
so
y
2
x
2
16837
2
9062
2
25899 (mod 30167).
By computing both of the values, gcd(7775
,
30167) = 311 = gcd(
y
−
≡
−
≡
7775
·
−
x,n
)
·
and gcd(25899
,
30167) = 97 = gcd(
x
+
y,n
), we get that
n
= 30167 = 97
311.
t
x
t
y
t
v
t
0
173
−
2
·
7
·
17
(1
,
1
,
1
,
0
,
1
,
0
,
0
,
0
,
0
,
0
,
0
,
0)
−
−
·
1
172
11
53
(1
,
0
,
0
,
1
,
0
,
0
,
0
,
0
,
0
,
0
,
1
,
0)
−
5
168
−
29
·
67
(1
,
0
,
0
,
0
,
0
,
1
,
0
,
0
,
0
,
0
,
0
,
1)
5
178
37
·
41
(0
,
0
,
0
,
0
,
0
,
0
,
0
,
1
,
1
,
0
,
0
,
0)
−
−
·
·
6
167
2
17
67
(1
,
1
,
0
,
0
,
1
,
0
,
0
,
0
,
0
,
0
,
0
,
1)
7
180
7
·
11
·
29
(0
,
0
,
1
,
1
,
0
,
1
,
0
,
0
,
0
,
0
,
0
,
0)
11
184
7
·
17
·
31
(0
,
0
,
1
,
0
,
1
,
0
,
1
,
0
,
0
,
0
,
0
,
0)
7
4
14
187
2
·
(0
,
1
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0)
−
15
158
−
11
·
43
(1
,
0
,
0
,
1
,
0
,
0
,
0
,
0
,
0
,
1
,
0
,
0)
7
3
−
17
156
−
·
17
(1
,
0
,
1
,
0
,
1
,
0
,
0
,
0
,
0
,
0
,
0
,
0)
18
191
2
·
7
·
11
·
41
(0
,
1
,
1
,
1
,
0
,
0
,
0
,
0
,
1
,
0
,
0
,
0)
−
23
150
−
11
·
17
·
41
(1
,
0
,
0
,
1
,
1
,
0
,
0
,
0
,
1
,
0
,
0
,
0)
28
201
2
·
7
·
17
·
43
(0
,
1
,
1
,
0
,
1
,
0
,
0
,
0
,
0
,
1
,
0
,
0)
Some elementary linear algebra underlies the solution to a factorization prob-
lem using the QS as depicted in Example C.5. By ensuring that there are
k
+2
vectors v
t
in a
k
+ 1-dimensional vector space
k
+1
2
F
, we guarantee that there
is a linear dependence relation among the v
t
.
In other words, we ensure the
existence of the set
in step (3) of the algorithm such that congruence (C.5)
holds. There is no guarantee that
x
S
y
(mod
n
), but there are usually several
dependency relations among the v
t
, so there is a high probability that at least
one of them will yield an (
x,y
) pair such that
x
≡±
y
(mod
n
). The problem, of
course, is that for “large” smoothness bounds
B
, we need a lot of congruences
before we may be able to get these dependency relations.
For
k
as given in Footnote C.2, the asymp
totic running t
ime (see page 502),
≡±
of the quadratic sieve is
O
exp
(1 +
o
(1))
ln(
n
) ln(ln(
n
))
.
To split
n
∈
N
, with the QS, we consider a polynomial,
√
n
)
2
g
(
x
)=(
x
+
−
n,
Search WWH ::
Custom Search