Veröffentlicht · wird verbessert
Algorithm
ggT und kgV, modulare Arithmetik und Inverse, schnelle Exponentiation, Sieb des Eratosthenes und nCr mod p: Zahlentheorie für Algorithmen.
Die Zahlentheorie untersucht ganze Zahlen, vor allem Teilbarkeit und Reste. In Algorithmen heißt das: ggT und kgV mit dem euklidischen Algorithmus berechnen, sehr große Werte mit modularer Arithmetik handhaben und modulare Inverse mit dem erweiterten euklidischen Algorithmus oder dem kleinen Satz von Fermat bestimmen. Schnelle Exponentiation, das Sieb des Eratosthenes, Primfaktorzerlegung und Binomialkoeffizienten modulo einer Primzahl vervollständigen den Werkzeugkasten.
Diese Werkzeuge begegnen einem in Programmierwettbewerben und Vorstellungsgesprächen ständig als „Gib das Ergebnis modulo 10^9 + 7 aus“. In der Praxis bilden sie die Grundlage für Public-Key-Kryptografie wie RSA und Diffie-Hellman, für Hashfunktionen, Zufallszahlengeneratoren und Prüfziffern. Die meisten laufen in logarithmischer oder nahezu linearer Zeit, sodass Berechnungen, die naiv nie fertig würden, in Millisekunden gelingen.
Verfolgen Sie zuerst die Rechenregeln der modularen Arithmetik und den euklidischen Algorithmus von Hand und implementieren Sie dann schnelle Exponentiation und das Sieb selbst. Danach folgen modulare Inverse und nCr mod p. Wer C++ oder Java schreibt, sollte den Umgang mit Multiplikationsüberläufen und negativen Resten üben. Lernen Sie auch Standardfunktionen wie Pythons pow(a, e, m) und math.gcd kennen.
Wiederholtes Anwenden von ggT(a, b) = ggT(b, a mod b) liefert den ggT in O(log n); die erweiterte Variante gibt zusätzlich die Koeffizienten von ax + by = ggT(a, b) zurück.
Addition, Subtraktion und Multiplikation erhalten Reste, daher reduziert man nach jedem Schritt; Division wird zur Multiplikation mit einer modularen Inversen.
Durch Quadrieren der Basis entlang der Binärstellen des Exponenten wird a^e mod m mit etwa log e statt e Multiplikationen berechnet.
Das Streichen der Vielfachen jeder Primzahl ab i × i findet alle Primzahlen bis n in O(n log log n); eine Tabelle kleinster Primfaktoren zerlegt Zahlen danach schnell.
gcd bestimmt den größten gemeinsamen Teiler mit dem euklidischen Algorithmus, das kgV ergibt sich als a // gcd(a, b) * b. mod_pow ist schnelle Exponentiation: Es durchläuft die Bits des Exponenten, quadriert und multipliziert, und bei einem Primzahlmodul p liefert a^(p-2) die modulare Inverse von a. sieve listet mit dem Sieb des Eratosthenes alle Primzahlen bis 30. Speichern Sie die Datei und führen Sie python number_theory.py aus.
number_theory.py
import math
def gcd(a: int, b: int) -> int:
while b:
a, b = b, a % b
return a
def mod_pow(base: int, exp: int, mod: int) -> int:
result, base = 1 % mod, base % mod
while exp > 0:
if exp & 1:
result = result * base % mod
base = base * base % mod
exp >>= 1
return result
def sieve(n: int) -> list[int]:
is_prime = [False, False] + [True] * (n - 1)
for i in range(2, math.isqrt(n) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = False
return [i for i, p in enumerate(is_prime) if p]
MOD = 10**9 + 7
print(gcd(84, 36), 84 // gcd(84, 36) * 36) # 12 252
print(mod_pow(3, 200, 13)) # 9
print(mod_pow(3, MOD - 2, MOD)) # 333333336, the inverse of 3
print(sieve(30)) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
python number_theory.pySechs Kapitel führen dich von der Installation bis zu den Kernkonzepten von Mathematik und Zahlentheorie.
Stelle Fragen, teile Erfahrungen und tausche Meinungen zu Mathematik und Zahlentheorie aus.
Noch keine Diskussionen. Starte die erste.
0 Kommentare
Anmelden · Melde dich an, um einen Kommentar zu schreiben.
Schreib den ersten Kommentar.