Cryptography Reference
In-Depth Information
We notice that if
p
is prime and divides
A
2
n
, then
A
2
−
≡
n
(mod
p
), therefore
n
is a quadratic residue modulo
p
, hence (
p
)
=
1 when
p
is odd. Therefore we can
just pick
B
equal to
−
1, 2, and all prime numbers
p
lesser than
b
and for which
(
p
)
=
1.
We have already mentioned that a random integer within the order of magnitude of
n
is
b
-smooth with probability
u
−
u
where
u
log
n
log
b
. So by picking a totally random
A
mod
n
, we obtain a relation with probability
u
−
u
. The trick here (due to Carl Pomerance)
consists of increasing this probability by decreasing the order of magnitude of
A
mod
n
by picking
A
=
m
.
A
mod
n
is now within an order of magnitude of
√
n
,so
u
is
decreased by one half.
=
X
+
e
√
(1
+
o
(1)) log
n
log log
n
when
we carefully choose
b
, as for the ECM method (see Ref. [152]).
We can heuristically prove that the complexity is
O
726, the nearest integer to
the square root of
n
. The list of prime numbers of our factor basis is
As an example, we factorize
n
=
527773. We let
m
=
2
,
3
,
5
,
7
,
11
,
13
,
17
,
19
,
23
,
29
,
31
,
37
,
41
,
43
,
47
,
53
,
59
,
61
,
67
.
But
n
is a quadratic residue modulo
3
,
7
,
11
,
13
,
17
,
41
,
53
,
61
,
67
only. Therefore we set
B
={−
1
,
2
,
3
,
7
,
11
,
13
,
17
,
41
,
53
,
61
,
67
}
.Wenowtry
A
=
X
+
m
with
X
=
0
,
+
1
,
−
1
,
+
2
,
−
2
,
+
3
,
−
3
,...
and we test which
A
2
−
n
values are
b
-smooth. We have
m
2
−
=−
·
·
n
1
17
41
1)
2
2
2
3
3
+
−
=
·
·
(
m
n
7
1)
2
2
2
(
m
−
−
n
=−
1
·
·
3
·
179
2)
2
(
m
+
−
n
=
3
·
11
·
67
2)
2
(
m
−
−
n
=−
1
·
3
·
11
·
109
.
5)
2
2
2
3
3
(
m
+
−
n
=
·
·
61
.
7)
2
2
2
(
m
+
−
n
=
·
3
·
13
·
61
7)
2
2
2
(
m
−
−
n
=−
1
·
·
3
·
17
·
53
Search WWH ::
Custom Search