Hallo,
eine Aufgabe der alten Klausur war, das Inverse 7 mod 15 einkreisen…gegeben Zahlen 0-14
Ich bekomme raus: 7*28 = 196 = 13*15 + 1
Müßte das Ergebnis jetzt nicht 28 sein? Kann aber ja garnicht, weil nur Zahlen von 0-14..
Oder ist die 13 das Ergebnis?
Wenn [latex]mk\equiv 1\mod n[/latex] und [latex]m'\equiv m\mod n[/latex],
dann ist auch [latex]m'k\equiv 1\mod n[/latex].
Hilft das weiter?
Kann hier nicht jemand mal ein kleinen trick posten wie man auf das inverse kommt?[18]
Naja, es muss ja gelten ((x * i) mod y) = 1 für ein i aus dem Bereich [1,y)
Man kann ja einfach alle Möglichkeiten durchprobieren, also Brute Force:
#include <iostream>
unsigned inverse(unsigned x, unsigned y)
{
for (unsigned i = 1; i < y; ++i)
if (((i * x) % y) == 1) return i;
return 0;
}
int main()
{
std::cout << "Divident: ";
unsigned x;
std::cin >> x;
std::cout << " Divisor: ";
unsigned y;
std::cin >> y;
unsigned i = inverse(x, y);
if (i) std::cout << "Inverses: " << i << std::endl;
else std::cout << "Es existiert kein Inverses." << std::endl;
}
Divident: 7
Divisor: 15
Inverses: 13
Man kann die Multiplikation und Division auch geschickt durch Addition und Subtraktion ersetzen, sowas fällt einem Menschen ja durchaus leichter. Ein bischen logging-Ausgabe trägt hoffentlich zum Verständnis bei:
#include <iostream>
unsigned inverse(unsigned x, unsigned y)
{
for (unsigned i = 1, s = x; i < y; ++i)
{
std::cout << "i = " << i << "\ts = " << s << std::endl;
if (s == 1) return i;
s += x;
if (s >= y) s -= y;
}
return 0;
}
int main()
{
std::cout << "Divident: ";
unsigned x;
std::cin >> x;
std::cout << " Divisor: ";
unsigned y;
std::cin >> y;
unsigned i = (x < y) ? inverse(x, y) : 0;
if (i) std::cout << "Inverses: " << i << std::endl;
else std::cout << "Es existiert kein Inverses." << std::endl;
}
Divident: 7
Divisor: 15
i = 1 s = 7
i = 2 s = 14
i = 3 s = 6
i = 4 s = 13
i = 5 s = 5
i = 6 s = 12
i = 7 s = 4
i = 8 s = 11
i = 9 s = 3
i = 10 s = 10
i = 11 s = 2
i = 12 s = 9
i = 13 s = 1
Inverses: 13
Ein paar persönliche Beobachtungen:
- Falls x ein Teiler von y ist, kann es kein multiplikatives Inverses geben.
- Sobald für s ein Wert rauskommt, der schonmal da war, kann man die Berechnung abbrechen. Es existiert dann kein multiplikatives Inverses.
- Das Multiplikative Inverse von a mod a+1 ist a:
a * a mod (a+1) = 1 Behauptung
a * a / (a+1) = n Rest 1 andere Schreibweise
a * a = (a+1) * n + 1 andere Schreibweise
a * a = (a+1) * (a-1) + 1 mit n = a-1
a * a = a²-1 + 1 dritte binomische Formel
a * a = a² -1 + 1 = 0
Ich denke auch, dass Brute-Force ausreichen sollte.
Eine andere Frage:
In Brunnis Folien im PKI-Kapitel steht auf Folie 19:
Note:
- RSA ≠ factoring,
- DSA ≠ Discrete Logarithm Problem (DLP),
- DH ≠ DLP
Was ist damit gemeint?
//Edit: Die Antwort ist (glaube ich), dass DH nicht auf dem DLP basiert, sondern, dass der Aufwand zur Lösung von DH ähnlich komplex ist, wie DLP. (von der RSA-Webseite: Maurer [Mau94] has shown that breaking the Diffie-Hellman protocol is equivalent to computing discrete logarithms under certain assumptions.)
Und noch eine Klausur-Frage:
Wahr/Falsch: g ist Primwurzel von p genau dann, wenn g teilerfremd zu p ist.
Bin kein Mathematiker, aber…
- p muss eine Primzahl sein, damit g eine Primwurzel sein kann.
- dann gibt es phi(p)= p-1 Zahlen, die teilerfremd zu p sind.
- d.h., dass die Behauptung nur stimmt, wenn g<=p-1 ist.
Ich weiss nicht, ob das nicht sogar laut Definition so ist. Zumindest wird bei Diffie-Hellman gefordert, dass g<p ist.
Hab ich mir das richtig überlegt?
Wahr/Falsch: g ist Primwurzel von p genau dann, wenn g teilerfremd zu p ist.
Falsch. 2 und 7 sind teilerfremd, aber [latex]2^3 \equiv 1 \text{ mod $7$}[/latex]
Mein Lösungsansatz:
- p muss eine Primzahl sein, damit g eine Primwurzel sein kann.
ja…
Das heißt das P hat nur 1 und sich selbst als möglichen Teiler. G ist also teilerfremd, weil es ja die Wurzel von P ist (also ungleich P) und deshalb auch nicht 1 ist. Sofern man davon ausgeht dass P größer 1 ist.
Wichtig ist laut den Ausführungen von Diffie Hellmann nur, dass G teilerfremd zu P
-1 ist. Was ja mit hinreichend großen Primzahlen für P auch gegeben ist.
Also falsch…
oh da war jemand schneller ;)
