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}$ .
$$\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}.$$
mimetext/htmlrootassigneelast_run_timestampAڰbmpersist_js_state·has_pluto_hook_features$40b8e474-16e0-4a61-bb28-11d90beefeearunning§runtime0ydepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$40b8e474-16e0-4a61-bb28-11d90beefeeadepends_on_disabled_cells¦queued¤logsoutputbody1mimetext/plainrootassigneelast_run_timestampAڰ^persist_js_state·has_pluto_hook_features$592ae01b-2819-402d-9538-17018df5c34brunning§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$592ae01b-2819-402d-9538-17018df5c34bdepends_on_disabled_cells¦queued¤logsoutputbodyPTrouver $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$ .
Lemme : Si $a \equiv r \pmod{b}$ alors $\text{gcd}(a, b) = \text{gcd}(b, r)$ .
mimetext/htmlrootassigneelast_run_timestampAڰZ$persist_js_state·has_pluto_hook_features$3cd40d9e-fcea-427d-9877-cea65e7ea413running§runtime ?=3depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$3cd40d9e-fcea-427d-9877-cea65e7ea413depends_on_disabled_cells¦queued¤logsgroupstdoutlinemsg5 0.003560 seconds (40.01 k allocations: 17.619 MiB)
text/plainlevelLogLevel(-555)idPlutoRunner_40f9f5d1cell_id$3cd40d9e-fcea-427d-9877-cea65e7ea413kwargsfileP/home/runner/.julia/packages/Pluto/sRdkC/src/runner/PlutoRunner/src/io/stdout.jloutputbodyT2531162323732361242240155003520607291766356485802485278951929841991312781760541315230153423463758831637443488219211037689033673531462742885329724071555187618026931630449193158922771331642302030331971098689235780843478258502779200293635651897483309686042860996364443514558772156043691404155819572984971754278513112487985892718229593329483578531419148805380281624260900362993556916638613939977074685016188258584312329139526393558096840812970422952418558991855772306882442574855589237165219912238201311184749075137322987656049866305366913734924425822681338966507463855180236283582409861199212323835947891143765414913345008456022009455704210891637791911265475167769704477334859109822590053774932978465651023851447920601310106288957894301592502061560528131203072778677491443420921822590709910448617329156135355464620891788459566081572824889514296350670950824208245170667601726417091127999999941149913010424532046881958285409468463211897582215075436515584016297874572183907949257286261608612401379639484713101138120404671732190451327881433201025184027541696124114463488665359385870910331476156665889459832092710304159637019707297988417848767011085425271875588008671422491434005115288334343837778792282383576736341414410248994081564830202363820504190074504566612515965134665683289356188727549463732830075811851574961558669278847363279870595320099844676879457196432535973357128305390290471349480258751812890314779723508104229525161740643984423978659638233074463100366500571977234508464710078102581304823235436518145074482824812996511614161933313389889630935320139507075992100561077534028207257574257706278201308302642634678112591091843082665721697117838726431766741158743554298864560993255547608496686850185804659790217122426535133253371422250684486113457341827911625517128815447325958547912113242367201990672230681308819195941016156001961954700241576553750737681552256845421159386858399433450045903975167084252876848848085910156941603293424067793097271128806817514906531652407763118308162377033463203514657531210413149191213595455280387631030665594589183601575340027172997222489081631144728873621805528648768511368948639522975539046995395707688938978847084621586473529546678958226255042389998718141303055036060772003887773038422366913820397748550793178167220193346017430024134496141145991896227741842515718997898627269918236920453493946658273870473264523119133765447653295022886429174942653014656521909469613184983671431465934965489425515981067546087342348350724207583544436107294087637975025147846254526938442435644928231027868701394819091132912397475713787593612758364812687556725146456646878912169274219209708166678668152184941578590201953144030519381922273252666652671717526318606676754556170379350956342095455612780202199922615392785572481747913435560866995432578680971243966868110016581395696310922519803685837460795358384618017215468122880442252343684547233668502313239328352671318130604247460452134121833305284398726438573787798499612760939462427922917659263046333084007208056631996856315539698234022953452211505675629153637867252695056925345220084020071611220575700841268302638995272842160994219632684575364180160991884885091858259996299627148614456696661412745040519981575543804847463997422326563897043803732970397488471644906183310144691243649149542394691524972023935190633672827306116525712882959108434211652465621144702015336657459532134026915214509960877430595844287585350290234547564574848753110281101545931547225811763441710217452979668178025286460158324658852904105792472468108996135476637212057508192176910900422826969523438985332067597093454021924077101784215936539638808624420121459718286059401823614213214326004270471752802725625810953787713898846144256909835116371235019527013180204030167601567064268573820697948868982630904164685161783088076506964317303709708574052747204405282785965604677674192569851918643651835755242670293612851920696732320545562286110332140065912751551110134916256237884844001366366654055079721985816714803952429301558096968202261698837096090377863017797020488044826628817462866854321356787305635653577619877987998113667928954840972022833505708587561902023411398915823487627297968947621416912816367516125096563705174220460639857683971213093125mimetext/plainrootassigneelast_run_timestampAڰ_Zpersist_js_state·has_pluto_hook_features$67093a35-8e1b-4cd3-b11b-c7ff601f802erunning§runtime mkdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$67093a35-8e1b-4cd3-b11b-c7ff601f802edepends_on_disabled_cells¦queued¤logsoutputbody
mimetext/htmlrootassigneelast_run_timestampAڰ^۹persist_js_state·has_pluto_hook_features$ac5e1516-1574-4893-a965-f799947076cbrunning§runtimeBdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$ac5e1516-1574-4893-a965-f799947076cbdepends_on_disabled_cells¦queued¤logsgroupstdoutlinemsgO 0.284572 seconds (701.20 k allocations: 37.581 MiB, 99.93% compilation time)
text/plainlevelLogLevel(-555)idPlutoRunner_40f9f5d1cell_id$ac5e1516-1574-4893-a965-f799947076cbkwargsfileP/home/runner/.julia/packages/Pluto/sRdkC/src/runner/PlutoRunner/src/io/stdout.jloutputbodyU2.531162323732361578998428490601662084769270923897910687031954402219719762339543e4179mimetext/plainrootassigneelast_run_timestampAڰ`"jpersist_js_state·has_pluto_hook_features$a826d9d1-47db-4645-be6e-3ae0ed8d4e18running§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$a826d9d1-47db-4645-be6e-3ae0ed8d4e18depends_on_disabled_cells¦queued¤logsoutputbody.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}$$
Shanks's Babystep–Giantstep Algorithm
mimetext/htmlrootassigneelast_run_timestampAڰ`:(Apersist_js_state·has_pluto_hook_features$e9633e3f-376d-413d-bc19-d015f6ce76e5running§runtime7ݸdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$e9633e3f-376d-413d-bc19-d015f6ce76e5depends_on_disabled_cells¦queued¤logsoutputbodyL3618502788666131106986593281521497120414687020801267626233049500247285301248mimetext/plainrootassigneelast_run_timestampAڰ`[persist_js_state·has_pluto_hook_features$37585789-bd43-4ce5-b550-ad712b70d226running§runtime idepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$37585789-bd43-4ce5-b550-ad712b70d226depends_on_disabled_cells¦queued¤logsoutputbody
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}$ .
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.
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}$ .
Diffie-Hellman
mimetext/htmlrootassigneelast_run_timestampAڰ`Wݩpersist_js_state·has_pluto_hook_features$a1081bb2-2186-4b19-b667-0c246155f360running§runtime
depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$a1081bb2-2186-4b19-b667-0c246155f360depends_on_disabled_cells¦queued¤logsgroupstdoutlinemsg2 0.000133 seconds (826 allocations: 100.922 KiB)
text/plainlevelLogLevel(-555)idPlutoRunner_40f9f5d1cell_id$a1081bb2-2186-4b19-b667-0c246155f360kwargsfileP/home/runner/.julia/packages/Pluto/sRdkC/src/runner/PlutoRunner/src/io/stdout.jloutputbodyT2531162323732361242240155003520607291766356485802485278951929841991312781760541315230153423463758831637443488219211037689033673531462742885329724071555187618026931630449193158922771331642302030331971098689235780843478258502779200293635651897483309686042860996364443514558772156043691404155819572984971754278513112487985892718229593329483578531419148805380281624260900362993556916638613939977074685016188258584312329139526393558096840812970422952418558991855772306882442574855589237165219912238201311184749075137322987656049866305366913734924425822681338966507463855180236283582409861199212323835947891143765414913345008456022009455704210891637791911265475167769704477334859109822590053774932978465651023851447920601310106288957894301592502061560528131203072778677491443420921822590709910448617329156135355464620891788459566081572824889514296350670950824208245170667601726417091127999999941149913010424532046881958285409468463211897582215075436515584016297874572183907949257286261608612401379639484713101138120404671732190451327881433201025184027541696124114463488665359385870910331476156665889459832092710304159637019707297988417848767011085425271875588008671422491434005115288334343837778792282383576736341414410248994081564830202363820504190074504566612515965134665683289356188727549463732830075811851574961558669278847363279870595320099844676879457196432535973357128305390290471349480258751812890314779723508104229525161740643984423978659638233074463100366500571977234508464710078102581304823235436518145074482824812996511614161933313389889630935320139507075992100561077534028207257574257706278201308302642634678112591091843082665721697117838726431766741158743554298864560993255547608496686850185804659790217122426535133253371422250684486113457341827911625517128815447325958547912113242367201990672230681308819195941016156001961954700241576553750737681552256845421159386858399433450045903975167084252876848848085910156941603293424067793097271128806817514906531652407763118308162377033463203514657531210413149191213595455280387631030665594589183601575340027172997222489081631144728873621805528648768511368948639522975539046995395707688938978847084621586473529546678958226255042389998718141303055036060772003887773038422366913820397748550793178167220193346017430024134496141145991896227741842515718997898627269918236920453493946658273870473264523119133765447653295022886429174942653014656521909469613184983671431465934965489425515981067546087342348350724207583544436107294087637975025147846254526938442435644928231027868701394819091132912397475713787593612758364812687556725146456646878912169274219209708166678668152184941578590201953144030519381922273252666652671717526318606676754556170379350956342095455612780202199922615392785572481747913435560866995432578680971243966868110016581395696310922519803685837460795358384618017215468122880442252343684547233668502313239328352671318130604247460452134121833305284398726438573787798499612760939462427922917659263046333084007208056631996856315539698234022953452211505675629153637867252695056925345220084020071611220575700841268302638995272842160994219632684575364180160991884885091858259996299627148614456696661412745040519981575543804847463997422326563897043803732970397488471644906183310144691243649149542394691524972023935190633672827306116525712882959108434211652465621144702015336657459532134026915214509960877430595844287585350290234547564574848753110281101545931547225811763441710217452979668178025286460158324658852904105792472468108996135476637212057508192176910900422826969523438985332067597093454021924077101784215936539638808624420121459718286059401823614213214326004270471752802725625810953787713898846144256909835116371235019527013180204030167601567064268573820697948868982630904164685161783088076506964317303709708574052747204405282785965604677674192569851918643651835755242670293612851920696732320545562286110332140065912751551110134916256237884844001366366654055079721985816714803952429301558096968202261698837096090377863017797020488044826628817462866854321356787305635653577619877987998113667928954840972022833505708587561902023411398915823487627297968947621416912816367516125096563705174220460639857683971213093125mimetext/plainrootassigneelast_run_timestampAڰ_~Jpersist_js_state·has_pluto_hook_features$d8a28762-8aab-49e9-b9ac-38901d34abffrunning§runtime"depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$d8a28762-8aab-49e9-b9ac-38901d34abffdepends_on_disabled_cells¦queued¤logsoutputbodyF
Fast powering
mimetext/htmlrootassigneelast_run_timestampAڰ^persist_js_state·has_pluto_hook_features$15367f3b-c7e4-4004-a018-5422a7f22024running§runtime _depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$15367f3b-c7e4-4004-a018-5422a7f22024depends_on_disabled_cells¦queued¤logsoutputbody٬On peut mettre le vecteur de taille $n^2$ sous forme de matrice de taille $n \times n$
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)$ .
$$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.
$$a \equiv \alpha \pmod{n} \quad \text{et} \quad b \equiv \beta \pmod{n}
\quad \Rightarrow \quad a b \equiv \alpha \beta \pmod{n}$$
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$ .
$30x \equiv j \pmod{7} \quad \Rightarrow \quad x \equiv (30)^{-1} j\pmod{7}$
É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}$ .
$$A \equiv g^a \pmod{p} \qquad B \equiv g^b \pmod{p}$$
Utils
mimetext/htmlrootassigneelast_run_timestampAڰ`Xpersist_js_state·has_pluto_hook_features$64eb4b52-4946-467c-867a-a6fc437b15f6running§runtime#gdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$64eb4b52-4946-467c-867a-a6fc437b15f6depends_on_disabled_cells¦queued¤logsoutputbodyb
Meet in the middle approach
mimetext/htmlrootassigneelast_run_timestampAڰ`9ְpersist_js_state·has_pluto_hook_features$31388128-33a3-4443-835e-74b91bf48268running§runtime&udepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$31388128-33a3-4443-835e-74b91bf48268depends_on_disabled_cells¦queued¤logsoutputbody4mimetext/plainrootassigneelast_run_timestampAڰ`~wpersist_js_state·has_pluto_hook_features$4714b7d7-32ee-42a1-bfa5-93eafda739d3running§runtime Qdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$4714b7d7-32ee-42a1-bfa5-93eafda739d3depends_on_disabled_cells¦queued¤logsoutputbodyt
Diagonalization to speed up powering
mimetext/htmlrootassigneelast_run_timestampAڰ_:persist_js_state·has_pluto_hook_features$d882afdd-eb85-467c-bf18-525c0c5da5e7running§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$d882afdd-eb85-467c-bf18-525c0c5da5e7depends_on_disabled_cells¦queued¤logsgroupstdoutlinemsg/ 0.000046 seconds (39 allocations: 2.609 KiB)
text/plainlevelLogLevel(-555)idPlutoRunner_40f9f5d1cell_id$d882afdd-eb85-467c-bf18-525c0c5da5e7kwargsfileP/home/runner/.julia/packages/Pluto/sRdkC/src/runner/PlutoRunner/src/io/stdout.jloutputbodyU2.531162323732361578998428490601662084769270923897910687031954402219719762339543e4179mimetext/plainrootassigneelast_run_timestampAڰ`.Mpersist_js_state·has_pluto_hook_features$a7d9703a-5121-4b43-8cd4-2acf9a0d91efrunning§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$a7d9703a-5121-4b43-8cd4-2acf9a0d91efdepends_on_disabled_cells¦queued¤logsoutputbody#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})$ .
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.
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}$ .
$366x \equiv j \pmod{7} \quad \Rightarrow \quad x \equiv (366)^{-1} j\pmod{7}$
Ensemble de solutions: $(x + kb, y - ka)$ pour un $k \in \mathbb{Z}$ arbitraire. Prenons $k$ tel que $0 \le x + kb < b$ avec mod.
Arithmétique modulaire : produit
mimetext/htmlrootassigneelast_run_timestampAڰ^8apersist_js_state·has_pluto_hook_features$18031ccb-657f-409a-9080-9a0ada3ae8b5running§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$18031ccb-657f-409a-9080-9a0ada3ae8b5depends_on_disabled_cells¦queued¤logsoutputbody13 Le nombre 2 est une racine primitive modulo 11
Voir [HPS14; Section 2.7]
Recursive implementation
mimetext/htmlrootassigneelast_run_timestampAڰ^2persist_js_state·has_pluto_hook_features$87fdefa1-3bbd-4b69-ad3a-72baca6e55eerunning§runtime6depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$87fdefa1-3bbd-4b69-ad3a-72baca6e55eedepends_on_disabled_cells¦queued¤logsoutputbody4mimetext/plainrootassigneelast_run_timestampAڰ`@persist_js_state·has_pluto_hook_features$48eba223-6cce-4aa2-9977-4883ba7903fcrunning§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$48eba223-6cce-4aa2-9977-4883ba7903fcdepends_on_disabled_cells¦queued¤logsoutputbodyObservation 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$ .
$365x \equiv j \pmod{7} \quad \Rightarrow \quad x \equiv (365)^{-1} j\pmod{7}$
Dicrete logarithm
mimetext/htmlrootassigneelast_run_timestampAڰ`1npersist_js_state·has_pluto_hook_features$f39cccac-5b24-46e4-8749-1b0a944542efrunning§runtime ydepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$f39cccac-5b24-46e4-8749-1b0a944542efdepends_on_disabled_cells¦queued¤logsoutputbody8mimetext/htmlrootassigneelast_run_timestampAڰ^rߓpersist_js_state·has_pluto_hook_features$c5e906c8-0f73-4955-baa7-337195329e04running§runtime Idepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$c5e906c8-0f73-4955-baa7-337195329e04depends_on_disabled_cells¦queued¤logsoutputbodyÉ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$ .
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}$ .
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]
[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.
mimetext/htmlrootassigneelast_run_timestampAڰc.persist_js_state·has_pluto_hook_features$1e27eedc-5308-4608-863f-fb81d60acdf0running§runtime ~7depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$1e27eedc-5308-4608-863f-fb81d60acdf0depends_on_disabled_cells¦queued¤logsoutputbodyٿQuelle est la complexité? $\mathcal{O}(\sqrt{p}\log(p))$
The complexity is difficult to evaluate but can be shown to be $O(\log(\min(a, b)))$ .
10
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]
Inversion modulaire par Euclide étendu
mimetext/htmlrootassigneelast_run_timestampAڰ^ڭpersist_js_state·has_pluto_hook_features$f6e22fc3-382e-4548-bc59-8f944e06d237running§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$f6e22fc3-382e-4548-bc59-8f944e06d237depends_on_disabled_cells¦queued¤logsoutputbody32×2 Matrix{Float64}:
1.0 1.0
1.0 -1.11022e-16mimetext/plainrootassigneelast_run_timestampAڰ` Vpersist_js_state·has_pluto_hook_features$4ef2c7e9-fb37-4e38-a252-b9c3f83d2a82running§runtimedepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$4ef2c7e9-fb37-4e38-a252-b9c3f83d2a82depends_on_disabled_cells¦queued¤logsoutputbody;mimetext/htmlrootassigneelast_run_timestampAڰ`Yڰpersist_js_state·has_pluto_hook_features$ce07d5c5-90a3-4c12-bada-30e4da1b99fdrunning§runtime<5depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$ce07d5c5-90a3-4c12-bada-30e4da1b99fddepends_on_disabled_cells¦queued¤logsoutputbodyprefixInt64elements 1text/plain2text/plain4text/plain8text/plain16text/plain15text/plain13text/plain9text/plain 1text/plain
2text/plain 4text/plain 8text/plain
16text/plain15text/plain13text/plain9text/plaintypeArrayprefix_shortobjectidb2193a9b14979af5mime!application/vnd.pluto.tree+objectrootassigneelast_run_timestampAڰa)persist_js_state·has_pluto_hook_features$b5f3620d-0942-41bb-80b0-d2ddcfe65090running§runtime e3gdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$b5f3620d-0942-41bb-80b0-d2ddcfe65090depends_on_disabled_cells¦queued¤logsoutputbodyEigen{Float64, Float64, Matrix{Float64}, Vector{Float64}}
values:
2-element Vector{Float64}:
-0.6180339887498948
1.618033988749895
vectors:
2×2 Matrix{Float64}:
0.525731 -0.850651
-0.850651 -0.525731mimetext/plainrootassigneeElast_run_timestampAڰ_ҡpersist_js_state·has_pluto_hook_features$4a98507b-653e-4354-a825-7605f8fcb31brunning§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$4a98507b-653e-4354-a825-7605f8fcb31bdepends_on_disabled_cells¦queued¤logsoutputbodyK4×4 Matrix{Int64}:
1 16 1 16
2 15 2 15
4 13 4 13
8 9 8 9mimetext/plainrootassigneelast_run_timestampAڰa*persist_js_state·has_pluto_hook_features$736307ec-a2a4-11ef-0f85-ad1a0093e06arunning§runtime 9 depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$736307ec-a2a4-11ef-0f85-ad1a0093e06adepends_on_disabled_cells¦queued¤logsoutputbodyZ
La théorie des nombres
mimetext/htmlrootassigneelast_run_timestampAڰZ$kpersist_js_state·has_pluto_hook_features$a7afc0cb-a980-4f4f-b782-9791d932ee52running§runtime udepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$a7afc0cb-a980-4f4f-b782-9791d932ee52depends_on_disabled_cells¦queued¤logsoutputbodyFVoir [HPS14; Section 2.8].
mimetext/htmlrootassigneelast_run_timestampAڰ`$spersist_js_state·has_pluto_hook_features$8a5a251f-5373-445a-97b1-4d652c6b7ba8running§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$8a5a251f-5373-445a-97b1-4d652c6b7ba8depends_on_disabled_cells¦queued¤logsoutputbody%refs (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampAڰbݰpersist_js_state·has_pluto_hook_features$9efb7a71-9a03-4716-8d34-aae233e9b898running§runtime'depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$9efb7a71-9a03-4716-8d34-aae233e9b898depends_on_disabled_cells¦queued¤logsoutputbody8mimetext/plainrootassigneexlast_run_timestampAڰaS persist_js_state·has_pluto_hook_features$6e5e3ec6-c96a-4a4a-bf4d-4b115f9b0d82running§runtime ߸depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$6e5e3ec6-c96a-4a4a-bf4d-4b115f9b0d82depends_on_disabled_cells¦queued¤logsoutputbody*collision (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampAڰ`Ppersist_js_state·has_pluto_hook_features$f4f49568-dcf2-4c76-ba66-065d2fda7a4arunning§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$f4f49568-dcf2-4c76-ba66-065d2fda7a4adepends_on_disabled_cells¦queued¤logsoutputbody$$a \equiv \alpha \pmod{n} \quad \text{et} \quad b \equiv \beta \pmod{n}
\quad \Rightarrow \quad a + b \equiv \alpha + \beta \pmod{n}$$
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}$$
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:
S'il y avait 364 jours par ans, les fêtes seraient toujours le même jour de la semaine!
