arithmetique-cryptologie

\(\forall a \in {\mathbb{F}}_{p}^{\times},\text{ ord}(a)~|~p - 1\) \[\begin{array}{r} a^{p - 1} = a^{b\text{ ord}(a)} = \left( a^{\text{ord}(a)} \right)^{b} = 1^{b} = 1 \\ a^{p - 1} = 1\text{ mod }p \\ \text{donc }a^{p} = a\text{ mod }p \end{array}\]

Montrons \(\forall n \in {\mathbb{N}},\mathcal{P(n)}:\) “dans un anneau commutatif intègre un polunome non nul de degré n possède au plus n racines” par récurrence sur n.

Initialisation: \(\mathcal{P}(0)\): Le polynome constant possède 0 racine

Hérédité:
Soit \(n \in {\mathbb{N}}\) tq \(\mathcal{P}(n - 1)\). Soit P un polynome de degré \(n + 1\)

Bon voilà

On cherche l’ordre de 5 dans \({\mathbb{F}}_{23}^{\times}\) \({\mathbb{F}}_{p}^{\times}\) est d’ordre \(p - 1 = 22 = 11 \times 2\)

D’après le théorème de Lagrange, l’ordre d’un élément divise l’ordre du groupe

donc l’ordre de 5 divise 22

• 1: \(5^{1} = 5 \neq 1\text{ mod }3\)

• 2: \(5^{2} = 25 = 2 \neq 1\text{ mod }3\)

• 11: \(5^{11} = \left( 5^{2} \right)^{5} \times 5 = 22 \neq 1\text{ mod }3\)

• 22 reste le seul ordre possible par élimination

Donc 5 est d’ordre \(22 = p - 1\) donc 5 est un générateur de \({\mathbb{F}}_{23}^{X}\)

\(x = 1\operatorname{mod}9 \Leftrightarrow x = 1 + 9k,k \in {\mathbb{Z}}\)
\(\begin{aligned} x = 2\operatorname{mod}8 & \Leftrightarrow 1 + 9k = 2\operatorname{mod}8 \\ & \Leftrightarrow k = 1\operatorname{mod}8 \\ & \Leftrightarrow k = 1 + 8t \end{aligned}\)
\(\ldots \Leftrightarrow t = 4 + 5u\)
\(\ldots \Leftrightarrow u = 6 + 7v\)
On reporte dans le système \(x = 2458 + 2520v\) donc \(x = 2458\operatorname{mod}2520\)

Il y a des formules de con mais non notés car vraiment formules de con

Soit \(d\) vérifiant cette hypothèse. On a alors \(7d = 1\operatorname{mod}20 \Leftrightarrow d = 3\operatorname{mod}20\).

on veut calculer \(14^{3}\operatorname{mod}33\)

\(\begin{cases} c_{p} = 14 = 2\operatorname{mod}3 \\ m_{q} = 14^{3} = 2\operatorname{mod}11 \end{cases}\)

\(\text{pgcd}(a,n) = 1 \Rightarrow a\text{ inversible }\operatorname{mod}n\)

Par déf \(\text{ord}\left( \left( {{\mathbb{Z}}/n{\mathbb{Z}}} \right)^{\times} \right) = \text{ card}\left( \left( {{\mathbb{Z}}/n{\mathbb{Z}}} \right)^{\times} \right) = \varphi(n)\)

Théorème de Lagrange: \(a \in \left( {{\mathbb{Z}}/n{\mathbb{Z}}} \right)^{\times},\text{ ord}(a)~|~\text{ord}\left( \left( {{\mathbb{Z}}/n{\mathbb{Z}}} \right)^{\times} \right) = \varphi(n)\) donc \(\varphi(n) = l\text{ ord}(a)\) donc \(a^{\varphi(n)} = a^{l \times \text{ ord}(a)} = 1^{l} = 1\operatorname{mod}n\)

Énoncé: Soit \(a \in {\mathbb{Z}}\) et \(p\) premier, alors \(a^{p} = a\operatorname{mod}p\)

• Si a est multiple de \(p\): \(a = lp\), \((lp)^{p} = 0\operatorname{mod}p = p\operatorname{mod}p\)

• Si a est n’est pas multiple de \(p\) \(\Rightarrow \text{pgcd}(a,p) = 0\). D’après 1, \(a^{\varphi(n)} = 1\operatorname{mod}p\) et \(\varphi(n) = p - 1\) donc on multiplie par \(a\), on a le résultat

cf fiche.

Si:

• \(m = 0\) \(\left( 0^{e} \right)^{d} = 0\operatorname{mod}n\)

• \(m\) est premier avec \(n\). On dait que \(ed = 1\operatorname{mod}\varphi(n) \Leftrightarrow ed = 1 + k\varphi(n)\)
  donc \(m^{ed} = m^{1 + k\varphi(n)} = m \times 1\operatorname{mod}n\)

• \(m\) n’est pas premier avec \(n\) \(n\) multiple de \(p\), premier avec \(q\) ou m multiple de \(q\), premier avec \(p\) cas symétriques, on suppose que \(m\) est multiple de \(p\) et premier avec \(q\).
  p et q étant premiers entre eux, on peut appliquer le th des restes chinois. On a alors \(m\operatorname{mod}p = 0,m\operatorname{mod}q = m_{q}\). On a alors \(m_{q}^{ed} = m_{q}\operatorname{mod}q\) car \(m^{\varphi(q)} = 1\operatorname{mod}q\) et \(ed = 1 + k\varphi(p)\varphi(q)\). On a donc \(\begin{cases} x = 0\operatorname{mod}p \\ x = m_{q}\operatorname{mod}q \end{cases}\). \(m\) vérifie cette équation, et d’après le théorème chinois c’est l’unique solution.

Page incomplète ou erronée? Contribuez sur le repo