Pourquoi c'est central. La mécanique quantique est entièrement formulée en algèbre linéaire : les états sont des vecteurs dans un espace de Hilbert, les observables sont des opérateurs linéaires, la mesure est une projection. En cryptographie, les réseaux euclidiens (Kyber, Dilithium) reposent sur l'algèbre des matrices sur ℤ_q, et la transformée de Fourier discrète structure l'algorithme de Shor.
Espace vectoriel sur ℂ›
Fondement QM
Un espace vectoriel V sur ℂ est un ensemble muni d'une addition et d'une multiplication scalaire (par des complexes) satisfaisant 8 axiomes. En QM : les états quantiques vivent dans ℂⁿ ou dans un espace de Hilbert de dimension infinie. La notion clé est la linéarité : toute combinaison linéaire α|ψ₁⟩ + β|ψ₂⟩ est un état valide. C'est le fondement du principe de superposition. Une base orthonormée {|eᵢ⟩} vérifie ⟨eᵢ|eⱼ⟩ = δᵢⱼ (delta de Kronecker).
Produit scalaire hermitien & norme›
Fondement QM
Sur ℂⁿ : ⟨u|v⟩ = Σᵢ ūᵢvᵢ (conjugué complexe de u). Propriétés : sesquilinéarité (⟨u|αv⟩ = α⟨u|v⟩, ⟨αu|v⟩ = ᾱ⟨u|v⟩), hermiticité (⟨u|v⟩ = ⟨v|u⟩*) et positivité (⟨u|u⟩ ≥ 0). La norme est ‖u‖ = √⟨u|u⟩. En QM : ‖|ψ⟩‖ = 1 est la condition de normalisation, et |⟨φ|ψ⟩|² est la probabilité de transition entre états. L'inégalité de Cauchy-Schwarz |⟨u|v⟩|² ≤ ⟨u|u⟩⟨v|v⟩ est à la base du principe d'incertitude de Heisenberg.
Fondement QMKyber/Dilithium
Un opérateur linéaire A : V → V satisfait A(αu+βv) = αAu+βAv. En base finie, A est représentée par une matrice. Types critiques en QM : opérateur hermitien (A† = A) → valeurs propres réelles = observables mesurables. Opérateur unitaire (U†U = I) → préserve les normes = évolution quantique. Opérateur de projection P² = P = P† → effondrement du vecteur d'état. En lattice-crypto : Kyber manipule des matrices A ∈ ℤ_q^(k×k) — la sécurité repose sur la difficulté de inverser As ≈ b avec petit bruit e.
A† = (Aᵀ)* · Hermitien : A = A† · Unitaire : U†U = UU† = IAdjoints et classifications
Valeurs propres & diagonalisation›
Fondement QM
λ est valeur propre de A si ∃v≠0 tel que Av = λv (v = vecteur propre). Le polynôme caractéristique det(A−λI) = 0 donne les valeurs propres. Théorème spectral : tout opérateur hermitien sur un espace de Hilbert est diagonalisable dans une base orthonormée de vecteurs propres, et ses valeurs propres sont réelles. C'est pourquoi les observables quantiques (énergie, spin, position) sont hermitiens — leurs mesures sont des réels. La décomposition spectrale A = Σᵢ λᵢ |eᵢ⟩⟨eᵢ| est fondamentale.
A|eᵢ⟩ = λᵢ|eᵢ⟩ · A = Σᵢ λᵢ|eᵢ⟩⟨eᵢ| · P(λᵢ) = |⟨eᵢ|ψ⟩|²Décomposition spectrale & probabilité de mesure
Produit tensoriel ⊗›
Intrication QM
Le produit tensoriel de deux espaces V (dim m) et W (dim n) donne V⊗W de dimension mn. Pour un système bipartite (Alice + Bob), l'espace d'état est ℂ² ⊗ ℂ² = ℂ⁴. C'est là que réside l'intrication : un état |Φ⁺⟩ = (|00⟩+|11⟩)/√2 ne peut pas s'écrire comme |α⟩⊗|β⟩ — il est non-séparable. Mathématiquement, un état est intriqué si et seulement s'il n'est pas un produit tensoriel de deux états. La dimension croît exponentiellement avec le nombre de qubits : n qubits → ℂ^(2ⁿ).
Algorithme de Shor
La DFT transforme un vecteur (x₀,...,x_{N-1}) en (X₀,...,X_{N-1}) via Xₖ = Σⱼ xⱼ · ωₙ^(jk), où ωₙ = e^(2πi/N). La matrice DFT est unitaire (F†F = I) — c'est un opérateur quantique valide. En QM : la QFT (Quantum Fourier Transform) est l'analogue quantique. Pour Shor, la QFT détecte la période r de f(x) = aˣ mod N en O((log N)²) portes. La QFT sur n qubits agit sur 2ⁿ amplitudes simultanément — c'est l'avantage exponentiel quantique. La FFT classique fait O(N log N), la QFT fait O(n²) = O(log²N).
QFT|j⟩ = (1/√N) Σₖ e^(2πijk/N)|k⟩ · N = 2ⁿQuantum Fourier Transform sur n qubits
SVD — Décomposition en valeurs singulières›
Réseaux euclidiens
Toute matrice A ∈ ℂ^(m×n) se décompose A = UΣV†, où U, V sont unitaires et Σ est diagonale (valeurs singulières σᵢ ≥ 0). En cryptographie sur réseaux : la condition spectrale de A (rapport σ_max/σ_min) mesure la qualité d'une base de réseau — une bonne base a des valeurs singulières proches, une mauvaise base a un grand ratio. L'algorithme LLL (Lenstra-Lenstra-Lovász) réduit une mauvaise base en une meilleure en temps polynomial. La sécurité de Kyber repose sur le fait qu'une base aléatoire est presque toujours "mauvaise".
Matrice densité ρ›
États mixtes QM
Un état quantique pur |ψ⟩ est décrit par ρ = |ψ⟩⟨ψ| (projecteur de rang 1). Un état mixte — mélange statistique — est ρ = Σᵢ pᵢ|ψᵢ⟩⟨ψᵢ| avec Σpᵢ = 1. Propriétés : ρ = ρ† (hermitien), Tr(ρ) = 1, ρ ≥ 0 (semi-définie positive). Test de pureté : Tr(ρ²) = 1 (pur), Tr(ρ²) < 1 (mixte). La décohérence transforme des états purs en états mixtes — les termes hors-diagonaux (cohérences) s'annulent. La matrice réduite ρ_A = Tr_B(ρ_AB) quantifie l'entropie d'intrication.
ρ = Σᵢ pᵢ|ψᵢ⟩⟨ψᵢ| · Tr(ρ)=1 · S(ρ) = −Tr(ρ log ρ)Matrice densité & entropie de von Neumann
Démo interactive — Produit scalaire & projection
θ (angle)45°‖v‖80
Le vecteur vert est u = (1,0) (base canonique). Le vecteur or est v(θ). La projection de v sur u est ⟨u|v⟩ = cos θ (affiché en bleu). L'angle entre deux vecteurs est directement lié à leur produit scalaire via cos θ = ⟨u|v⟩ / (‖u‖‖v‖).
Corps finis & Arithmétique modulaire — Le langage de la cryptographie classique
Pourquoi c'est central. RSA, DH, AES, les courbes elliptiques — tout repose sur l'arithmétique dans des corps finis. ℤ/nℤ (entiers mod n), 𝔽_p (corps premier), 𝔽_{2^n} (corps de caractéristique 2). La notion de groupe cyclique, d'ordre, et de problème du logarithme discret est le cœur de la cryptographie à clé publique.
Arithmétique modulaire — ℤ/nℤ›
RSA · DH
a ≡ b (mod n) si n | (a−b). Les opérations +, −, × se font modulo n. L'inverse multiplicatif de a mod n existe si et seulement si gcd(a,n) = 1 (algorithme d'Euclide étendu). Le théorème de Fermat-Euler : a^φ(n) ≡ 1 (mod n) si gcd(a,n)=1, où φ(n) est l'indicatrice d'Euler. RSA repose directement sur ce théorème : (mᵉ)ᵈ ≡ m (mod n) car ed ≡ 1 (mod φ(n)).
Diffie-Hellman
𝔽_p = ℤ/pℤ est un corps quand p est premier : tout élément non-nul a un inverse. Le groupe multiplicatif 𝔽_p* est cyclique d'ordre p−1 : il existe un générateur g tel que {g¹, g², ..., g^(p-1)} = 𝔽_p*. Le problème du logarithme discret (DLP) : étant donné g, p et A = gᵃ mod p, retrouver a. Computationnellement infaisable pour p ≥ 2048 bits (meilleur algo connu : Number Field Sieve, sous-exponentiel). Diffie-Hellman repose entièrement sur ce problème.
A = gᵃ mod p (facile) · a = log_g A mod p (difficile) · DH: K = gᵃᵇ mod pLogarithme discret & échange DH
Corps de Galois 𝔽_{2^8} — GF(256)›
AES
𝔽_{2^8} est le corps à 256 éléments construit comme ℤ_2[x] / p(x), où p(x) = x⁸+x⁴+x³+x+1 est le polynôme irréductible d'AES. Chaque élément est un polynôme de degré ≤ 7 à coefficients dans {0,1}, représenté par un octet. La multiplication est la multiplication polynomiale modulo p(x) — pas la multiplication entière mod 256. L'opération MixColumns d'AES est une multiplication matricielle dans 𝔽_{2^8}. La S-box SubBytes est l'inversion dans 𝔽_{2^8} suivie d'une transformation affine.
𝔽_{2^8} = 𝔽_2[x] / (x⁸+x⁴+x³+x+1)Corps de Galois utilisé par AES
Théorème des restes chinois (CRT)›
RSA · NTT
Si n₁, n₂, ..., nₖ sont deux à deux premiers entre eux, alors le système x ≡ aᵢ (mod nᵢ) a une solution unique mod N = n₁n₂...nₖ. En cryptographie : la déchiffrement RSA-CRT accélère le calcul m^d mod n en calculant séparément mod p et mod q, puis combine — gain de 4× en vitesse. En algèbre des réseaux (NTT) : la Number Theoretic Transform utilise le CRT pour multiplier des polynômes mod q en O(n log n), crucial pour la performance de Kyber et Dilithium.
Courbes elliptiques sur 𝔽_p›
ECDH · ECDSA
Une courbe elliptique E sur 𝔽_p est l'ensemble {(x,y) ∈ 𝔽_p² : y² = x³+ax+b} ∪ {∞}, avec 4a³+27b² ≠ 0. L'addition de points est définie géométriquement (corde-tangente) et forme un groupe abélien. La multiplication scalaire kP = P+P+...+P (k fois) est rapide avec double-and-add. ECDLP : étant donné P et Q = kP, retrouver k est infaisable. Avantage : sécurité équivalente à RSA avec des clés ~10× plus petites (256 bits ECDH ≈ 3072 bits RSA).
Kyber · Dilithium
L'anneau R_q = ℤ_q[x]/(xⁿ+1) est la structure algébrique de Kyber (n=256, q=3329). La multiplication de deux polynômes dans R_q est l'opération fondamentale — coûteuse naïvement en O(n²), mais la NTT (Number Theoretic Transform) la réduit à O(n log n) si q est un premier NTT-friendly (q ≡ 1 mod 2n). Le problème MLWE ("Module Learning With Errors") dans cet anneau est la fondation de sécurité : étant donné A·s + e = b mod q (A public, s secret, e petit bruit), retrouver s est infaisable.
R_q = ℤ_q[x]/(xⁿ+1) · MLWE: b = As + e, retrouver sAnneau de Kyber (n=256, q=3329)
Calcule gcd(a,n), l'inverse modulaire de a mod n (si gcd=1), et l'exposant RSA d tel que e·d ≡ 1 (mod φ(n)) avec e=a.
Nombres complexes & Analyse complexe — La géométrie des amplitudes
Pourquoi c'est central. Les amplitudes quantiques sont des nombres complexes. L'exponentielle complexe e^(iθ) = cos θ + i sin θ (formule d'Euler) est omniprésente : dans les états propres de l'énergie (e^(−iEt/ℏ)), dans la QFT (ωₙ = e^(2πi/N)), dans les matrices de rotation de spin (e^(iθσ/2)). Comprendre ℂ géométriquement, c'est comprendre pourquoi l'interférence quantique fonctionne.
Forme polaire & formule d'Euler›
Amplitudes QM
z = a+ib = r·e^(iθ), avec r = |z| (module) et θ = arg(z) (argument). La formule d'Euler : e^(iθ) = cos θ + i sin θ. Conséquence remarquable : e^(iπ) + 1 = 0. En QM : un état |ψ⟩ = α|0⟩ + β|1⟩ peut s'écrire α = cos(θ/2), β = e^(iφ)sin(θ/2) — les angles θ et φ paramétrisent la sphère de Bloch. La phase globale e^(iγ)|ψ⟩ est non-observable, mais la phase relative entre termes est physique et produit l'interférence.
e^(iθ) = cos θ + i sin θ · e^(iπ)+1=0 · |ψ⟩ = cos(θ/2)|0⟩ + e^(iφ)sin(θ/2)|1⟩Euler & sphère de Bloch
Conjugué complexe & module›
Règle de Born
Si z = a+ib, le conjugué est z* = a−ib. |z|² = z·z* = a²+b². En QM, la règle de Born : la probabilité d'obtenir le résultat associé à l'état |φ⟩ en mesurant |ψ⟩ est P = |⟨φ|ψ⟩|² = ⟨φ|ψ⟩·⟨φ|ψ⟩*. Le carré du module est nécessaire (et suffisant) pour passer des amplitudes complexes aux probabilités réelles. C'est le pont entre le formalisme mathématique et les observations. La conjugaison apparaît aussi dans la définition de l'adjoint : (AB)† = B†A†.
Racines de l'unité & DFT›
QFT · Shor
Les racines N-ièmes de l'unité sont ωₙ = e^(2πik/N) pour k = 0,...,N−1. Elles forment un groupe cyclique de ℂ*. Géométriquement : N points régulièrement espacés sur le cercle unité. La DFT est essentiellement la multiplication par la matrice de Vandermonde de ces racines. En QFT : la transformée de Fourier quantique sur N=2ⁿ états agit sur les amplitudes complexes — c'est une rotation dans ℂ^N qui révèle les périodes. L'algorithme de Shor détecte la période r de aˣ mod N via les pics dans le spectre de la QFT.
Qubits
Les matrices de Pauli σₓ, σᵧ, σ_z sont hermitiens, unitaires, et de trace nulle. σ_z = [[1,0],[0,-1]] (observable spin Z), σₓ = [[0,1],[1,0]] (porte X/NOT), σᵧ = [[0,-i],[i,0]]. Relation : σᵢσⱼ = δᵢⱼI + iεᵢⱼₖσₖ. Rotations de qubit : toute porte à 1 qubit est une rotation sur la sphère de Bloch : R_n(θ) = e^(−iθn·σ/2) = cos(θ/2)I − i sin(θ/2)(n·σ), avec n l'axe. Porte H = (σₓ+σ_z)/√2. Porte T = e^(iπ/8·σ_z).
σ_z = diag(1,−1) · σₓ=[[0,1],[1,0]] · H=(σₓ+σ_z)/√2Matrices de Pauli & portes quantiques
Démo — Plan complexe & multiplication par e^(iθ)
θ (rotation)45°Re(z)0.7
Le point orange est z = Re(z) + i·Im(z). Multiplier par e^(iθ) effectue une rotation de θ autour de l'origine (point vert). C'est exactement ce que fait l'évolution temporelle quantique e^(−iHt/ℏ) sur le vecteur d'état — une rotation dans l'espace de Hilbert.
Probabilités & Théorie de l'information — Shannon, entropie, Bayes
Pourquoi c'est central. La mécanique quantique est probabiliste à son cœur (règle de Born). La sécurité cryptographique se quantifie en entropie (Shannon). BB84 se prouve via la théorie de l'information quantique. IIT (conscience) utilise Φ, une mesure d'information intégrée. Et Bayes est le fondement de la mise à jour des croyances — y compris en QBism.
Entropie de Shannon H(X)›
Sécurité cryptographique
H(X) = −Σᵢ pᵢ log₂(pᵢ) (bits). Mesure l'incertitude d'une variable aléatoire X. Maximum : H = log₂(n) pour une distribution uniforme sur n valeurs. Minimum : H = 0 si un résultat est certain. En cryptographie : la longueur minimale d'une clé doit satisfaire H(K) ≥ log₂(2^λ) = λ bits. La sécurité d'un chiffrement se réduit à l'entropie de la clé. Le masque jetable (OTP) est sûr car H(K) = H(M) → H(M|C) = H(M) : le chiffré ne révèle rien. Amplification de confidentialité dans BB84 : la privacy amplification réduit H(K|Eve) → 0 par hachage universel.
H(X) = −Σᵢ pᵢ log₂ pᵢ · H_max = log₂ n · H(M|C)=H(M) → OTPEntropie de Shannon
Entropie de von Neumann S(ρ)›
Intrication QM
S(ρ) = −Tr(ρ log ρ) = −Σᵢ λᵢ log λᵢ (où λᵢ = valeurs propres de ρ). S(ρ) = 0 pour un état pur, S(ρ) = log d pour l'état maximalement mixte (ρ = I/d). Entropie d'intrication : pour un état bipartite pur |ψ_AB⟩, E(|ψ_AB⟩) = S(ρ_A) = S(ρ_B) mesure le degré d'intrication. Pour les états de Bell : E = 1 ebit (maximum pour 2 qubits). Pour un état produit : E = 0. Lien IIT : Φ (phi) mesure l'information au-delà de la somme des parties — une généralisation de S pour les systèmes causaux.
QKD · BB84
I(X;Y) = H(X) − H(X|Y) = H(X) + H(Y) − H(X,Y). Mesure ce qu'Alice et Bob partagent. En QKD : la preuve de sécurité de BB84 montre que la clé finale est sûre si I(Alice;Bob) − I(Alice;Eve) > 0 après réconciliation et amplification. Le taux de clé sécurisée est r ≥ I(A;B) − I(A;E). Si Eve intercepte, I(A;E) > 0 mais le QBER révèle son existence. La divergence de Kullback-Leibler D_KL(P||Q) = Σ pᵢ log(pᵢ/qᵢ) mesure la "distance" entre distributions — utilisée en apprentissage automatique pour l'optimisation.
QBism · Cryptanalyse
P(A|B) = P(B|A)·P(A) / P(B). Permet de mettre à jour une croyance (P(A) → P(A|B)) à la lumière d'une observation B. En QBism : la fonction d'onde est la distribution de croyances d'un agent — "l'effondrement" est une mise à jour bayésienne, pas un phénomène physique. En cryptanalyse : les attaques par canal auxiliaire (side-channel) utilisent la corrélation bayésienne entre mesures de puissance et valeurs de clé. Les algorithmes de décodage probabiliste (LDPC, Turbo codes) pour la réconciliation d'information dans BB84 sont des variantes d'inférence bayésienne (algorithme belief-propagation).
Distributions et inégalités clés›
Sécurité prouvableDistribution uniforme sur {0,1}ⁿ : entropie maximale n bits — idéale pour les clés cryptographiques. Inégalité de Markov : P(X ≥ a) ≤ E[X]/a. Inégalité de Chebyshev : P(|X−μ| ≥ k·σ) ≤ 1/k². Lemme de Chernoff/Hoeffding : les déviations d'une somme de variables i.i.d. sont exponentiellement improbables — fondement des preuves de sécurité cryptographique (aucun adversaire PPT ne peut distinguer un chiffré aléatoire en temps polynomial avec prob. non-négligeable). Fonction de la fuite d'information : si Eve obtient m bits d'information, la clé peut être raccourcie de m bits via privacy amplification.
Démo — Entropie de Shannon en fonction de p
p (Bernoulli)0.50
H(p) = −p·log₂(p) − (1−p)·log₂(1−p). Maximum à p=0.5 : H=1 bit (incertitude maximale). Minimum à p=0 ou p=1 : H=0 (certitude). La clé d'un bit doit avoir p=0.5 pour être sécurisée — n'importe quel biais réduit l'entropie effective.
Analyse, espaces de Hilbert & équations différentielles
Pourquoi c'est central. L'équation de Schrödinger est une équation différentielle aux dérivées partielles dans un espace de Hilbert de dimension infinie. Les fonctions d'onde sont des éléments de L²(ℝ) — l'espace des fonctions de carré intégrable. La transformée de Fourier continue connecte position et impulsion. Les séries de Fourier/Taylor servent à développer les solutions.
Espace L²(ℝ) & fonctions d'onde›
Schrödinger
L²(ℝ) = {f : ℝ → ℂ | ∫|f(x)|²dx < ∞} muni du produit scalaire ⟨f|g⟩ = ∫f*(x)g(x)dx. C'est un espace de Hilbert de dimension infinie — l'espace naturel des fonctions d'onde ψ(x). La condition de normalisation ∫|ψ(x)|²dx = 1 assure que P(x)dx = |ψ(x)|²dx est une densité de probabilité. Les fonctions propres de l'hamiltonien forment une base orthonormée de L² — les énergies discrètes émergent des conditions aux limites. La base {|x⟩} (position) et {|p⟩} (impulsion) sont deux bases continues reliées par la transformée de Fourier.
Transformée de Fourier continue & dualité x↔p›
Principe d'incertitude
ψ̃(p) = (1/√(2πℏ)) ∫ ψ(x) e^(−ipx/ℏ) dx. La transformée inverse : ψ(x) = (1/√(2πℏ)) ∫ ψ̃(p) e^(ipx/ℏ) dp. L'opérateur impulsion est p̂ = −iℏ∂/∂x dans la représentation position, et x̂ = iℏ∂/∂p dans la représentation impulsion. La relation de commutation [x̂, p̂] = iℏ est la source algébrique du principe d'incertitude ΔxΔp ≥ ℏ/2. Une fonction très localisée en x (petit Δx) a une transformée de Fourier très étalée (grand Δp) — c'est le théorème de Heisenberg-Fourier.
Schrödinger · Évolution
L'équation de Schrödinger dépendante du temps iℏ∂ψ/∂t = Ĥψ est une EDP linéaire du premier ordre en t et du second en x (via Ĥ = −ℏ²/2m · ∂²/∂x² + V). Solution formelle : ψ(t) = e^(−iĤt/ℏ)|ψ(0)⟩ — l'exponentielle d'opérateur définie par la série de Taylor. Pour Ĥ indépendant de t, la solution se sépare : ψ(x,t) = Σₙ cₙ φₙ(x) e^(−iEₙt/ℏ). Les φₙ sont les états propres (équation de Schrödinger stationnaire Ĥφₙ = Eₙφₙ). Le facteur e^(−iEt/ℏ) est une rotation dans ℂ — la phase accumule linéairement avec le temps.
OHQ · Hydrogène
Les polynômes de Hermite Hₙ(x) sont les fonctions propres de l'oscillateur harmonique : ψₙ(x) = Nₙ Hₙ(x) e^(−x²/2). Ils forment une base orthogonale de L²(ℝ, e^(−x²)). Les polynômes de Legendre Pₗ(cos θ) apparaissent dans l'atome d'hydrogène (orbitales s, p, d...). Les polynômes de Laguerre Lₙ(r) décrivent la partie radiale. Ces familles sont liées par des équations de récurrence, ce qui permet de calculer Hₙ efficacement. En QC : les polynômes de Hermite interviennent dans la décomposition de circuits optiques quantiques continus (modes gaussiens).
Développements en séries — Taylor, exponentielle d'opérateur›
Portes quantiques
e^A = Σₙ Aⁿ/n! (convergente pour tout opérateur borné). Pour A = iθH avec H hermitien : e^(iθH) est unitaire. Formule de Baker-Campbell-Hausdorff (BCH) : e^A e^B = e^(A+B+[A,B]/2+...) — cruciale pour composer des portes quantiques. La série de Taylor permet d'approximer : cos θ = 1−θ²/2+... et sin θ = θ−θ³/6+... interviennent dans toutes les décompositions de portes. En simulation quantique (Trotterisation), e^(i(A+B)t) ≈ (e^(iAt/n)e^(iBt/n))ⁿ avec erreur O(t²/n).
e^A = Σₙ Aⁿ/n! · e^(iθH) unitaire si H† = H · BCH: e^Ae^B = e^(A+B+[A,B]/2+…)Exponentielle matricielle & composition de portes
Théorie des groupes & Algèbre abstraite — La structure derrière la cryptographie
Pourquoi c'est central. Un groupe est la structure minimale permettant de définir la "réversibilité" — et la cryptographie à clé publique repose sur des groupes où certaines opérations sont faciles dans un sens et infaisables dans l'autre. Les courbes elliptiques, DH, RSA sont tous des problèmes dans des groupes spécifiques. En QM, les symétries physiques correspondent à des représentations de groupes (groupe de rotation SU(2), groupe de Lorentz).
Groupes — définition et exemples clés›
Structure fondamentale
(G, ·) est un groupe si : fermeture (a·b ∈ G), associativité, élément neutre e (a·e = a), et inverse (∀a, ∃a⁻¹). Exemples cryptographiques : (ℤ/nℤ, +) groupe additif cyclique d'ordre n — base de RSA. 𝔽_p* groupe multiplicatif d'ordre p−1 — base de DH. E(𝔽_p) groupe des points d'une courbe elliptique — base ECDH. (ℤ/pℤ)[x]/(xⁿ+1)* — base de Kyber. Ordre d'un élément g : le plus petit k tel que gᵏ = e. Pour DH, la sécurité dépend du fait que g soit un générateur d'ordre (p−1) entier.
Groupes cycliques & théorème de Lagrange›
DH · RSA
G est cyclique si ∃g tel que G = {gⁿ | n ∈ ℤ}. Théorème de Lagrange : l'ordre de tout sous-groupe H de G fini divise |G|. Corollaire : g^|G| = e pour tout g ∈ G. Application à RSA : (ℤ/pqℤ)* a ordre φ(pq) = (p−1)(q−1). Lagrange implique m^φ(pq) ≡ 1 (mod pq) — c'est exactement ce qui permet de construire ed ≡ 1 (mod φ(n)) pour que le déchiffrement inverse le chiffrement. Application à Shor : la période de aˣ mod N est l'ordre de a dans (ℤ/Nℤ)*, et Lagrange borne cette période par φ(N).
SU(2) — groupe de rotation des qubits›
QM · Spin
SU(2) est le groupe des matrices 2×2 complexes unitaires de déterminant 1. Tout élément s'écrit U = e^(−iθ n·σ/2). SU(2) est isomorphe (2-pour-1) au groupe SO(3) des rotations de ℝ³ — c'est pour ça qu'un spin-1/2 revient à l'état initial après une rotation de 4π, pas 2π (phase −1 après 2π). Les représentations irréductibles de SU(2) sont étiquetées par le spin j = 0, 1/2, 1, 3/2... Les qubits sont des spineurs de SU(2). En QC : tout circuit à 1 qubit est un élément de SU(2) — la sphère de Bloch est l'espace homogène SU(2)/U(1).
SU(2) = {U ∈ M₂(ℂ) | U†U=I, det(U)=1} · U = e^(-iθn·σ/2)Groupe de rotation des qubits
Anneaux, idéaux & polynômes›
Kyber · Dilithium
Un anneau (R, +, ×) est un groupe abélien pour + avec une multiplication associative et distributive. Un idéal I ⊂ R est un sous-ensemble fermé par + et par multiplication par R. L'anneau quotient R/I est fondamental : ℤ/nℤ = ℤ/(n), ℤ_q[x]/(xⁿ+1) pour Kyber. La réduction modulo un polynôme irréductible crée un corps (si l'idéal est maximal). En LWE : le problème Module-LWE vit dans R_q^(k×k) — les matrices de l'anneau. La structure de l'anneau (xⁿ ≡ −1) crée des propriétés de quasi-cyclicité qui accélèrent les calculs via NTT.
Théorie des nombres — premiers, factorisation›
RSA · Shor
Théorème fondamental de l'arithmétique : tout entier > 1 se factorise de manière unique en produit de nombres premiers. Algorithmes de factorisation classiques : Crible de Fermat, p−1 de Pollard (si p−1 friable), ρ de Pollard (O(N^(1/4))), Number Field Sieve (sous-exponentiel, NFS). Pour RSA-2048 : NFS requiert ~10²² opérations — hors de portée. Shor : factorisation en O(log³N) opérations quantiques via QFT + recherche de période. La sécurité de RSA s'effondre entièrement avec un QC à ~4000 qubits logiques (dont ~10⁷ physiques aux taux d'erreur actuels).
NFS classique: exp(O((log N)^(1/3))) · Shor quantique: O((log N)³)Complexité de la factorisation