Diferència entre revisions de la pàgina «RSA»

3 bytes afegits ,  fa 8 anys
cap resum d'edició
#Calcula la [[Funció Fi d'Euler]] <math>\phi(n) = (p-1)(q-1) \,</math>.
#Tria un enter <math>e</math> amb <math>1 < e < \phi(n) \,</math> i que sigui [[coprimer]] amb <math>\phi(n) \,</math>.
#Calcula <math>d</math> tal que <math>d e \equiv 1\pmod{\phi(n)}</math>. És a dir <math>d=e^{\phi(n)-1} \,</math>
 
* els nombres primers poden ser comprovats de forma probabilística usant el [[Funció Fi d'Euler|Petit teorema de Fermat]]: <math>a^{(p-1)} \equiv 1 \pmod{p}</math>, si <math>p \,</math> és primer; comprovant amb uns quants valors d'<math>a \,</math> dóna un bona probabilitat de què <math>p \,</math> és primer. (Els [[Nombres de Carmichael]] poden passar la comprovació per a tot <math>a \,</math>, però són extremadament rars.)
*(Els passos 3 i 4 es poden millorar amb l'[[Algorisme ampliat d'Euclides ampliat]]; vegeu [[aritmètica modular]].)
*(El pas 4, alternativament, també es pot considerar com trobar un enter <math>x \,</math> tal que <math>d = \frac{x(p-1)(q-1)+1}{e}</math> és un enter, aleshores usant el valor de <math>d \pmod{(p-1)(q-1)} \,</math>;
*(Del pas 2 PKCS#1 v2.1 usa <math>\lambda = m.c.m(p-1, q-1) \,</math> en lloc de <math>\phi = (p-1)(q-1) \,</math>).
28

modificacions