Demnächst

Riemanns Hypothese und das Internet - IV


Die Entwicklung eines sicheren Verschlüsselungssystems im Zeitalter von Supercomputern ist nicht einfach. Die Wissenschaftler R. Rivest, A. Shamir und L. Adleman haben jedoch ein Kryptosystem mit öffentlichem Schlüssel namens "RSA" entwickelt, das unantastbar ist. Dieses Kryptosystem hängt von der mathematischen Kenntnis der Primzahlen und ihrer Eigenschaften ab.

Wie wir in den vorhergehenden Spalten gesehen haben, war die Arbeit der mathematischen Gemeinschaft bei der Ausarbeitung dieses Systems sehr wichtig. Der deutsche Mathematiker C. F. Gauss formulierte den Kongruenzbegriff, der für die Kodierung und Dekodierung von Schlüsseln im RSA-System von grundlegender Bedeutung ist. Andererseits wird die vorgeschlagene Methode durch einen Satz des Schweizer Mathematikers L. Euler gerechtfertigt, der eine Verallgemeinerung eines Kongruenzergebnisses des französischen Mathematikers P. de Fermat ist, der als „Fermats kleiner Satz“ bekannt ist. Wie bei Fermats letztem Satz gab der französische Mathematiker nur dieses Ergebnis an, und es war an Euler, Fermats kleinen Satz zu demonstrieren und zu verallgemeinern. Dieses Ergebnis besagt, dass:

„Wenn p ist eine Primzahl und m ist eine Ganzzahl, die nicht teilbar ist durch p,

so m p - 1 ≡ 1 (mod p), das heißt, der Rest der Aufteilung von m p - 1 von Cousin p é 1.”

Zum Beispiel ist der Rest der Division 1.024 = 210 = 211 - 1 bis 11 ist 1.

Die Verallgemeinerung dieses Theorems durch Euler gilt für jedes Modul. Daher verwenden wir die erforderliche Version, um das RSA-System zu rechtfertigen, bei dem das Modul aus dem Produkt zweier Primzahlen besteht.

Euler-Fermat-Theorem:

„Wenn p und was sind Primzahlen und m ist eine ganze Zahl, die auch durch nicht teilbar ist p und nicht für was,

so m (p-1)×(was-1) ≡ 1 (mod pwas), das heißt, der Rest der Aufteilung von m (p-1)×(was-1) von pwas é 1.”

Zum Beispiel ist der Rest der Division von 256 = 28 = 22.4 um 15 = 3,5 ist 1.

Wie wir bereits gesehen haben, benötigen Sie zum Codieren eines Texts gemäß dem RSA-System Folgendes:

(1) eine große Anzahl NDas ist das Produkt von zwei verschiedenen Cousins p und wasdh N = pwas.

(2) eine ganze Zahl E, bekannt als Codierschlüssel, der die folgenden Eigenschaften erfüllt: der größte gemeinsame Teiler (MDC) zwischen E und das Produkt (p - 1)•(was -1) ist 1 und der MDC zwischen E und N ist auch 1.

Um einen Text gemäß dem RSA-System zu dekodieren, benötigen Sie:

(3) eine ganze Zahl D, bekannt als Entschlüsselungsschlüssel, der die Bedingung erfüllt:

ED ≡ 1(mod (p -1)•(was - 1)).

Die Beziehung zwischen E und D ist symmetrisch, das heißt, wenn D ist der Entschlüsselungsschlüssel für Edann E ist der Entschlüsselungsschlüssel für D.

In den vorherigen Spalten haben wir die Nachricht codiert ÖFFENTLICHER SCHLÜSSEL mit dem RSA-System, wo wir wählen

N = 2.537 = 43•59, p = 43, was = 59 und Codierschlüssel E = 13.

Zunächst notieren wir uns die Nummer N = 2.537 besteht aus 4 Ziffern und wir teilen den Text in Buchstabenpaare auf:

PU BL IC KE Y

und vervollständige den letzten Block mit dem Buchstaben C bekommen:

<>

PU BL IC KE YC<>

.

Unter Verwendung der Konvertierungstabelle, die natürliche Zahlenalphabetbuchstaben verknüpft, lauten die konvertierten Nachrichtenblöcke wie folgt:

1520 0111 0802 1004 2402.

Auf diese Weise erhält der Empfänger die verschlüsselte Nachricht:

0095 1648 1410 1299 0811.

Um diese Nachricht zu entschlüsseln, benötigen wir den öffentlichen Entschlüsselungsschlüssel. D. In der vorherigen Spalte haben wir erhalten D = 937 als Entschlüsselungsschlüssel.

Wir kodieren jeden Block, Pder Nachricht in einem verschlüsselten Block Q.unter Verwendung der Beziehung

<>

Q.<>

P13 (mod 2.537).

Den Block entschlüsseln Q. dieser verschlüsselten Nachricht müssen wir die Relation verwenden

PQ. 937 (mod 2.537), 0 ≤ P < 2.537.

Wir weisen darauf hin, dass diese Beziehung gültig ist, weil

Q.P13 (mod 2,537) impliziertin

<>

Q. <>

937<>

