Algorithmic Number Theory - A Classical Introduction to Cryptography: Applications for Communications Security - page 208

If we extract the sixth and eighth rows, we obtain a matrix with determinant − 133 which
is invertible modulo p − 1 . By inverting the matrix, we obtain through computations in
Z p − 1 that

⎛
⎝

⎞
⎠

⎛
⎝

⎞
⎠

10918
5240
18146
3187
13929
902

x 1
x 2
x 3
x 4
x 5
x 6

=

which leads to

g 10918 2 = mod p

g 5240 3 = mod p

g 18146 5 = mod p

g 3187

7 = mod p

g 13929

11 = mod p

g 902 13 = mod p

We can finally figure out that

yg 30 2 1 5 1 7 1 13 2 ≡ × × × (mod p )

hence

g − 30 + 10918 + 18146 + 3187 + 2 × 902 g 34025

y = mod p = mod p .

7.5 Exercises

n − 1

Exercise 7.1. We call strong prime an odd prime n such that is prime as well. Prove that we

2

5 ) .

can (heuristically) generate -bit strong primes within a time complexity of O (

Hint: Make the heuristic assumption that m and 2 m + 1 behave like independent random odd

numbers when m is a random odd number.

Exercise 7.2. Assume we have a table S of n Boolean elements. We consider the five following
algorithms.