Lényegében egy olyan algoritmus amely képes meghatározni hogy 12-nek az 1356-ik hatványa mennyivel egyenlő. Amit lehetne bruteforce-al ami ugye úgy nézne ki hogy (12*12*12*12....) és ez 1356-szor elvégezni amit nem is nagyon tudhatnánk letárolni.... vagyis csak nagy nehézségek árán. De mint mindenből van egy kicsit szebb, egy kicsit jobb így erre is van egy elegáns megodás. Ez nem mondja ki konkrétan hogy ennyivel, vagy annyival egyenlő a mi hatványunk hanem zárt alakban adja meg.Forrás atovább után---->>
#include<iostream>
using namespace std;
int
main ()
{
int alap, kitevo, modulus;
int i, s, seged, maradek, j, b, q;
b = 1;
cout << "Add meg az alapot: ";
cin >> alap;
cout << "Add meg a kitevot: ";
cin >> kitevo;
cout << "Add meg a modulust: ";
cin >> modulus;
seged = 2;
s = 1;
while (seged <= kitevo)
{
seged = seged * 2;
s++;
}
int bintomb[s];
int kimenet[s];
int segedes[s];
seged = 1;
while (seged < kitevo)
{
seged = seged * 2;
}
if ((kitevo - seged) == 0)
{
bintomb[0] = 1;
for (i = 1; i < s; i++)
bintomb[i] = 0;
j = s;
}
if (kitevo < seged)
{
seged = seged / 2;
j = 0;
while (seged >= 1)
{
if (kitevo > seged)
{
bintomb[j] = 1;
kitevo = kitevo - seged;
seged = seged / 2;
j++;
}
if (kitevo < seged)
{
bintomb[j] = 0;
seged = seged / 2;
j++;
}
if (kitevo == seged)
{
bintomb[j] = 1;
kitevo = kitevo - seged;
seged = seged / 2;
j++;
} } }
cout << "A kitevő bináris repije:";
for (i = 0; i < s; i++)
cout << bintomb[i] << " ";
cout << endl;
seged = alap;
kimenet[0] = alap;
for (i = 1; i < s; i++)
{
kimenet[i] = ((seged * seged) % modulus);
seged = ((seged * seged) % modulus);
}
cout << "Segéd tömb elemei: ";
for (i = 0; i < s; i++)
cout << kimenet[i] << " ";
cout << endl;
q = s - 1;
for (i = 0; i < s; i++)
{
segedes[q] = bintomb[i];
q--;
}
for (i = 0; i < s; i++)
if (segedes[i] == 1)
b = b * kimenet[i];
cout << "A megadott hatvány = " << (b %modulus) << " mod " << modulus << endl;
return 0;
}
Kimenete:
Add meg az alapot: 2
Add meg a kitevot: 145
Add meg a modulust: 167
A kitevő bináris repije:1 0 0 1 0 0 0 1
Segéd tömb elemei: 2 4 16 89 72 7 49 63
A megadott hatvány = 54 mod 167
Ebből tovább menve a Fermat féle prímteszt is előállítható, aminek az alakja az hogy adott egy bazi nagy szám ami felírható valamilyen 'a' hatványaként, ekkor a kitevő legyen 'p'. De ez csak egy propabilisztikus prímteszt, ami röviden annyit tesz hogy valamilyen valséggel rámondja az adott számra hogy prím-e. Ennek a valsége egyenlő az 1/(2 az N-ediken) ahol N jelőli a próbák számát. Visszakanyarodva a lényegre tehát 'a'-nak a (p-1) hatványa kongruens 1-el mod 'p' ha ez teljesül akkor van rá esély hogy a számunk prím. Erre egy példa:
Add meg az alapot: 15
Add meg a kitevot: 130
Add meg a modulust: 131
A kitevő bináris repije:1 0 0 0 0 0 1 0
Segéd tömb elemei: 15 94 59 75 123 64 35 46
A megadott hatvány = 1 mod 131
De azért csak esély, mert vannak olyan összetett számok melyekre szintén teljesül ez az egyenlet, de ezek nem prímek.
