Mathematik-Referenz
Suchen Sie nach ganzen Zahlen, Primzahlen, modularer Arithmetik, zyklischen Gruppen generatoren, quadratischen Resten, diophantischen Gleichungen und RSA mit Formeln und Beispielen.
Sukzessive Potenzen von 3 besuchen jeden nicht-null-Rest, bevor sie zu 1 zurückkehren.
Das Quadrieren der nicht-null-Reste ergibt nur 1, 2 und 4.
55 Begriffe
Ganze Zahlen und Grundlagen
Integer
ℤEine ganze Zahl, die negativ, Null oder positiv sein kann.
Verwenden Sie ganze Zahlen für Zählungen mit Richtung, Indizes, Differenzen und exakte diskrete Berechnungen.
-4, 0 und 27 sind ganze Zahlen.Ganze Zahlen und Grundlagen
Natural number
ℕEine natürliche Zahl; ob Null eingeschlossen ist, hängt von der verwendeten Konvention ab.
Geben Sie die Konvention an, bevor Sie natürliche Zahlen in einem Beweis, einer Spezifikation oder einem Programm verwenden.
Einige Bücher definieren natürliche Zahlen als beginnend bei 1, daher sollten Sie immer die Konvention überprüfen.
This guide uses ℕ = {0, 1, 2, 3, ...}.Ganze Zahlen und Grundlagen
Absolute value
|a|Der nicht-negative Abstand einer ganzen Zahl von Null auf der Zahlengeraden.
Verwenden Sie es, um Magnitude, Distanz, Fehler und symmetrische Grenzen auszudrücken.
|-7| = 7 and |5 - 12| = 7.Ganze Zahlen und Grundlagen
Parity
n mod 2Die Eigenschaft einer ganzen Zahl, gerade oder ungerade zu sein.
Verwenden Sie Parität für Verzweigungen, abwechselnde Muster, Beweise, Prüfsummen und Bit-Logik.
18 mod 2 = 0, so 18 is even.Ganze Zahlen und Grundlagen
Division algorithm
a = bq + rFür ganze Zahlen a und positive b gibt es eindeutige ganze Zahlen q und r mit 0 ≤ r < b.
Verwenden Sie es als Grundlage für Quotienten, Reste, den euklidischen Algorithmus und die modulare Arithmetik.
29 = 6 × 4 + 5, so q = 4 and r = 5.Teilbarkeit
Divisor
d | nEine ganze Zahl d ist ein Teiler von n, wenn n = dk für eine ganze Zahl k gilt.
Verwenden Sie Teiler, um die Faktorstruktur, gemeinsame Faktoren und die exakte Teilbarkeit zu analysieren.
6 | 42 because 42 = 6 × 7.Teilbarkeit
Multiple
n = dkEine Zahl, die durch Multiplikation einer ganzen Zahl mit einer anderen ganzen Zahl erhalten wird.
Verwenden Sie Vielfache für Zeitpläne, gemeinsame Perioden, zyklische Systeme und die Ausrichtung des Nenners.
Vielfache von 5 sind 0, 5, 10, 15 und 20.Teilbarkeit
Divisibility test
n mod d = 0Eine Regel, die bestimmt, ob eine ganze Zahl eine andere Zahl ohne Durchführung der langen Division teilt.
Verwenden Sie es für schnelle Überprüfungen, Kopfrechnen, die Validierung von Eingaben und die Vermittlung der Stellenwertstruktur.
7,452 is divisible by 3 because 7 + 4 + 5 + 2 = 18.Teilbarkeit
Greatest common divisor
gcd(a, b)Die größte positive ganze Zahl, die beide ganzen Zahlen genau teilt.
Verwenden Sie es, um Brüche zu reduzieren, die Koprimität zu testen, Kongruenzen zu lösen und Verhältnisse zu berechnen.
gcd(84, 30) = 6.Teilbarkeit
Least common multiple
lcm(a, b)Die kleinste positive ganze Zahl, die ein Vielfaches von beiden nicht-Null-ganzen Zahlen ist.
Verwenden Sie es, um Zyklen zu synchronisieren, Brüche zu kombinieren und sich wiederholende Zeitpläne zu berechnen.
lcm(12, 18) = 36.Teilbarkeit
GCD-LCM identity
gcd(a,b)lcm(a,b)=|ab|Eine Beziehung, die den größten gemeinsamen Teiler und das kleinste gemeinsame Vielfache zweier nicht-null-Integer verbindet.
Verwenden Sie es, um eine Größe effizient zu berechnen, wenn die andere bereits bekannt ist.
gcd(12,18)=6, so lcm(12,18)=|12×18|/6=36.Teilbarkeit
Euclidean algorithm
gcd(a,b)=gcd(b,a mod b)Ein wiederholender Restalgorithmus zum Finden des größten gemeinsamen Teilers.
Verwenden Sie es für die schnelle Berechnung der GCD, auch wenn die Eingabezahlen groß sind.
gcd(252,105) = gcd(105,42) = gcd(42,21) = 21.Teilbarkeit
Extended Euclidean algorithm
ax + by = gcd(a,b)Eine Erweiterung des euklidischen Algorithmus, die auch die Bézout-Koeffizienten x und y findet.
Verwenden Sie es, um modulare Inverse zu berechnen und lineare Diophantische Gleichungen zu lösen.
35×(-1) + 12×3 = 1, also ist -1 ein Koeffizient für 35.Teilbarkeit
Coprime integers
gcd(a,b)=1Zwei ganze Zahlen sind teilerfremd, wenn ihr größter gemeinsamer Teiler 1 ist.
Verwenden Sie die Teilerfreiheit, um die Invertierbarkeit modulo n zu bestimmen und den Eulerschen Satz anzuwenden.
8 und 15 sind teilerfremd, obwohl keine der Zahlen eine Primzahl ist.Primzahlen und Faktorisierung
Prime number
pEine ganze Zahl größer als 1, deren einzige positive Teiler 1 und sich selbst sind.
Verwenden Sie Primzahlen als grundlegende Bausteine der Integer-Faktorisierung und der Public-Key-Kryptographie.
2, 3, 5, 7 und 11 sind Primzahlen.Primzahlen und Faktorisierung
Composite number
n = abEine ganze Zahl größer als 1, die einen positiven Teiler außer 1 und sich selbst hat.
Verwenden Sie es, um faktorisierbare Zahlen von Primzahlen zu unterscheiden.
21 is composite because 21 = 3 × 7.Primzahlen und Faktorisierung
Prime factorization
n=∏pᵢ^aᵢEine ganze Zahl als Produkt von Potenzen von Primzahlen schreiben.
Verwenden Sie es, um Teiler, GCDs, LCMs und arithmetische Funktionen zu berechnen.
360 = 2^3 × 3^2 × 5.Primzahlen und Faktorisierung
Fundamental theorem of arithmetic
n=∏pᵢ^aᵢJede ganze Zahl größer als 1 hat eine Primfaktorzerlegung, die bis auf die Faktorreihenfolge eindeutig ist.
Verwenden Sie es, um Algorithmen und Beweise zu rechtfertigen, die auf Primzahlpotenzen basieren.
72 = 2^3 × 3^2 ist die eindeutige Primfaktorzerlegung von 72.Primzahlen und Faktorisierung
Sieve of Eratosthenes
Ein Algorithmus, der Primzahlen bis zu einem Grenzwert auflistet, indem wiederholt Vielfache jeder gefundenen Primzahl markiert werden.
Verwenden Sie es, wenn viele Primzahlabfragen die gleiche moderate obere Grenze gemeinsam haben.
Um Primzahlen bis 30 zu finden, markieren Sie die Vielfachen von 2, 3 und 5.Primzahlen und Faktorisierung
Primality test
Ein Algorithmus, der entscheidet, ob eine gegebene ganze Zahl eine Primzahl ist.
Verwenden Sie die Teilerprobe für kleine Eingaben und probabilistische Tests wie Miller-Rabin für große Eingaben.
Ein Wahrscheinlichkeitsprimzahltest kann mehrere Runden oder ein deterministisches Basissatz für den beabsichtigten Integerbereich erfordern.
Die Teilungsprüfung benötigt nur Kandidatenteiler bis √n.Modulare Arithmetik
Congruence
a ≡ b (mod n)Zwei ganze Zahlen sind kongruent modulo n, wenn n ihre Differenz teilt.
Verwenden Sie es, um ganze Zahlen durch äquivalente Reste in zyklischen Berechnungen zu ersetzen.
29 ≡ 5 (mod 12), weil 12 29 - 5 teilt.Modulare Arithmetik
Residue class
[a]ₙDie Menge aller ganzen Zahlen, die modulo n kongruent zu einer festen ganzen Zahl sind.
Verwenden Sie es, um modulare Werte als Äquivalenzklassen und nicht als isolierte Zahlen zu betrachten.
[2]₅ = {..., -8, -3, 2, 7, 12, ...}.Modulare Arithmetik
Modulo operation
a mod nEine Operation, die einen Restwert nach der Division durch n zurückgibt.
Verwenden Sie es für das Umschließen von Indizes, Uhren, Hash-Tabellen und periodische Zustände.
(23 + 5) mod 24 = 4.Modulare Arithmetik
Modular arithmetic
ℤ/nℤArithmetik, die auf Restklassen mit Ergebnissen durchgeführt wird, die modulo n reduziert werden.
Verwenden Sie es in der Kryptographie, der Codierungstheorie, zyklischen Puffern und Kalenderberechnungen.
(17 × 19) mod 12 = 11.Modulare Arithmetik
Modular inverse
a⁻¹ mod nEin Wert x, der ax ≡ 1 (mod n) erfüllt; er existiert genau dann, wenn gcd(a,n)=1.
Verwenden Sie es, um in der modularen Arithmetik zu teilen, Kongruenzen zu lösen und kryptografische Algorithmen zu implementieren.
Versuchen Sie keine modulare Division, bevor Sie überprüft haben, dass der Teiler teilerfremd zum Modulus ist.
3⁻¹ mod 7 = 5 because 3 × 5 ≡ 1 (mod 7).Modulare Arithmetik
Modular exponentiation
a^k mod nBerechnung einer Potenz modulo n, ohne zuerst die potenziell riesige vollständige Potenz zu konstruieren.
Verwenden Sie wiederholtes Quadrieren in der Kryptographie, Primzahltests und Problemen mit großen Exponenten.
3^13 mod 7 = 3 using repeated squaring.Modulare Arithmetik
Linear congruence
ax ≡ b (mod n)Eine Kongruenz, die nach ganzen Zahlen x fragt, die eine lineare modulare Gleichung erfüllen.
Verwenden Sie GCD-Bedingungen und modulare Inverse, um Lösungen zu bestimmen und zu berechnen.
3x ≡ 4 (mod 7) ergibt x ≡ 6 (mod 7).Modulare Arithmetik
Chinese remainder theorem
x ≡ aᵢ (mod nᵢ)Ein Satz, der kompatible Kongruenzen kombiniert und eine eindeutige Lösung modulo dem Produkt liefert, wenn die Moduli paarweise teilerfremd sind.
Verwenden Sie es, um unabhängige zyklische Beschränkungen zu kombinieren und die Berechnung großer Zahlen zu beschleunigen.
x ≡ 2 (mod 3), x ≡ 3 (mod 5) ergibt x ≡ 8 (mod 15).Modulare Arithmetik
Euler's totient function
φ(n)Die Anzahl der ganzen Zahlen von 1 bis n, die teilerfremd zu n sind.
Verwenden Sie es im Satz von Euler, bei RSA-Schlüsselberechnungen und bei reduzierten Restklassen.
φ(12) = 4, weil 1, 5, 7 und 11 teilerfremd zu 12 sind.Modulare Arithmetik
Euler's theorem
a^φ(n) ≡ 1 (mod n)Wenn a und n teilerfremd sind, ergibt a hoch φ(n) 1 modulo n.
Verwenden Sie es, um Exponenten zu reduzieren, modulare Identitäten zu beweisen und RSA zu erklären.
gcd(3,10)=1 and φ(10)=4, so 3^4 ≡ 1 (mod 10).Modulare Arithmetik
Fermat's little theorem
a^(p-1) ≡ 1 (mod p)Für eine Primzahl p und eine Zahl a, die nicht durch p teilbar ist, ist a hoch p-1 kongruent zu 1 modulo p.
Verwenden Sie es für modulare Inverse unter einem Primmodul und für die Primzahlprüfung.
Ein Fermat-Test beweist nicht, dass eine Zahl eine Primzahl ist, da Pseudoprimzahlen existieren.
2^6 ≡ 1 (mod 7).Zyklische Gruppen und Generatoren
Group
(G, *)Eine Menge mit einer assoziativen Operation, einem Identitätselement und einem Inversen für jedes Element.
Verwenden Sie Gruppen, um arithmetische Strukturen zu beschreiben, bei denen Operationen kombiniert und umgekehrt werden können.
Die ganzen Zahlen bilden eine Gruppe unter Addition mit dem neutralen Element 0 und dem Inversen -a für a.Zyklische Gruppen und Generatoren
Abelian group
a*b=b*aEine Gruppe, deren Operation kommutativ ist.
Verwenden Sie es für modulare Addition, Vektoraddition und viele arithmetische Gruppen, bei denen die Reihenfolge der Operationen keine Rolle spielt.
(ℤ/nℤ, +) ist eine abelsche Gruppe.Zyklische Gruppen und Generatoren
Additive group modulo n
(ℤ/nℤ, +)Die Restklassen modulo n mit Addition, die modulo n durchgeführt wird.
Verwenden Sie es, um zyklische Zähler, periodische Zustände und Kongruenzklassen unter Addition zu modellieren.
In ℤ/5ℤ, 3+4=2.Zyklische Gruppen und Generatoren
Multiplicative group of units
(ℤ/nℤ)×Die Restklassen, die relativ zu n teilerfremd sind, mit Multiplikation modulo n.
Verwenden Sie es, um modulare Inverse, primitive Wurzeln, den Eulerschen Satz und die Kryptographie mit öffentlichem Schlüssel zu untersuchen.
(ℤ/8ℤ)×={1,3,5,7}.Zyklische Gruppen und Generatoren
Cyclic group
G=⟨g⟩Eine Gruppe, deren jedes Element eine Potenz oder eine wiederholte Summe eines Elements ist.
Verwenden Sie es, um eine Gruppenoperation auf arithmetische Operationen auf Exponenten oder Integer-Vielfachen zu reduzieren.
Die additive Gruppe ℤ/6ℤ wird durch 1 und 5 erzeugt.Zyklische Gruppen und Generatoren
Generator
⟨g⟩=GEin Element, dessen wiederholte Gruppenoperation jedes Element einer zyklischen Gruppe erzeugt.
Verwenden Sie es, um zyklische Gruppen aufzulisten und exponentenbasierte kryptografische Operationen zu definieren.
Geben Sie immer die Gruppe und die Operation an, da ein Element eine Struktur erzeugen kann, aber nicht eine andere.
Potenzen von 3 modulo 7 ergeben 3, 2, 6, 4, 5, 1, also erzeugt 3 (ℤ/7ℤ)×.Zyklische Gruppen und Generatoren
Order of an element
ord(g)Der kleinste positive Integer k, für den g^k das neutrale Element ist.
Verwenden Sie es, um zu testen, ob ein Element ein Generator ist, und um die Zykluslänge zu bestimmen.
Modulo 7 gilt: ord(2)=3, weil 2^3≡1 und kein kleinerer positiver Exponent funktioniert.Zyklische Gruppen und Generatoren
Primitive root
ordₙ(g)=φ(n)Ein Generator der multiplikativen Gruppe der Einheiten modulo n.
Verwenden Sie primitive Wurzeln, um nicht-Null-Reste als Potenzen darzustellen und diskrete Logarithmen zu formulieren.
3 ist eine primitive Wurzel modulo 7, weil ihre Ordnung φ(7)=6 ist.Zyklische Gruppen und Generatoren
Primitive root existence
Primitive Wurzeln modulo n existieren genau für n=1, 2, 4, p^k oder 2p^k, wobei p eine ungerade Primzahl ist.
Verwenden Sie das Kriterium, bevor Sie nach einer primitiven Wurzel modulo einer zusammengesetzten Zahl suchen.
Es gibt keine primitive Wurzel modulo 8, da 8 keine der erforderlichen Formen aufweist.Zyklische Gruppen und Generatoren
Discrete logarithm
g^x=hGegeben ein Generator g und ein Gruppenelement h, fragt der diskrete Logarithmus nach einem Exponenten x, der die Gleichung g^x=h erfüllt.
Verwenden Sie es, um die Sicherheitsannahmen von Diffie-Hellman, ElGamal und elliptischen Kurven zu verstehen.
Der diskrete Logarithmus kann in kleinen oder schlecht gewählten Gruppen einfach zu berechnen sein und nur unter geeigneten Parametern schwer.
Modulo 7 mit Generator 3 gilt: log₃(5)=5, weil 3^5≡5.Zyklische Gruppen und Generatoren
Carmichael function
λ(n)Der kleinste positive Exponent m, so dass a^m ≡ 1 modulo n für jedes a, das relativ zu n teilerfremd ist.
Verwenden Sie es, um einen engeren universellen Exponenten als φ(n) für modulare Potenzen und RSA-Analysen zu erhalten.
λ(8)=2, weil jedes ungerade a die Bedingung a²≡1 (mod 8) erfüllt.Quadratische Reste
Quadratic residue
x²≡a (mod n)Ein Rest a, für den die Kongruenz x²≡a modulo n eine Lösung hat.
Verwenden Sie es, um modulare Quadratwurzeln, Primzahltests und quadratische Residuen-Kryptographie zu analysieren.
2 ist ein quadratischer Rest modulo 7, weil 3²≡2.Quadratische Reste
Quadratic nonresidue
Ein von Null verschiedener Rest, für den x²≡a modulo n keine Lösung hat.
Verwenden Sie es, um Residuen zu klassifizieren und Tests oder kryptografische Parameter mit bekanntem quadratischen Charakter zu erstellen.
3 ist ein quadratischer Nichtrest modulo 7.Quadratische Reste
Modular square root
x=√a mod nEine Lösung x für x²≡a modulo n.
Verwenden Sie es in der Punktdekodierung, nummerntheoretischen Algorithmen und residu-basierten Kryptographie.
Die Quadratwurzeln von 2 modulo 7 sind 3 und 4.Quadratische Reste
Legendre symbol
(a/p)Für eine ungerade Primzahl p ist ein Wert 0, 1 oder -1, der die Teilbarkeit durch p oder den Status als quadratischer Rest modulo p angibt.
Verwenden Sie es, um den quadratischen Charakter zu testen und das Eulersche Kriterium und die quadratische Rekiprokität kompakt auszudrücken.
(2/7)=1, weil 2 ein quadratischer Rest modulo 7 ist.Quadratische Reste
Jacobi symbol
(a/n)Eine multiplikative Erweiterung des Legendre-Symbols auf positive, ungerade, zusammengesetzte Nenner.
Verwenden Sie es für effiziente Charakterberechnungen und Algorithmen, die nicht zuerst die Faktorisierung von n erfordern.
Ein Jacobi-Symbol von 1 garantiert nicht, dass a ein quadratischer Rest modulo der zusammengesetzten Zahl n ist.
(5/21)=(5/3)(5/7)=1.Quadratische Reste
Euler's criterion
a^((p-1)/2)≡(a/p) (mod p)Ein Kriterium, das den Status eines quadratischen Rests modulo einer ungeraden Primzahl unter Verwendung der modularen Potenzierung bestimmt.
Verwenden Sie es, um das Legendre-Symbol zu berechnen, ohne jede Quadratzahl aufzulisten.
Für p=7 gilt 3^3≡-1 (mod 7), also ist 3 ein quadratischer Nichtrest.Quadratische Reste
Quadratic reciprocity
(p/q)(q/p)=(-1)^((p-1)(q-1)/4)Ein Satz, der beschreibt, ob eine ungerade Primzahl ein quadratischer Rest modulo einer anderen ist.
Verwenden Sie es, um große Legendre-Symbol-Berechnungen auf kleinere zu reduzieren.
Da 3 und 11 beide 3 modulo 4 sind, gilt (3/11)=-(11/3).Quadratische Reste
Supplementary laws
(-1/p), (2/p)Formeln, die den quadratischen Charakter von -1 und 2 modulo einer ungeraden Primzahl bestimmen.
Verwenden Sie sie zusammen mit der quadratischen Reziprozität, um Legendre-Symbol-Berechnungen zu vervollständigen.
(2/p)=1, wenn p≡1 oder 7 (mod 8), und -1, wenn p≡3 oder 5 (mod 8).Quadratische Reste
Tonelli-Shanks algorithm
Ein Algorithmus zum Finden einer modularen Quadratwurzel eines quadratischen Rests modulo einer ungeraden Primzahl.
Verwenden Sie es, wenn der Modul eine Primzahl ist und die einfache Abkürzung p≡3 modulo 4 nicht anwendbar ist.
Für p=13 findet der Tonelli-Shanks-Algorithmus x=6 oder 7 für x²≡10 (mod 13).Quadratische Reste
Square roots modulo a composite
Quadratwurzeln werden modulo Primpotenzen gefunden und mit dem chinesischen Restsatz kombiniert.
Verwenden Sie es, um Rabin-ähnliche Systeme und Kongruenzen mit zusammengesetzten Moduli zu analysieren.
Für ein Produkt von verschiedenen ungeraden Primzahlen kann ein Rest mehrere Quadratwurzeln haben, sodass die Auswahl der beabsichtigten Wurzel zusätzliche Informationen erfordert.
Lösen Sie x²≡1 modulo 3 und 5, und kombinieren Sie dann die Vorzeichenauswahl modulo 15.Ganze Zahlen Gleichungen
Diophantine equation
Eine Gleichung, für die nur ganzzahlige Lösungen gesucht werden.
Verwenden Sie Teilbarkeit, GCD, Kongruenzen und Grenzen, um festzustellen, ob ganzzahlige Lösungen existieren.
3x + 5y = 17 has the integer solution x = 4, y = 1.Ganze Zahlen Gleichungen
Linear Diophantine equation
ax + by = cEine lineare Gleichung, deren Unbekannte ganze Zahlen sein müssen; Lösungen existieren genau dann, wenn gcd(a,b) c teilt.
Verwenden Sie es für die exakte Allokation, Münzprobleme, Zeitpläne und Gitterbeschränkungen.
6x + 9y = 30 ist lösbar, weil gcd(6,9)=3 30 teilt.Anwendungen
RSA arithmetic
c ≡ m^e (mod n)Öffentliche Schlüsselarithmetik, die auf modularer Exponentiation und der Schwierigkeit der Faktorisierung eines Produkts großer Primzahlen basiert.
Verwenden Sie es, um zu verstehen, wie die Zahlentheorie die Verschlüsselung und digitale Signaturen unterstützt.
Testwerte dienen nur zum Lernen; echte RSA erfordert standardisierte Padding, sichere Schlüsselgrößen und geprüfte Bibliotheken.
Mit den Beispielwerten n=55, e=3 und m=7, gilt c=7^3 mod 55=13.