Potegowanie szybkie modulo

Witam,
Mam problem ze zrozumieniem szybkiego potęgowania modulo. Chcę pominąć szczegół implementacyjny tzn. na chwile obecną nie chcę używać operacji bitowych (z góry dziękuje za wyrozumiałość). Zajmę się tym później, bo chcę najpierw dobrze zrozumieć ideę. Moja liczba jest zapisana w tablicy znakowej i jest odwrócona (tzn. po odwróceniu tablicy otrzymam bity w odpowiedniej kolejności). Wiem, że użycie strlen jest nieotymalne, ale chodzi mi o samą ideę. Jest w sieci mnóstwo kodów, a ja chcę to zrozumieć.

a^k
a - liczba podnoszona do potęgi
k - szereg, czyli liczba naturalna rozbita na sumę potęg liczby 2, po zsumowaniu daje wykladnik w postaci liczby naturalnej
dzięki własnościom potęg mogę to zamienić a podniesione do szeregu na iloczyn liczb, który zwracając da mi liczbę której poszukuje (z własności potęg)

int potega_modulo(int liczba, int modulo, char* wykladnik)
{
  int zwracana = 1, wykladnik, wynik_czesciowy;
  int ilosc_iteracji = strlen(tablica);
  liczba = liczba % modulo;
  // tablica jest domyslne odwrocona
  for(int j = 0; j <= ilosc_iteracji; ++j) {
    if(tablica[j] == '1') {
      wykladnik = pow(2, j);
      wynik_czesciowy = pow(liczba, wykladnik);
      zwracana = (zwracana * wynik_czesciowy) % modulo;
    }
  }
  
  return zwracana;
}

To zwraca dobre wyniki, ale nie wykonuje tego tak jak trzeba, ponieważ obliczam na piechotę wykładnik oraz przemnażam po kolei wszystkie składniki.

1. Jak wyeliminować użycie funkcji pow? Z jej użyciem raczej nie jest to szybkie potęgowanie, tylko przekombinowane potęgowanie zwykłe.

W potęgowaniu binarnym chodzi o to, żeby zmniejszyć liczbę działań arytmetycznych potrzebnych do otrzymania wyniku. Robisz to, podnosząc do potęgi drugiej wyniki poprzedniego potęgowania do drugiej. Jeżeli masz obliczyć a^8, to zamiast wykonywać aaaaaaaa, wykonujesz ((a^2)^2)^2. Przy wykładnikach niebędących potęgami 2, musisz znaleźć sposób na potęgowanie liczb nieparzystych, ponieważ liczba ta w swoim rozkładzie będzie zawierać co najmniej 1 liczbę nieparzystą. Sposób jest prosty:
tworzysz 2 zmienne p (wykładnik parzysty) i n (nieparzysty). Jeżeli podstawa to a, a wykładnik w:
=> do p wpisujesz a, do n 1;
while (w==1)
{
jeżeli w parzyste => podnosisz p do kwadratu, zapisujesz w p i dzielisz wykładnik przez 2;
jeżeli wykładnik nieparzysty => mnożysz na, zapisujesz w n i odejmujesz 1 od w;
}
=> mnożysz p*n
=> masz wynik

przeanalizuj sobie te kroki dla np. 2^{3, 10}10.

Kod RAM, wykonujący szybkie potęgowanie i wypisujący 4 ostatnie cyfry (skracanie w trakcie wykonywania):

          read  1
          load  1
          div   =10000
          mult  =10000
          sub   1
          mult  =-1
          store 1
          load  =1
          store 2
          read  3
          load  3
petla:  jzero licz
          div   =2
          mult  =2
          sub   3
          jzero parzyste
          load  2
          mult  1
          store 2
          div   =10000
          mult  =10000
          sub   2
          mult  =-1
          store 2
parzyste: load  1
          mult  1
          store 1
          div   =10000
          mult  =10000
          sub   1
          mult  =-1
          store 1
          load  3
          div   =2
          store 3
          jump  petla
licz:     load  2
          div   =10000
          mult  =10000
          sub   2
          mult  =-1
          store 2
          write 2
 

Nauczyłem się to liczyć na papierze. Sprawa jest prosta. Dzięki.