From 66c3bbfa94d8a41e58adf154be25e6d86fee8e30 Mon Sep 17 00:00:00 2001
From: "martial.simon" <martial.simon@epita.fr>
Date: Sun, 13 Apr 2025 19:54:19 +0200
Subject: init: initial commit

---
 CHIFR/TD/TD2.md | 61 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 61 insertions(+)
 create mode 100755 CHIFR/TD/TD2.md

(limited to 'CHIFR/TD/TD2.md')

diff --git a/CHIFR/TD/TD2.md b/CHIFR/TD/TD2.md
new file mode 100755
index 0000000..3708417
--- /dev/null
+++ b/CHIFR/TD/TD2.md
@@ -0,0 +1,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
-- 
cgit v1.2.3