Cryptography Reference
In-Depth Information
Each of these algorithms provides the same result. What is this result? What is the complexity
of each of these algorithms?
log
n. Infer
that the k-th prime is equivalent in magnitude to k
log
k, and that the sum of the inverses of prime
numbers smaller than n is equivalent to
log log
n.
Hint: We admit that the number of prime integers smaller than n is equivalent to n
/
Exercise 7.3.
Factor
2
32
−
1
,
2
64
−
1
,
3
32
−
1
.
Show that
2
8
1
and
2
16
+
+
1
are prime.
Factor
2
32
+
1
and
2
64
+
1
by any method.
Exercise 7.4.
Using the paradigm which extends the p
1
factorization method into the elliptic
curve method, propose an algorithm for finding a prime factor p of n when p
−
+
1
is B-smooth.
Hint: Use the
GF(
p
2
)
∗
group structure.
Exercise 7.5.
Factorize 530899, 509017, 539377 using the quadratic sieve method.
Search WWH ::
Custom Search