≡ (P13)937 (mod 2.537) ≡ P12.181 (mod 2.537).

<>

Als 13۰937 = 12.181 = 5۰2.436 + 1 erhalten wir

<>

Q. <>

937<>

≡ (P13)937 (mod 2.537) ≡ P12.181 (mod 2.537) ≡ (P2.436)5 P (mod 2.537).

Nach dem Euler-Fermat-Theorem erhalten wir, da 13 und 59 Primzahlen sind

<>

P<>

(13 - 1) (59 -1) = P 2.436 ≡ 1 (mod 2.537)

und dann

<>

(P2.436)5 PP (mod 2.537).

Daher erhalten wir durch Transitivität

<>

Q.<>

937<>

P (mod 2.537), 0 ≤ P < 2.537

wenn MDC (P, 2.537) = 1.

Beachten Sie, dass die Beziehung

<>

Q.<>

937<>

P (mod 2537), 0 ≤ P <2.537, MDC (P, 2.537) = 1

gilt für alle Blöcke in diesem Beispiel.

Jetzt lass uns nehmen Q. wie Block 0095. Also müssen wir die Kongruenz lösen

95 937P (mod 2.537),

das heißt, bestimmen Sie den Rest der Division von 95937 für 2,537.

Zunächst stellen wir fest, dass es einfacher ist, diese Kongruenz aufzulösen, wenn wir 937 als Summe der Grundkräfte 2 annehmen:

937 = 512 + 256 + 128 + 32 + 8 + 1 = 29 + 28 + 27 + 25 + 23 + 1.

Deshalb haben wir:

952 = 9.025 = 3<>

۰2.537 + 1.414 ≡ 1.414 (mod 2.537);

bald

954 ≡ (1.414)2 (mod 2.537).

Wie (1.414)2 = 1.999.396 = 788<>

372.537 + 240 folgt daraus

954 ≡ 240 (mod 2.537).

In gleicher Weise erhalten wir:

958 ≡ 1.786 (mod 2.537);

9516 ≡ 787 (mod 2.537);

9532 ≡ 341 (mod 2.537);

9564 ≡ 2.116 (mod 2.537);

95128 ≡ 2.188 (mod 2.537);

95256 ≡ 25 (mod 2.537);

95512 ≡ 625 (mod 2.537);

Deshalb:

(95)937 =

(95)512 <>

۰ (95)256<>

۰(95)128<>

۰(95)32<>

۰ (95)8<>

۰(95)

625<>

۰25<>

۰2188<>

۰341<>

۰1786<>

۰95 (mod 2.537).

Wenn wir die Produkte zu zweit nehmen, erhalten wir:

625<>

۰25 = 15.625 = 6<>

۰2.537 + 403 ≡ 403(mod 2.537)

2.188<>

۰341 = 746.108 = 294<>

۰2.537 + 230 ≡ 230(mod 2.537)

1.786<>

۰95 = 169.670 = 66<>

۰2.537 + 2.228 ≡ 2.228(mod 2.537).

Bald

625<>

۰25<>

۰2.188<>

۰341<>

۰1.786<>

95 (mod 2,537)

403<>

۰ 230<>

۰ 2.228 (mod 2.537).

Wie

403<>

۰230 =

92.690 =

36<>

۰2.537 + 1.358 ≡

1.358(mod 2.537)

folgt dem

1.358 - 2.228 = 3.025.624 = 1.192 - 2.537 + 1.520 - 1.520 (mod 2537).

Wir schließen daraus

625<>

۰25<>

۰2.188<>

۰341<>

۰1.786<>

۰95 =

1.358۰ 2.228 =

3.025.624 =

1.192۰2.537 + 1.520 ≡

1.520 (mod 2.537).

Deshalb Q. entspricht Block 1.520.

Forschungen zur Riemann-Hypothese liefern solch wertvolle Informationen über das Primzahlenmuster, dass Fortschritte bei dieser Untersuchung zu erheblichen Fortschritten bei den Factoring-Techniken und folglich zu einem Verstoß gegen die Sicherheit der Datenübertragung über das Internet führen könnten.

Wir betonen, dass die Entwicklung des RSA-Kryptosystems ein weiteres herausragendes Beispiel für den Bedarf an mathematischer Forschung darstellt, da es die Arbeit unzähliger Generationen von Mathematikern darstellt. In der Tat ist daran zu erinnern, dass es Euklid war, der vor mehr als zweitausendunddreihundert Jahren genial demonstrierte, dass es unendlich viele Primzahlen gibt.

Trotz aller Kraft und Stärke, die die Mathematik zeigt, gibt es immer noch eine ziemlich schlechte und widersprüchliche Idee, die sie nur mit einer Sprache im Dienste der Wissenschaft identifiziert…

Mathematik ist eine der größten Schöpfungen des menschlichen Geistes und wir schließen mit den Worten eines der Schöpfer der Differential- und Integralrechnung, des deutschen Mathematikers Leibniz:

"Mathematik ist die Ehre des menschlichen Geistes."

Zurück zu den Spalten

<


Video: Die Riemannsche Vermutung Weihnachtsvorlesung 2016 (Kann 2021).