path:/home/runner/work/LSINC1113/LSINC1113/Lectures/2_number.jlcell_results $a7985d16-500b-4024-aaa1-78e654b94be4running§runtime Gdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$a7985d16-500b-4024-aaa1-78e654b94be4depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAکBH
has_pluto_hook_features¤body Comment trouver l'inverse modulaire ? Si on avait les coefficients $x$ et $y$ tels que $xa + yn = 1$ , l'inverse serait $x$ . Dans l'algorithme d'Euclide, on ne garde que le reste et on oublie le quotient . Il faudrait combiner les quotients des différentes opérations pour trouver $x$ .
$$A' \equiv B^a \pmod{p} \qquad B' \equiv A^b \pmod{p}$$
Fast powering
persist_js_state$a826d9d1-47db-4645-be6e-3ae0ed8d4e18running§runtime E]depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$a826d9d1-47db-4645-be6e-3ae0ed8d4e18depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAک?S:dhas_pluto_hook_features¤body.Est-ce que 2345 est divisible par 3 ou 9?
$$\begin{align}
2 \cdot 10^3 + 3 \cdot 10^2 + 4 \cdot 10 + 5 & \equiv \,\, ? \pmod{9}\\
2 \cdot 1^3 + 3 \cdot 1^2 + 4 \cdot 1 + 5 & \equiv \,\, ? \pmod{9}\\
2 + 3 + 4 + 5 & \equiv 14 \pmod{9}\\
\end{align}$$
Est-ce que 2345 est divisible par 11?
$$\begin{align}
2 \cdot (10)^3 + 3 \cdot 10^2 + 4 \cdot 10 + 5 & \equiv \,\, ? \pmod{11}\\
2 \cdot (-1)^3 + 3 \cdot (-1)^2 + 4 \cdot (-1) + 5 & \equiv \,\, ? \pmod{11}\\
-2 + 3 - 4 + 5 & \equiv 2 \pmod{11}\\
\end{align}$$
Fermat’s Little Theorem
persist_js_state$6c3595d2-4f68-44da-90e7-dc9c68479bcfrunning§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$6c3595d2-4f68-44da-90e7-dc9c68479bcfdepends_on_disabled_cells¦queued¤logsoutputmimetext/plainrootassigneelast_run_timestampAکG_has_pluto_hook_features¤body%cite (generic function with 1 method)persist_js_state$a293bb0e-078d-4335-a446-3096a79c03bcrunning§runtime!kdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$a293bb0e-078d-4335-a446-3096a79c03bcdepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAکD(has_pluto_hook_features¤bodyH
Diffie-Hellman
persist_js_state$38744170-9af6-44b5-a0be-46a83da3253erunning§runtime ظdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$38744170-9af6-44b5-a0be-46a83da3253edepends_on_disabled_cells¦queued¤logsoutputmimetext/plainrootassigneelast_run_timestampAکCТ˷has_pluto_hook_features¤body(fib_pow (generic function with 1 method)persist_js_state$87fdefa1-3bbd-4b69-ad3a-72baca6e55eerunning§runtime;fdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$87fdefa1-3bbd-4b69-ad3a-72baca6e55eedepends_on_disabled_cells¦queued¤logsoutputmimetext/plainrootassigneelast_run_timestampAکEʷhas_pluto_hook_features¤body4persist_js_state$77093b36-c232-4477-be49-845f1a631829running§runtime
depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$77093b36-c232-4477-be49-845f1a631829depends_on_disabled_cells¦queued¤logsgroupstdoutlinemsg 0.000001 seconds
text/plainlevelLogLevel(-555)idPlutoRunner_40f9f5d1cell_id$77093b36-c232-4477-be49-845f1a631829kwargsfileP/home/runner/.julia/packages/Pluto/F6SNP/src/runner/PlutoRunner/src/io/stdout.jloutputmimetext/plainrootassignee@time pow_1000last_run_timestampAکE^{lhas_pluto_hook_features¤body248persist_js_state$462fa407-d973-4e9e-8512-b7cd3bb98b7brunning§runtime S$depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$462fa407-d973-4e9e-8512-b7cd3bb98b7bdepends_on_disabled_cells¦queued¤logsoutputmimetext/plainrootassigneelast_run_timestampAکC2has_pluto_hook_features¤body(fib_seq (generic function with 1 method)persist_js_state$ca8905ef-97a3-424c-bb2e-559f7151585brunning§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$ca8905ef-97a3-424c-bb2e-559f7151585bdepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAک?Shas_pluto_hook_features¤body3Ensemble de solutions: $(x + kb, y - ka)$ pour un $k \in \mathbb{Z}$ arbitraire. Prenons $k$ tel que $0 \le x + kb < b$ avec mod.
Fast modular powering
persist_js_state$ee43c389-55f4-4cf9-a8db-ce37d1b89db4running§runtime,depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$ee43c389-55f4-4cf9-a8db-ce37d1b89db4depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAکD!has_pluto_hook_features¤bodyق
Shanks's Babystep–Giantstep Algorithm
persist_js_state$9b9fc5e6-1a41-43c5-ba43-2c93bc3ef66brunning§runtime{depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$9b9fc5e6-1a41-43c5-ba43-2c93bc3ef66bdepends_on_disabled_cells¦queued¤logsgroupstdoutlinemsg/ 0.000037 seconds (22 allocations: 1.586 KiB)
text/plainlevelLogLevel(-555)idPlutoRunner_40f9f5d1cell_id$9b9fc5e6-1a41-43c5-ba43-2c93bc3ef66bkwargsfileP/home/runner/.julia/packages/Pluto/F6SNP/src/runner/PlutoRunner/src/io/stdout.jloutputmimetext/plainrootassigneelast_run_timestampAکDhas_pluto_hook_features¤bodyU2.531162323732361242240155003520607291766356485802485278951929841991312781989138e4179persist_js_state$cd481f6c-66f4-4ebf-9769-c3edc24f403brunning§runtime%
depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$cd481f6c-66f4-4ebf-9769-c3edc24f403bdepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAکBu_has_pluto_hook_features¤bodyz
Algorithme d'Euclide : élaboration
persist_js_state$9752afbb-96e6-4f96-92cb-09654cf46155running§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$9752afbb-96e6-4f96-92cb-09654cf46155depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAکB.has_pluto_hook_features¤body[Est-ce que l'inverse modulaire existe toujours ? Par le théorème de Bézout, il existe si et seulement si $\text{gcd}(a, n) \mid 1$ , c'est à dire que $\text{gcd}(a, n) = 1$ .
Comment prouver que l'égalité $ax + by = c$ implique que $\text{gcd}(a, b)$ divise $c$ ? Soit $g = \text{gcd}(a, b)$ . Par définition, il existe $\alpha, \beta$ tels que $a = \alpha g$ et $b = \beta g$ . On a alors $c = ax + by = (\alpha x + \beta y) g$ ce qui implique que $c$ est un multiple de $g$ .
10 $$xb + yr = g \quad \text{et} \quad r = a - qb \quad \Rightarrow \quad (x - yq)b + ya = g$$
Solution homogène $x = b$ , $y = -a$ → $ba - ab = 0$ . Donc si $(x, y)$ est solution, $(x + b, y - a)$ aussi.
Corollaire
$$n \mid a \quad \text{et} \quad n \mid b \quad \Rightarrow \quad n \mid (ab)$$
À ne pas confondre avec
$$a \mid n \quad \text{et} \quad b \mid n \quad \Rightarrow \quad (ab/\text{gcd}(a,b)) \mid n$$
Fast powering for matrices
persist_js_state$6107d03d-1e45-4eb9-b8e2-51e4a72485e6running§runtime!depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$6107d03d-1e45-4eb9-b8e2-51e4a72485e6depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAکC has_pluto_hook_features¤body\
Recursive implementation
persist_js_state$e1b5733f-a7a8-458f-a345-b358b9a03fcfrunning§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$e1b5733f-a7a8-458f-a345-b358b9a03fcfdepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAک?Uhas_pluto_hook_features¤bodyOn remarque que la matrice est de rang 1. Elle vaut
$$\begin{bmatrix}
1 & g^n & \cdots & g^{n^2-n}\\
g & g^{n+1} & \ddots & g^{n^2-n+1}\\
\vdots & \ddots & \ddots & \vdots\\
g^{n-1} & g^{2n-1} & \cdots & g^{n^2 - 1}
\end{bmatrix}
\equiv
\begin{bmatrix}
1\\
g\\
g^2\\
\vdots\\
g^{n-1}
\end{bmatrix}
\begin{bmatrix}
1 &
g^{n} &
g^{2n} &
\cdots &
g^{n^2-n}
\end{bmatrix}
\pmod{p}$$
13 Quelle est la complexité? $\mathcal{O}(\sqrt{p}\log(p))$
Est-ce une complexité linéaire ou exponentielle en fonction de la taille de l'input La taille est proportionnelle à $\log_2(p)$ donc on être linéaire en $p$ c'est être proportionnel à $2^{\log_2(p)}$ et donc la complexité est exponentielle en la taille de l'input ! [HPS14; Section 2.6]
Fermat's little theorem [HPS14; Theorem 1.24]
$$\text{Si} \quad p \text{ est premier}\quad \text{et} \quad p \nmid g,\quad \text{alors} \quad
g^{p - 1} \equiv 1 \pmod{p}.$$
Algorithme d'Euclide étendu
persist_js_state$ab467d70-ceb1-40e5-b8fe-82e2f1bd95fdrunning§runtime(udepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$ab467d70-ceb1-40e5-b8fe-82e2f1bd95fddepends_on_disabled_cells¦queued¤logsoutputmimetext/plainrootassigneelast_run_timestampAکEPhas_pluto_hook_features¤body3persist_js_state$a7d9703a-5121-4b43-8cd4-2acf9a0d91efrunning§runtime kdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$a7d9703a-5121-4b43-8cd4-2acf9a0d91efdepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAک?T?has_pluto_hook_features¤body#La méthode meet in the middle est une méthode générique permettant de passer d'une complexité de $\mathcal{O}(N)$ à $\mathcal{O}(\sqrt{N})$ .
11 $$a \equiv \alpha \pmod{n} \quad \text{et} \quad b \equiv \beta \pmod{n}
\quad \Rightarrow \quad a + b \equiv \alpha + \beta \pmod{n}$$
Théorème de Bézout
persist_js_state$642d545f-b1b9-49da-8a03-ad63e3214f59running§runtime ddepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$642d545f-b1b9-49da-8a03-ad63e3214f59depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAک?Shas_pluto_hook_features¤body$$a \equiv \alpha \pmod{n} \quad \text{et} \quad b \equiv \beta \pmod{n}
\quad \Rightarrow \quad a b \equiv \alpha \beta \pmod{n}$$
persist_js_state$a7afc0cb-a980-4f4f-b782-9791d932ee52running§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$a7afc0cb-a980-4f4f-b782-9791d932ee52depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAکG{has_pluto_hook_features¤bodyFVoir [HPS14; Section 2.8].
Étant donné un nombre premier $p$ et une racine primitive $g$ modulo $p$ et un entier $a$ tel que $p \nmid a$ , le Discrete logarithme problem consiste à retrouver $x$ tel que $g^x \equiv a \pmod{p}$ .
Exemples
persist_js_state$c2fab245-8a98-4b41-ade2-c5b16e9c39f9running§runtime'#depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$c2fab245-8a98-4b41-ade2-c5b16e9c39f9depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAکC1}has_pluto_hook_features¤body^
Chinese remainder theorem
persist_js_state$35b7b8b7-bff6-4f64-91b9-b65035162365running§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$35b7b8b7-bff6-4f64-91b9-b65035162365depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAکG has_pluto_hook_features¤bodyEVoir [HPS14; Section 2.3]
Quelle est la complexité spatiale et temporelle de discrete_log ? $\mathcal{O}(p)$ temporelle et $\Omega(1)$ spatiale. Voir [HPS14; Proposition 2.19].
Si tous les mois avaient 30 jours, est-ce qu'il y a des jours de la semaine qui ne seront jamais le premier du mois ?
Reformulation: pour tout nombre $0 \le j < 7$ , existe-t-il $x$ et $y$ tels que $30x = j + 7y$ . Notation modulo : $30x \equiv j \pmod{7}$ .
Si tous les ans avaient 365 jours, est-ce qu'il y a des jours de la semaine qui ne seront jamais le 25 Décembre ? Est si tous les ans avaient 366 jours ? Et s'ils avaient 364 jours ?
Reformulation: pour tout nombre $0 \le j < 7$ , existe-t-il $x$ et $y$ tels que $365x = j + 7y$ . Notation modulo : $365x \equiv j \pmod{7}$ .
Inverse modulaire : étant donné $a, n$ , trouver $x$ (noté $a^{-1}$ ) tel que $xa \equiv 1 \pmod{n}$
Division modulaire : étant donné $a, b, n$ , trouver $x$ tel que $xa \equiv b \pmod{n}$ → $x \equiv a^{-1}b \pmod{n}$ .
Algorithme d'Euclide : implémentation
persist_js_state$65f4990f-1952-4682-8fa8-9e3dd4bf1ebfrunning§runtime
Ldepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$65f4990f-1952-4682-8fa8-9e3dd4bf1ebfdepends_on_disabled_cells¦queued¤logsgroupstdoutlinemsg 0.000001 seconds
text/plainlevelLogLevel(-555)idPlutoRunner_40f9f5d1cell_id$65f4990f-1952-4682-8fa8-9e3dd4bf1ebfkwargsfileP/home/runner/.julia/packages/Pluto/F6SNP/src/runner/PlutoRunner/src/io/stdout.jloutputmimetext/plainrootassignee@time pow_999last_run_timestampAکE_has_pluto_hook_features¤body500persist_js_state$d1b260fb-7500-47fb-bb48-21b5857ab55arunning§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$d1b260fb-7500-47fb-bb48-21b5857ab55adepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAک?Rʧhas_pluto_hook_features¤bodyLemme : Si $a \equiv r \pmod{b}$ alors $\text{gcd}(a, b) = \text{gcd}(b, r)$ .
Observation clé Si $a > b$ , trouver un mono-variant.On a $(a, b) > (b, r)$ . En effet, $a > b$ par supposition et $b > r$ par définition de l'algorithme d'Euclide. Notons que même si la supposition $a > b$ n'est pas vraie, elle le devient pour $\text{gcd}(b, r)$ .
Diagonalization to speed up powering
persist_js_state$3da58487-192f-458a-9d47-7a4ce98b6da3running§runtime#depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$3da58487-192f-458a-9d47-7a4ce98b6da3depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAکD has_pluto_hook_features¤body6
Utils
persist_js_state$6cf004be-5205-429e-8131-ef607cebeaecrunning§runtime(depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$6cf004be-5205-429e-8131-ef607cebeaecdepends_on_disabled_cells¦queued¤logsoutputmimetext/plainrootassigneelast_run_timestampAکDwhas_pluto_hook_features¤bodyA2×2 Matrix{Float64}:
0.525731 -0.850651
-0.850651 -0.525731persist_js_state$0e3fb524-bea1-4ef0-9589-36230a84e949running§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$0e3fb524-bea1-4ef0-9589-36230a84e949depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneegp_pickerlast_run_timestampAکE
has_pluto_hook_features¤bodyypersist_js_state$aee611f2-bc86-4e85-bbcb-add78c6a9175running§runtime]߸depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$aee611f2-bc86-4e85-bbcb-add78c6a9175depends_on_disabled_cells¦queued¤logsoutputmime!application/vnd.pluto.tree+objectrootassigneelast_run_timestampAکBۭhas_pluto_hook_features¤bodyobjectid54a1c5b46a9f8dc9typeTupleelements1text/plain89932200text/plain-32561659text/plainpersist_js_state$97736c6a-3f5d-4978-8dd2-0a11c09ba9f0running§runtime 2depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$97736c6a-3f5d-4978-8dd2-0a11c09ba9f0depends_on_disabled_cells¦queued¤logsoutputmimetext/plainrootassigneelast_run_timestampAکB"has_pluto_hook_features¤body%pgcd (generic function with 1 method)persist_js_state$9722971a-16f1-4f28-ba31-c12b673b8a30running§runtime ~/depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$9722971a-16f1-4f28-ba31-c12b673b8a30depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAک?T`has_pluto_hook_features¤body3persist_js_state$8a5a251f-5373-445a-97b1-4d652c6b7ba8running§runtime <depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$8a5a251f-5373-445a-97b1-4d652c6b7ba8depends_on_disabled_cells¦queued¤logsoutputmimetext/plainrootassigneelast_run_timestampAکG/has_pluto_hook_features¤body%refs (generic function with 1 method)persist_js_state$592ae01b-2819-402d-9538-17018df5c34brunning§runtime$depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$592ae01b-2819-402d-9538-17018df5c34bdepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAکCFhas_pluto_hook_features¤bodyP
Fibonacci sequence
persist_js_state$191f8429-cbbb-44aa-8beb-271a94293e4brunning§runtime5depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$191f8429-cbbb-44aa-8beb-271a94293e4bdepends_on_disabled_cells¦queued¤logsoutputmimetext/plainrootassigneelast_run_timestampAکE~Phas_pluto_hook_features¤body$986325341584402112586461440731025613persist_js_state$1072a756-5026-4de9-93a8-f942d54c474arunning§runtime Kdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$1072a756-5026-4de9-93a8-f942d54c474adepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAکG has_pluto_hook_features¤bodyEVoir [HPS14; Section 2.7]
Arithmétique modulaire : produit
persist_js_state$eeaec4f4-71bd-43df-b9c9-a00bc3b1864brunning§runtime$depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$eeaec4f4-71bd-43df-b9c9-a00bc3b1864bdepends_on_disabled_cells¦queued¤logsoutputmime!application/vnd.pluto.tree+objectrootassigneelast_run_timestampAکBEhas_pluto_hook_features¤bodyobjectid54a1c5b46a9f8dc9typeTupleelements1text/plain89932200text/plain-32561659text/plainpersist_js_state$f6e22fc3-382e-4548-bc59-8f944e06d237running§runtime
depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$f6e22fc3-382e-4548-bc59-8f944e06d237depends_on_disabled_cells¦queued¤logsoutputmimetext/plainrootassigneelast_run_timestampAکDhas_pluto_hook_features¤body32×2 Matrix{Float64}:
1.0 1.0
1.0 -1.11022e-16persist_js_state$19ef447f-9fdf-49e1-8d1a-7860b4d4e9barunning§runtime 9adepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$19ef447f-9fdf-49e1-8d1a-7860b4d4e9badepends_on_disabled_cells¦queued¤logsoutputmimetext/plainrootassigneeDlast_run_timestampAکDndhas_pluto_hook_features¤bodyR2×2 Diagonal{BigFloat, Vector{BigFloat}}:
-0.618034 ⋅
⋅ 1.61803persist_js_state$82ba8fe1-435e-422b-abb7-cb50a7a85e1erunning§runtime!۸depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$82ba8fe1-435e-422b-abb7-cb50a7a85e1edepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAکD%ݷhas_pluto_hook_features¤bodyN
Dicrete logarithm
persist_js_state$41cf9efd-65e5-4abb-94d3-e824780e659crunning§runtimeuP6depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$41cf9efd-65e5-4abb-94d3-e824780e659cdepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAکH<(has_pluto_hook_features¤body~
[HPS14] J. Hoffstein, J. Pipher and J. H. Silverman. An Introduction to Mathematical Cryptography Undergraduate Texts in Mathematics (Springer, New York, NY, 2014 ). Accessed on Nov 18, 2024.
persist_js_state$58da5ba4-c858-4684-a9f4-5a39fdc4fb03running§runtime
i6depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$58da5ba4-c858-4684-a9f4-5a39fdc4fb03depends_on_disabled_cells¦queued¤logsoutputmimetext/plainrootassigneelast_run_timestampAکC%has_pluto_hook_features¤body+fast_power (generic function with 1 method)persist_js_state$ec25ce2a-de8a-4b69-a3f3-b47cd58ec986running§runtime6depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$ec25ce2a-de8a-4b69-a3f3-b47cd58ec986depends_on_disabled_cells¦queued¤logsoutputmimetext/plainrootassigneelast_run_timestampAکEe÷has_pluto_hook_features¤body252248persist_js_state$256c8009-4d2b-42f8-adaa-6f238ef22c6drunning§runtime
depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$256c8009-4d2b-42f8-adaa-6f238ef22c6ddepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneeslider_nlast_run_timestampAکEٷhas_pluto_hook_features¤body5 Étant donné un nombre premier $p$ et une racine primitive $g$ modulo $p$ , Alice (resp. Bob) génère un nombre secret $a$ (resp. $b$ ). Ils communique ensuite publiquement $A$ et $B$ .
Le nombre 2 est une racine primitive modulo 11
Quelle est la complexité temporelle ? Si $n$ est impair, au coup suivant, il est pair donc il n'est impair qu'au pire une fois sur deux. En $l$ multiplication, on divise $m$ au moins par $2^{l/2}$ donc on a une complexité logarithmique $\Theta(\log(m))$ en supposant que prod_func a une complexité $\Theta(1)$ .
Que faire si que $m$ est impair, c'est à dire $m = 2k + 1$ ... Si $b = a^{2k}$ , calcule le produit $b \times a$ .
251 Observation finale Si $a$ et $b$ sont positifs et qu'on effectue la substitution $(a, b) \to (b, r)$ récursivement, le mono-variant impose qu'on ne puisse itérer qu'un nombre fini de fois, que va-t-il se passer ?La paire $(a, b)$ va diminuer strictement (c'est à dire d'au moins 1) à chaque itération. Pourtant, ce sont des nombres entier positifs donc ils ne peuvent diminuer strictement qu'un nombre fini de fois. C'est une contradiction, comme cela se fait-il ? À un moment $b$ vaudra 0, on ne pourra alors plus faire de division Euclidienne. On utilisera alors le fait que $\text{gcd}(a, 0) = a$ .
Trouver $b$ tel que $x_k$ est solution:
$$x_k = b^k
\quad \to \quad b^{k+1} = b^k + b^{k-1}
\quad \to \quad b^2 - b - 1 = 0
\quad \to \quad b = \frac{1 \pm \sqrt{5}}{2}$$
On a donc une famille de solutions:
$$x_k = a_1
\left(\frac{1 - \sqrt5}{2}\right)^k +
a_2
\left(\frac{1 + \sqrt5}{2}\right)^k$$
Il reste à trouver $a_1$ et $a_2$ tels que $x_0 = 0$ et $x_1 = 1$ . Ça correspond à calculer E.vectors \ [1, 0], etc...
$$\begin{align}
x_0 & = 0 & a_1 + a_2 & = 0\\
x_1 & = 1 & a_1 \frac{1 - \sqrt5}{2} + a_2 \frac{1 + \sqrt5}{2} & = 1
\end{align}$$
Donc $a_1 = -1/\sqrt5$ et $a_2 = 1/\sqrt5$ .
Arithmétique modulaire : somme
persist_js_state$4853f4ef-fbb8-48c3-9523-13ab4969d097running§runtime ָdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$4853f4ef-fbb8-48c3-9523-13ab4969d097depends_on_disabled_cells¦queued¤logsoutputmimetext/plainrootassigneelast_run_timestampAکDЎhas_pluto_hook_features¤body+baby_steps (generic function with 1 method)persist_js_state$b57adc77-3783-4958-91a0-e90782338755running§runtime vdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$b57adc77-3783-4958-91a0-e90782338755depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneeslider_alast_run_timestampAکEHVhas_pluto_hook_features¤body11 $$A \equiv g^a \pmod{p} \qquad B \equiv g^b \pmod{p}$$
Définition Le résultat de la division Euclidienne de $a$ par un diviseur $d$ est un quotient $q$ et un reste $0 \le r < d$ tels que $a = qd + r$ . En notation modulaire $a \equiv r \pmod{d}$ .
$30x \equiv j \pmod{7} \quad \Rightarrow \quad x \equiv (30)^{-1} j\pmod{7}$
Comment calculer $a^m$ pour un large $m$ ?
Comment savoir si prime_list contient assez de nombres pour avoir la bonne réponse ? On a la bonne réponse modulo prod(prime_list) donc si prod(prime_list) > 2^power, on a la bonne réponse.
On peut mettre le vecteur de taille $n^2$ sous forme de matrice de taille $n \times n$
Meet in the middle approach
persist_js_state$bbb2793a-faa4-43bd-b2e8-e8d3ac93310frunning§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$bbb2793a-faa4-43bd-b2e8-e8d3ac93310fdepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAک?T has_pluto_hook_features¤bodyمS'il y avait 364 jours par ans, les fêtes seraient toujours le même jour de la semaine!
Définition $g$ est une racine primitive modulo $p$ si $g^k$ prend toutes les valeurs $1, 2, ..., p - 1$ .
$$\text{Si } \quad p \nmid b,\quad \text{ alors } \quad
b^{p - 1} \equiv 1 \pmod{p}$$
On doit donc trouver la ligne $i$ et la ligne et $j$ tels que
$$\begin{align}
g^{i-1}g^{(j-1)n} & \equiv a & \pmod{p}\\
g^{i-1} & \equiv a(g^{-n})^{j-1} & \pmod{p}
\end{align}$$
Ils ne reste plus qu'à chercher une collision entre les listes de restes modulo $p$ pour $g^{i-1}$ et $a(g^{-n})^{j-1}$ . L'identification des collision peut se faire en $\mathcal{O}(\sqrt{n}\log(n))$ avec une recherche dichotomique our en $\mathcal{O}(\sqrt{n})$ amorti avec un dictionaire.
Inverse et division modulaire
persist_js_state$8315b53f-abca-483d-bbf6-7e9193e751c9running§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$8315b53f-abca-483d-bbf6-7e9193e751c9depends_on_disabled_cells¦queued¤logsoutputmimetext/plainrootassigneelast_run_timestampAکEt2has_pluto_hook_features¤body*draw_fib (generic function with 2 methods)persist_js_state$4c2d45e3-56a2-467f-b87f-7b98cb873a05running§runtimetdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$4c2d45e3-56a2-467f-b87f-7b98cb873a05depends_on_disabled_cells¦queued¤logsoutputmime!application/vnd.pluto.tree+objectrootassigneelast_run_timestampAکEshas_pluto_hook_features¤bodyprefixInt64objectid771ffe29e6f08f7typeArrayprefix_shortelements 2text/plain3text/plain4text/plain2text/plain7text/plain8text/plain10text/plain6text/plain 15text/plain
2text/plain 19text/plain 39text/plain
22text/plain12text/plain50text/plain14text/plain35text/plain41text/plain64text/plain37text/plain11text/plain32text/plain67text/plain11text/plainpersist_js_state$3df688c8-1c52-462d-88be-daa153333c60running§runtime% u=depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$3df688c8-1c52-462d-88be-daa153333c60depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAکG has_pluto_hook_features¤body
Théorie des nombres: [HPS14; 1.2, 1.3, 1.4, 1.5, 2.2, 2.3]
Discrete Logarithme Problem et Diffie-Hellman: [HPS14; 2.2, 2.3, 2.6, 2.7, 2.8]
Observation clé Que dit le théorème de Bézout par rapport à $\text{gcd}(d, r)$ et $a$ .Le nombre $a$ est divisible par $\text{gcd}(d, r)$ . Le nombre $\text{gcd}(d, r)$ divise donc les 3 nombres, $a$ , $d$ et $r$ et donc $\text{gcd}(d, r) = \text{gcd}(a, d, r)$ . En combinant ça avec l'observation précédente, on a $\text{gcd}(a, d) = \text{gcd}(d, r)$ . On peut généraliser cela en le lemme suivant:
Comment trouver mod(2^power, 999000) en utilisant pow_1000 et pow_999 ? On peut utiliser une astuce similaire à l'interpolation Lagrangienne. On veut trouver $x$ et $y$ tels que
$$\texttt{pow\_1000}x + \texttt{pow\_999}y \equiv 2^\texttt{power} \pmod{999000}$$
On veut que $x \equiv 0 \pmod{999}$ et $x \equiv 1 \pmod{1000}$ . On utilise donc $x = 999x'$ avec $x' \equiv (999)^{-1} \pmod{1000}$ .
The complexity is difficult to evaluate but can be shown to be $O(\log(\min(a, b)))$ .
$366x \equiv j \pmod{7} \quad \Rightarrow \quad x \equiv (366)^{-1} j\pmod{7}$
$365x \equiv j \pmod{7} \quad \Rightarrow \quad x \equiv (365)^{-1} j\pmod{7}$
Division par 3 et 9
persist_js_state$9bdb30ba-48a7-4e1b-96c2-ea0e059d5253running§runtime<depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$9bdb30ba-48a7-4e1b-96c2-ea0e059d5253depends_on_disabled_cells¦queued¤logsoutputmimetext/plainrootassigneelast_run_timestampAکEhas_pluto_hook_features¤body3persist_js_state$736307ec-a2a4-11ef-0f85-ad1a0093e06arunning§runtime lIdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$736307ec-a2a4-11ef-0f85-ad1a0093e06adepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAک?Phas_pluto_hook_features¤bodyZ
La théorie des nombres
persist_js_state$40b8e474-16e0-4a61-bb28-11d90beefeearunning§runtime:depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$40b8e474-16e0-4a61-bb28-11d90beefeeadepends_on_disabled_cells¦queued¤logsoutputmimetext/plainrootassigneelast_run_timestampAکB[yhas_pluto_hook_features¤body1persist_js_state$6e59ee60-ef73-45ca-86eb-4d8a44c73771running§runtime mPdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$6e59ee60-ef73-45ca-86eb-4d8a44c73771depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAکBw8Ghas_pluto_hook_features¤bodyObservation clé Que dit le théorème de Bézout par rapport à $\text{gcd}(a, d)$ et $r$ .Le reste $r$ est divisible par $\text{gcd}(a, d)$ . Le nombre $\text{gcd}(a, d)$ divise donc les 3 nombres, $a$ , $d$ et $r$ et donc $\text{gcd}(a, d) = \text{gcd}(a, d, r)$ .
Le nombre 2 est une racine primitive modulo 11
Inversion modulaire par Euclide étendu
persist_js_state$21df1900-3954-4506-b759-aeeee664d1dfrunning§runtime
Gdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$21df1900-3954-4506-b759-aeeee664d1dfdepends_on_disabled_cells¦queued¤logsoutputmimetext/plainrootassigneelast_run_timestampAکChas_pluto_hook_features¤body'modinv (generic function with 1 method)persist_js_state$d830fffd-3781-40ca-85cb-c242f99667cerunning§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$d830fffd-3781-40ca-85cb-c242f99667cedepends_on_disabled_cells¦queued¤logsoutputmimetext/plainrootassigneelast_run_timestampAکDhas_pluto_hook_features¤body)fib_diag (generic function with 1 method)persist_js_state$08b18315-c28e-44ed-beb2-5b17421b0224running§runtime `depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$08b18315-c28e-44ed-beb2-5b17421b0224depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAک?R[has_pluto_hook_features¤body
Définition Le Greatest Common Divisor (GCD) de deux nombres $a \in \mathbb{Z}$ et $b \in \mathbb{Z}$ , noté $\text{gcd}(a, b)$ est le plus grand nombre $g \in \mathbb{Z}$ qui divise $a$ (noté $g \mid a$ ) et $b$ (noté $g \mid b$ ). C'est à dire qu'il existe $x \in \mathbb{Z}$ tel que $a = gx$ et $y \in \mathbb{Z}$ tel que $b = gy$ . En notation modulaire, $a \equiv 0 \pmod{g}$ et $b \equiv 0 \pmod{g}$ .
Théorème de Bézout Il existe $x, y \in \mathbb{Z}$ tels que $ax + by = c$ si et seulement si $\text{gcd}(a, b)$ divise $c$ . En notation modulaire $ax \equiv c \pmod{b}$ et $by \equiv c \pmod{a}$ .
What is the relation between $A'$ and $B'$ ? $$A' \equiv (g^b)^a \equiv g^{ab} \equiv (g^{a})^b \equiv B' \pmod{p}$$
Alice et Bob ont donc maintenant la même clef! Il est cependant difficile de trouver $A'$ depuis $A$ et $B$ sans connaitre les secrets $a$ ou $b$ si le Discrete Logarithm Problem est difficile.
Par l'algo d'Euclide, $\text{gcd}(n, n - 1) = 1$ donc $\text{gcd}(1000, 999) = 1$ .
Équation de récurrence:
$$x_{k+1} = x_k + x_{k-1}$$
Reformulation sans $(k-1)$
$$\begin{align}
x_{k+1} & = x_k + y_{k}\\
y_{k+1} & = x_k
\end{align}$$
Forme matricielle:
$$\begin{bmatrix}
x_{k+1}\\
y_{k+1}
\end{bmatrix}
=
\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}
\begin{bmatrix}
x_{k}\\
y_{k}
\end{bmatrix}$$
Matrix power:
$$\begin{bmatrix}
x_n\\
y_n
\end{bmatrix}
=
\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}^n
\begin{bmatrix}
x_0\\
y_0
\end{bmatrix}$$
Supposons que $m$ est pair, c'est à dire $m = 2k$ ... On a $a^{2k} = (a^k)^2$ . Si $b = a^k$ , on calcule le produit $b \times b$ .
