h3. Utilizari

Pentru determinarea inversul numarului x modulo un numar prim p: teorema mica a lui fermat ne spune ca x^(p-1)^ modulo p = 1. De aici avem ca inversul lui x este x^(p-2)^ pe care il putem calcula rapid folosind exponentiere rapida. O cale mai generala de a determina inversul unui numar x modulo un numar n, unde n nu este neaparat prim, ar fi folosirea algoritmului lui Euclid extins.

Pentru determinarea inversul numarului x modulo un numar prim p: teorema mica a lui Fermat ne spune ca $x^(p-1)^ modulo p = 1$. De aici avem ca inversul lui $x$ este $x^(p-2)^$ pe care il putem calcula rapid folosind exponentiere rapida. O cale mai generala de a determina inversul unui numar $x$ modulo un numar $n$, unde $n$ nu este neaparat prim, ar fi folosirea algoritmului lui Euclid extins.

Alta tip de probleme unde exponentierea rapida ne este utila ar fi determinarea rapida a valorii modulo n a unui element a[k] unde a este un sir definit printr-o recurenta liniara.

Alta tip de probleme unde exponentierea rapida ne este utila ar fi determinarea rapida a valorii modulo $n$ a unui element $a[k]$ unde $a$ este un sir definit printr-o recurenta liniara.

De exemplu daca sirul a[k] = x a[k - 1] + y a[k - 2] + z a[k - 3], atunci putem defini vectorul (a[k], a[k - 1] , a[k - 2]) fiind dat de inmultirea vectorului (a[k - 1], a[k - 2], a[k - 3) cu matricea A: <tex> \left( \begin{array}{ccc}

De exemplu daca sirul $a[k] = x a[k - 1] + y a[k - 2] + z a[k - 3]$, atunci putem defini vectorul <tex> \left( \begin{array}{ccc}
a[k] \\
a[k - 1] \\
a[k - 2]\end{array} \right)</tex> fiind dat de inmultirea matricii $A$: <tex> \left( \begin{array}{ccc}

x & y & z \\

0 & 1 & 0 \\
0 & 0 & 1 \end{array} \right)</tex>

1 & 0 & 0 \\
0 & 1 & 0 \end{array} \right)</tex> cu vectorul <tex> \left( \begin{array}{ccc}
a[k - 1] \\
a[k - 2] \\
a[k - 3]\end{array} \right)</tex>

Si atunci pentru a determina a[k] modulo n rapid, putem folosi ridicarea la putere a matricii A.

Si atunci pentru a determina $a[k] modulo n$ rapid, putem folosi ridicarea la putere a matricii $A$.

h2. Probleme similare

== include(page="template/taskfooter" task_id="lgput") ==

==SmfTopic(topic_id="2787")==

public

task: lgput

2787