Math
Fourier, une période et un facteur
Comparez un pic à son voisin, puis mesurez : un pic suggère un dénominateur, pas un facteur garanti. Modèle CPU idéal, 12 qubits, sans bruit ni appareil réel. Pour N=21, Q=128 < N² : précision réduite. Bases premières avec N ; sinon PGCD(a,N) donne déjà un facteur.
Ce qui se passe
Comparez un pic à son voisin, puis mesurez : un pic suggère un dénominateur, pas un facteur garanti.
Équations du module
Équations Q = 2^t; |ψ⟩ = Q^(-1/2) Σ_(x=0)^(Q−1) |x⟩|a^x mod N⟩ S_z(y) = Σ_(x: a^x mod N=z) exp(2πixy/Q) ; m_z = count(x dans la branche z) P(y sachant z) = |S_z(y)|²/(Q m_z) ; P(z)=m_z/Q P(y) = Σ_z |S_z(y)|²/Q²; Σ_y P(y)=1 y/Q ≈ p/d, 1 ≤ d < N ; vérifier a^d mod N = 1 avant l'extraction du facteur d pair : h=a^(d/2) mod N ; g−=gcd(h−1,N), g+=gcd(h+1,N) n'accepter que 1<g−,g+<N et g−g+=N ; h=±1 mod N est trivial N=15 : t=8, work=4 ; N=21 : t=7, work=5, Q=128<N² (précision réduite) vecteur d'état numérique idéal, 12 qubits ; l'oracle modulaire est une permutation de la base échantillon : frequency=count/n ; SE=sqrt(P(1−P)/n), n>0
