blob: 370841714db851d48da55a7672193ee2496b1afe (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
# Factorisation des entiers et logarithme discret
## Background mathématique
### Square & multiply
#### a/ $13^7 \mod{38}$
$$\begin{align}
13^7 \mod{38}&= 13^{2^0 \times 1} \times 13^{2^1\times 1} \times 13^{2^2\times 1} \\
&= 13 \times 13^{2} \times 13^4 \\
&= 13 * 169 \mod{38} \times 13^4 \mod{38}& \\
&= (13 \times 17) \mod{38} \times 23 \\
&= (31 \times 23) \mod{38} \\
&= 29
\end{align}$$
#### b/ Complexité
$\mathcal{O}(\log_{2}e)$
#### c/ Pour s'entraîner
### 1-2
#### a/ $11^{187} \mod{31}$
Petit théorème de Fermat : $11^{30} \equiv 1 \mod{31}$
Ainsi :
$$
\begin{align}
&11^{30} \equiv 1 \mod{31} \\
\Leftrightarrow & 11^{180} \equiv 1 \mod{31} \\
\Leftrightarrow & 11^{187} \equiv 13 \mod{31}
\end{align}
$$
#### b/ Inverse de $5$ dans $\mathbb{Z}/31\mathbb{Z}$
PTF : $5^{-1} \equiv 5^{29} \mod{31}$
Or
$$\begin{align}
5^{29} \mod{31} &= (5^{14} \times 5^{14} \times 5) \mod{31} \\
&= ((5^7)^4) \times 5 \mod{31} \\
&= (5^3 \times 5^3 \times 5^3 \times 5^3 \times 5^3 \times 5^3 \times 5^2) \\
&= 25
\end{align}
$$
Ainsi $5^{-1} = 25$ dans $\mathbb{Z}/31\mathbb{Z}$
### 1-3
#### a/ $7 \in \mathbb{Z}/38\mathbb{Z}$
$$
\begin{align}
38 &= 5 \times 7 + 3 \\
7 &= 2 \times 3 + 1 \\
3 &= 3 \times 1 + 0
\end{align}
$$
En remontant :
$$
\begin{align}
\gcd(38,7) = 1 &= 7 - 2 \times 3 \\
&= 7 - 2 \times (38 - 5 \times 7) \\
&= -2 \times 38 + 11 \times 7
\end{align}
$$
<u>Conclusion</u> : $7^{-1} = 11 \mod{38}$
#### b/ $6 \in \mathbb{Z}/28\mathbb{Z}$
### 1-4
|
