[leicht bis schwer] Square-and-Multiply

[CDW]

Eingereicht von Shalec:
----

Der leichte Teil:
Programmiere den Square-and-Multiply Binare Exponentiation – Wikipedia Algorithmus in so wenigen Zeichen, wie möglich.

Der "mittel" Teil:
Ergänze nun das Programm, um eine minimale Anzahl an Zeichen, sodass es auf einer gewählten Hardware optimal läuft.
Oder, falls es ein Intelprozessor ist:
Verändere den Code um eine minimale Anzahl an Zeichen, sodass dieser in konstanter Zeit rechnet.

Schwer (optional): Übertrage diesen Code auf eine Array-Arithmetik bei selbst bestimmter oder variabler Länge.

Ergänzung: Wähle nun zufällige eine Primzahl, die in Deinen Datentypen passt und ergänze das Programm um eine Modulo-Arithmetik.

# Square and Multiply Beschreibung
Input: Basis, Exponent (ggf. Primzahl)
Output: Basis ^ Exponent (ggf. modulo Primzahl)
Prozedur: Binare Exponentiation – Wikipedia
----

Spoiler: Loesung zum "Spicken" für den leichten Teil in C

#include <stdint.h>
#include <stdio.h>
void SqM(uint64_t a, uint64_t exponent, uint64_t *C) {
  do {
    if (exponent & 1) *C *= a;
    a *= a;
  } while (exponent >>= 1);
}

int main() {
  uint64_t C = 1, a = 2, ex = 60;
  SqM(a, ex, &C);
  printf("Calculation of %u^%u=%llu", a, ex, C);
}