ad-20240411.txt

Langzahlarithmetik: Input/Output, 11.04.2024, 13:56:17
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
geg.: lange Zahl zu einer Zweierpotenz-Basis, z.B. 2³²
Problem: Ausgabe als Dezimalzahl

Lösung für kleine Zahlen:
Was ist 0xdeadbeef dezimal?
(= 1101 1110 1010 1101 1011 1110 1110 1111 binär)

binär:
 1 + 2 + 4 + 8 

hexadezimal:
 13 * 16^7 + 14 * 16^6 + ... + 15 * 16^0

--> Dann brauchen wir zusätzlich auch eine Dezimal-Langzahlarithmetik.
    --> Problem gelöst, verbraucht aber zusätzlichen Speicherplatz.

Lösung ohne Umspeichern:
  Zahl % 10 --> dezimale Einerziffer
  Zahl /= 10
  Zahl % 10 --> dezimale Zehnerziffer
  Zahl /= 10
  Zahl % 10 --> dezimale Hunderterziffer
  ...
    --> Problem gelöst, verbraucht aber zusätzliche Rechenzeit.

Verwendung der Basis 2³² hat den Vorteil, daß der Rechner
dafür Assembler-Befehle kennt.

Binäre Exponentiation, 11.04.2024, 14:10:04
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
x^18 möglichst effizient berechnen:

 - 18 binär notieren 10010

 - von rechts nach links durchgehen, x jeweils quadrieren

   Bit 0 (ganz rechts): 0            x
   Bit 1:               1            x^2
   Bit 2:               0            x^4
   Bit 3:               0            x^8
   Bit 4:               1            x^16

 - Dort, wo die Einsen stehen, multiplizieren.
   (Mit 1 anfangen.)

                      1 * x^2 * x^16 = x^18

--> Effizienz der binären Exponentiation von x^n: O(_was_ von n?)
    
    O(log n)

    Die Schleife geht über die Binärziffern von n (= 18).
    Deren Anzahl ist log_2 (n).

 - Zum Vergleich: die Schleife

     int e = 1;
     for (int i = 0; i < 18; i++)
       e *= x;

   berechnet ebenfalls x^18. Effizienz: O(n)

   Die Schleife geht über die Zahl n selbst.

Aufgabe: RSA effizienter [als im Praktikum], 11.04.2024, 14:26:38
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Implementieren Sie RSA wie in Hardwarenahe Programmierung, Praktikumsversuch 1,
aber: Die Effizienz der Benutzung (Schlüsselerzeugung, Verschlüsseln, Entschlüsseln)
soll O((log n)^2) sein. [Im HP-Praktikum genügte O(n).]

Hinweis 1: Verwenden Sie
 - den Datentyp uint64_t,
 - binäre Exponentiation für die Ver- und Entschlüsselung,
 - den erweiterten euklidischen Algorithmus für die Schlüsselerzeugung.

Hinweis 2: Es sollte möglich sein, die Primzahlen so groß zu machen, daß ihr
Produkt den verwendeten Datentyp (uint64_t) _fast_ ausfüllt. Spätestens dann
sollte der Unterschied in der Rechengeschwindigkeit auch ohne Messung deutlich
spürbar sein.

Hinweis 3: Es ist weiterhin wichtig, nach jeder Multiplikation mit x
(einschließlich Quadrieren), modulo zu rechnen.

Vergleichen Sie die Zeitmessungen der alten Variante (O(n)) und der neuen (O(log(n)^2)).

Auch Zwischenergebnisse bereits melden; dann können wir darüber sprechen.
(Auch Fragen dürfen natürlich gestellt werden.;-)