Algorisme de Shor: diferència entre les revisions
Contingut suprimit Contingut afegit
Línia 73:
===Obtenció de factors a partir del període ===
Els nombres enters menors que ''N'' i [[coprimer]]s amb ''N'' formen un [[grup (matemàtiques)|grup]] abelià [[finit]] sota multiplicació [[Aritmètica modular|mòdul]] ''N'', que es denota típicament ('''Z'''/''N'''''Z''')
: <math> a^r \equiv 1 \ \mbox{mod}\ N.\, </math>
Línia 80:
: <math> a^r - 1 = (a^{r/2}- 1) (a^{r/2}+1) \equiv 0 \ \mbox{mod}\N </math>
: <math> \Rightarrow N
''r'' és el nombre enter positiu ''més petit'' tal que ''a''<sup>''r''</sup> ≡ 1, així que ''N'' no pot dividir (''a''<sup>''r''/2 </sup> - 1). Si ''N'' tampoc divideix (''a''<sup>''r''/2 </sup>+1), llavors ''N'' ha de tenir un factor comú no trivial amb (''a''<sup>''r''/2 </sup> - 1) i (''a''<sup>''r''/2 </sup>+1).
'''Prova:''' Per simplicitat,
Això ens
=== II. Trobar el període ===
| |||