| Autor |
Beitrag |
    
Mr. Ratlos
| | Veröffentlicht am Samstag, den 13. Januar, 2001 - 13:33: | 
|
Ich habe eine Funktion der Art g(x)=a^x (mod p*q) und diese Funktion muß injektiv sein. Damit das ist, muß a eine primitive Kongruenzwurzel sein. In einem Buch über Verschlüsselungen steht, daß etwa a=3 oder a=11 für p*q=31 ist. Das bringt mir leider auch nichts, da ich für p*q das Prokukt zweier Primzahlen benötige.
Geht es überhaupt, dass g(x) in GF(p*q) Gibt es ein Verfahren zur Berechnung von a und wie funktioniert das?
Ich würde mich über eine Antwort sehr freuen, da ich das alles in einer wichtigen Arbeit benötige... |
Zaph (Zaph)
| | Veröffentlicht am Samstag, den 13. Januar, 2001 - 15:57: |
|
Hallo Mr. Ratlos,
bringst du hier zwei Sachen durcheinander?
g(x) = a^x (mod p)
als Abbildung von {1,...,p-1} auf sich ist injektiv, wenn a ein primitives Element von Z_p ist.
Zum Beispiel p = 7.
a = 2 ist kein primitives Element, da die Potenzen von 2 modulo 7
2, 4, 1, 2, 4 ,1 ... u.s.w.
sind.
a = 3 ist primitiv, die ersten sechs Potenzen modulo 7 lauten 3, 2, 6, 4, 5, 1.
GF(p*q) ergibt ebenfalls keinen Sinn, da es keinen Körper mit p*q Elementen gibt, wenn p und q unterschiedliche Primzahlen sind.
Das einzige Verfahren zur Bestimmung eines primitiven Elements, was mir jetzt einfällt und bei dem nicht p - 1 Potenzen zu berechnen sind, ist:
Bestimme die Primfaktorzerlegung p1 * p2 * ... * pn von p-1 und setze qi = (p - 1)/pi für i = 1,...,n.
Rate a.
Berechne bi = a^qi mod p für i = 1,...,n.
Wenn ein bi = 1, rate ein neues a.
Sonst ist a ein primitives Element.
Wenn in der Verschlüsselung vom Produkt zweier Primzahlen die Rede ist, lautet die Funktion meistens
g(x) = x^e mod (p*q) |
Mr. Ratlos
| | Veröffentlicht am Samstag, den 13. Januar, 2001 - 17:00: |
|
Hallo Zaph,
Du hast mir schon weitergeholfen! Danke!
Gibt es dann überhaupt eine Möglichkeit, eine injektive diskrete Exponentialfunktion mit Falltüre zu finden?! Ich dachte da vor allem an den Chinesischen Restesatz - drum die zwei Primzahlen... |
Zaph (Zaph)
| | Veröffentlicht am Sonntag, den 14. Januar, 2001 - 00:58: |
|
Hallo Mr. Ratlos,
bin jetzt selber etwas ratlos. Kannst du deine Frage bitte präzisieren? [schreibt man das so?? - sieht merkwürdig aus!]
Zaph |
Mr. Ratlos
| | Veröffentlicht am Sonntag, den 14. Januar, 2001 - 15:23: |
|
Wieder mal Hallo!!
Und zwar suche ich eine Funktion zur Verschlüsselung. Diese soll irgendwie auf dem diskreten Logarithmus beruhen.
So dachte ich mir also, ich nehme eine diskrete Exponentialfunktion g(x)=a^x (mod p).
Diese Funktion ist aber leider nur injektiv, wenn a eine primitive Kongruenzwurzel ist. Außerdem hat die Funktion dann eine Inverse, und das ist die diskrete a-Logarithmus-Funktion.
Desweiteren hat die Funktion eine Falltüre, wenn p ein Produkt aus zwei Primzahlen ist. Ist p nicht das Produkt zweier Primzahlen, dann hat g(x) auch keine Falltüre, und man kann den Geheimtext nicht wieder entschlüsseln.
Drum brauche ich eine injektive Funktion g(x)=a^x (mod p) für die gilt:
a ist primitive Kongruenzwurzel und
p ist Produkt zweier Primzahlen.
Tja, und was genau ich jetzt für a und p wählen kann, darauf komme ich eben nicht.
Ich hab' schon fast einen Knoten im Hirn...
Danke für Deine Bemühungen,
Mr. Ratlos |
Zaph (Zaph)
| | Veröffentlicht am Sonntag, den 14. Januar, 2001 - 17:04: |
|
Gehst du davon aus, dass du den diskreten Logarithmus modulo p bzw. modulo q lösen kannst und willst damit den diskr. Log. modulo p*q berechnen, weil p*q zu groß ist, um den diskr. Log modulo p*q direkt zu lösen?
Weiß ja nicht, ob das so eine gute Idee ist! An was für Größenordnungen von p und q denkst du denn?
Wenn p und q Primzahlen sind und ggT(a,p*q) = 1 für a gilt, dann ist
a^kgV(p-1,q-1) = 1 mod p*q.
Mir der Injektivität wird es also wohl nix. |
Carmichael
| | Veröffentlicht am Mittwoch, den 07. Februar, 2001 - 13:36: |
|
Z/p^k* ist auch ne zyklische Gruppe. Da hast
auch deine Primitivwurzel. Vielleicht lässt sich
da der diskrete Logarithmus nicht so leicht bestimmen? |
Zaph (Zaph)
| | Veröffentlicht am Mittwoch, den 07. Februar, 2001 - 19:16: |
|
Ich muss dich enttäuschen.
(Z/16)* = ({1,3,5,7,9,11,13,15}, *) ist nicht zyklisch. |
Carmichael
| | Veröffentlicht am Donnerstag, den 08. Februar, 2001 - 16:36: |
|
p soll natürlich eine ungerade Primzahl sein. |
Zaph (Zaph)
| | Veröffentlicht am Freitag, den 09. Februar, 2001 - 18:17: |
|
Stimmt das? Wieso denn? Stehe gerade etwas auf dem Schlauch ... |
Carmichael
| | Veröffentlicht am Freitag, den 09. Februar, 2001 - 18:42: |
|
Ja stimmt schon.
(Z/p)* hat ne Primitivwurzel, weißt ja.
Und von der ausgehend kannst zeigen, dass ein primitivwurezel a in Z/p existiert für die gilt:
a^(p-1) nicht kongruent 1 (mod p^2);
a^[(p-1)*p] gilt aber natürlich(satz von euler)
damit muss a ne primitivwurzel in (Z/p²)* sein, demm wäre a^[(p-1)*p/d] mit d|p-1 kongruent 1 mod p², wäre es auch kongruent 1 mod p, und damit auch
a^[(p-1)/d], usw. so beweist dich dann mit induktion für (Z/p^n)* durch. |
Zaph (Zaph)
| | Veröffentlicht am Samstag, den 10. Februar, 2001 - 13:03: |
|
Ich glaube dir das schon. Aber deinen Beweis habe ich noch nicht verstanden.
1. Wenn a PW mod p^k, dann ist
a^d PW mod p^k
gdw.
ggT(d,phi(p^k)) = 1,
wobei
phi(p^k) = (p-1) * p^[k-1] = |(Z/p^k)*|.
Wenn ich dich richtig verstanden habe, gibt es jetzt ein d mit
ggT(d,phi(k)) = 1 und a^[d*phi(p^k)] != 1 mod p^[k+1]
Wieso sehe ich das nicht? :-/
2. Im Schritt von k nach k+1 verstehe ich nicht, warum aus
a^[phi(p^[k+1])/d] = 1 mod p^k
bereits
a^[phi(p^k)/d] = 1 mod p^k
folgt. Für k = 1 ist das okay, denn es gilt ja für jedes b, dass
b^p = b mod p. |
Carmichael
| | Veröffentlicht am Samstag, den 10. Februar, 2001 - 14:57: |
|
ne ich denk jetzt wir etwas durcheinander gekommen
also nochmal den Beweis von neuem:
Lemma: Es existiert eine PW in Z/p².
Beweis: Sei a PW in Z/p;
1. Fall
Ist (1) a^(p-1) != 1 (mod p²), dann gilt: Es sei d ord(a) in Z/p². Es gilt nun d teilt (2) p(p-1)=phi(p²) und a^d=1 (mod p). Damit muss (3) p-1|d gelten, denn a ist ja PW in Z/p. Wegen (1),(2) und (3) muss daher d=ord(a)=phi(p²) sein.
2. Fall
Ist a^(p-1) = 1 (mod p²), dann betrachten wir a+p:
(a+p)^(p-1) = a^(p-1) + (p-1)*a^(p-2)*p + ... + p^(p-1) = 1 + (p-1)*a^(p-2)*p = 1 - a^(p-2)*p !=1 (mod p²); [ da a^(p-2) = 1/a !=0 (mod p)]
Für die PW (in Z/p) a+p, gilt also (a+p)^(p-1) != 1 (mod p²) und wir landen wieder bei Fall 1...
So jetzt zur Verallgemeinerung auf p^k.
Ich skizzier nur. Verwende dazu: es gibt ein a, so dass a^phi(p^k) = 1 (mod p^k) und a^phi(p^k) != 1 (mod p^(k+1)), also a^phi(p^k) ist von der Form l*p^k +1 mit ggT(l,p)=1. Für damit eine Induktion über k, mit Hilfe des binomischen Satzes. [ phi(p^(k+1)) / phi(p^k) = p;
(l*p^k + 1)^p = r*p^(k+1) + 1 mit ggT(r,p)=1 ]
[[ Dass a eine PW in p^(k+1) sein muss, beweist du so wie im 1.Fall des Lemmas ]]
Ich hoff ich hab mich nirgends verschrieben |
Zaph (Zaph)
| | Veröffentlicht am Samstag, den 10. Februar, 2001 - 18:18: |
|
Ich dachte, ich hätts gerafft. Als ich dann versuchte, es in eigenen Worten aufzuschreiben, bin ich stecken geblieben:
Zeige: Wenn a eine PW mod p^k, dann ist a oder b := a + p^k ein PW mod p^(k+1).
Es sei d die Ordnung von a und e die Ordnung von b mod p^(k+1).
Zeige: d = |(Z/p^(k+1))*| oder e = |(Z/p^(k+1))*|.
Da a^d = 1 mod p^(k+1), ist a^d = 1 mod p^k. Da a PW mod p^k, folgt
(1) |Z/(p^k)*| = (p-1)*p^(k-1) teilt d
Weiter folgt
(2) d teilt |Z/(p^(k+1))*| = (p-1)*p^k.
da d die Ordnung mod p^(k+1) ist. Da p eine Primzahl ist, folgt aus (1) und (2) entweder
(i) d = (p-1)*p^(k-1)
oder
(ii) d = (p-1)*p^k.
Im Fall (ii) sind wir fertig. Es gelte also (i).
Betrachte nun b. Wegen b^e = a^e = 1 mod p^k folgt wie eben entweder
(iii) e = (p-1)*p^(k-1)
oder
(iv) e = (p-1)*p^k.
Es ist aber modulo pk+1
b(p-1)*p^(k-1)
= (a + pk)(p-1)*p^(k-1)
= a(p-1)*p^(k-1) + (p-1)*pk-1 * a(p-1)*p^(k-1) - 1 * pk + (irgendwas) * p2k nach Binomi
= 1 - p2k-1 * a(p-1)*p^(k-1) - 1 wegen (i) und pk+1 = 0
Das ist jetzt aber nur dann ungleich 1, wenn 2k-1 < k+1, also wenn k < 2.
Oder habe ich deine Verallgemeinerung falsch verstanden? |
Carmichael
| | Veröffentlicht am Samstag, den 10. Februar, 2001 - 19:09: |
|
;) Kenn ich, so hab ich es mir auch mal überlegt, kommst aber nicht weiter. Bei der Verallgemeinerung hast mich also falsch verstanden.
Also, es geht wie folgt:
Lemma 2: Es existiert ein a, so dass
a^phi(p^(k-1)) != 1 (mod p^k). k>=2;
Induktionsanfang: k=2 siehe Lemma
Induktionschritt:
Es ist a^phi(p^(k-1)) = 1 (mod p^(k-1)) [euler]aber != 1 (mod p^k) [I.annahme].
Damit ist a^phi(p^(k-1)) = l*p^(k-1) + 1 mit
ggT(l,p)=1.
Wir betrachten nun a^phi(p^k) mod p^(k+1):
a^phi(p^k) = [a^phi(p^(k-1))]^p =
[l*p^(k-1) + 1]^p = 1 + p*l*p^(k-1) +
+ (p über 2)*l*p^(2k-2) + [irgendwas] * p^(k+1)=
= 1 + l*p^k != 1 (mod p^(k+1))
Letzter Schritt: weil l nicht durch p teilbar
Vorletzter Schritt: weil 2k-2 >= k+1, denn k>=3
also: a^phi(p^(k-1 + 1)) != 1 (mod p^(k + 1));
damit ist die Induktion vollständig.
So, und mit diesem zweiten Lemma, kannst jetzt analog wie im Falle 1! des ersten Lemmas zeigen, dass (Z/p^k)* zyklisch ist. :-) |
Zaph (Zaph)
| | Veröffentlicht am Samstag, den 10. Februar, 2001 - 21:00: |
|
Jawoll, nu hab icks jerafft :-)
Zur Sicherheit nochmal folgende Feststellung, die sich aus deinem Beweis eigentlich ergeben müsste.
Wenn a ein primitives Element modulo p ist, dann ist a ein primitives Element mod p^k für jedes k.
Stimmst du mit mir hierin überein? |
Carmichael
| | Veröffentlicht am Samstag, den 10. Februar, 2001 - 23:48: |
|
Ne so kann man es nicht sagen.
Du kannst sagen, ist a eine Primitivwurzel modulo p, dann gibt es ein b mit a=b (mod p)
(und mit b-a<=p, siehe erstes Lemma 2. Fall), so dass b eine Primitivwurzel modulo p^k.
Außerdem: Ist a Primitivwurzel modulo p^k, dann ist a Primitivwurzel modulo p^l mit l<=k.
und natürlich: Ist a Primitivwurzel modulo p^k, dann ist a Primitivwurzel modulo p^l mit l>=k und k>=2. [hier sieht man auch den gleich folgenden Satz recht schön, da sich die Anzahl der Elemente ver p-fachen....]
Außerdem: Genau phi(phi(p^k)) Elemente erzeugen (Z/p^k)*; aber den Satz kennst ja, gilt ja für zyklische Gruppen.
Und: (Z/m)* ist genau dann zyklisch, wenn m von der Form 2*p^k, wobei p eine ungerade Primzahl ist.
Ist gar nicht mal so schwer zu zeigen, kannst mit kgV(p-1,q-1,...) arbeiten; kannst dich mal dran versuchen. |
Carmichael
| | Veröffentlicht am Sonntag, den 11. Februar, 2001 - 00:05: |
|
Fällt mir nochwas ein!!!!
Mit der Aussage, dass (Z/p^k)* zyklisch ist, kannst auch zeigen, dass (1) jede Carmichael-Zahl quadratfrei sein muss. ( dass (Z/p²)* zyklisch ist würde schon auch reichen, um dies zu zeigen)
Eine Zahl m ist genau dann Carmichael-Zahl, wenn für sie gilt:
Für alle a mit ggT(a,m)=1 gilt:
a^(m-1) = 1 (mod m);
Carmichael-Zahlen bestehen also den Primzahlentest für jede Basis.
mit (1) kannst dann wiederum zeigen, dass für Carmichael-Zahl m auch gilt:
a^m = a (mod m); für alle a
und auch eng damit verbunden:
Z/m -> Z/m mit f(a) = a^d und ggT(d,phi(m))=1 ist genau dann bijektiv, wenn m quadratfrei
Einen Spezialfall davon brauchst dann für das RSA-Verschlüsselungsverfahren; dabei wählt man nämlich m=p*q mit p,q Primzahlen. |
Zaph (Zaph)
| | Veröffentlicht am Sonntag, den 11. Februar, 2001 - 00:29: |
|
Stimmt, hätte schreiben müssen
Wenn a ein primitives Element modulo p^2 ist, dann ist a ein primitives Element modulo p^k für jedes k.
Im Übrigen glaube ich, den diskreten Logarithmus mod p^k einfach berechnen zu können. Doch dazu später mehr. |
Christoph Z (Carmichael)
| | Veröffentlicht am Sonntag, den 11. Februar, 2001 - 02:12: |
|
jo, würd mich schon interessieren..??? |
Zaph (Zaph)
| | Veröffentlicht am Sonntag, den 11. Februar, 2001 - 14:14: |
|
Das Problem, den diskreten Logarithmus in (Z/p^k)* zu berechnen, lässt sich auf die Bestimmung von k diskreten Logarithmen in Gruppen der Ordnung p bzw. p-1 zurückführen.
Gesucht x mit a^x = b mod p^k.
Schritt 1:
Bestimme x(1) mit
a^x(1) = b mod p
und setze
a(2) = a^(p-1) mod p^2,
b(2) = b * a^(-x(1)) mod p^2
Beachte: a(2) hat die Ordnung p in (Z/p^2)*.
Für n = 2,...,k:
Es sei a(n) mit Ordnung p in (Z/p^n)* bestimmt.
Berechne x(n) mit
a(n)^x(n) = b(n) mod p^n
und setze
a(n+1) = a(n)^p mod p^(n+1) (hat die Ordnung p modulo p^(n+1))
b(n+1) = b(n) * a(n)^(-x(n))
Schließlich:
x = x(1) + (p-1)*x(2) + p*(x(3) + ... + x(k))
Ich hoffe, das ist alles so korrekt. Am besten mal ein Beispiel:
Gesucht x mit 2^x = 13 mod 125.
2^x(1) = 3 mod 5 -> x(1) = 3, a(2) = 16, b(2) = 11
16^x(2) = 11 mod 25 -> x(2) = 4, a(3) = 76, b(3) = 51
76^x(3) = 51 -> x(3) = 4
-> x = 3 + 4*4 + 5*4 = 39
Zur Sicherheit eine Probe:
2^39 = 13 mod 125. Stimmt! |
Carmichael (Carmichael)
| | Veröffentlicht am Dienstag, den 20. Februar, 2001 - 16:42: |
|
HI,
also jetzt hab ich mir deine Methode zur Bestimmung des diskreten Logarithmus mal angeschaut, begreif es aber nicht. Kann mir nicht erklären wieso es funktionieren sollte. Zuerst dachte ich setzt man x = x(1) + (p-1)*x(2) + (p-1)(p*x(3) + p²*x(4) + ... + p^(k-2)*x(k)) hauts hin, ut es aber auch nicht. Denn
(a^x mod p^n)*a^-x = 1 (mod p^(n+1)) gilt natürlich nicht immer.
Wie du x definiert hast scheint es aber auch nicht immer hinzuhauen. Ich habs mal ein Bespiel modulo 3^3 genommen.
also:
2^x = 10 (mod 27) gesucht sei x
2^x(1) = 1 mod 3 -> x(1) = 2, a(2) = 4, b(2) = 7
4^x(2) = 7 mod 9 -> x(2) = 2, a(3) = 10, b(3)=19
10^x(3) = 19 mod 27 -> x(3) = 2
-> x = 2 + 2*2 + 3*2 = 12;
[ x' = 2 + 2*2 + 2*3*2 = 18; ]
aber 2^12 != 10 (mod 27);
Hab ich was falsch verstanden oder verrechnet?
Hilf mir mal bitte auf die Sprünge! |
Zaph (Zaph)
| | Veröffentlicht am Mittwoch, den 21. Februar, 2001 - 19:05: |
|
Nein, ich habe Schrott erzählt :-/
Da bei meinem Beispiel zufällig das richtige rauskam, weil ich mich verrechnet habe, ließ ich mich blenden.
Aber so müsste es gehen:
Gesucht x mit a^x = b mod p^k.
Setze x := 0.
Für n = 1 bis k mache das Folgende.
1) c := a^(phi(p^(n-1))) mod p^n
2) d := b * a^(-x) mod p^n
3) Bestimme y < p mit c^y = d mod p^n
4) x := x + phi(p^(n-1)) * y
(Es gilt immer a^x = b mod p^n)
Beispiele (diesmal mit dem Computer bestätigt):
1) a = 2, b = 13, p = 5, k = 6
| n | c | d | y | x | | 1 | 2 | 3 | 3 | 3 | | 2 | 16 | 11 | 4 | 19 | | 3 | 76 | 76 | 1 | 39 | | 4 | 376 | 376 | 1 | 139 | | 5 | 1876 | 1251 | 4 | 2139 | | 6 | 9376 | 3126 | 2 | 7139 |
Also 2^7139 = 13 mod 5^6
2) (Dein Beispiel erweitert) a = 29, b = 37, p = 3, k = 6
| n | c | d | y | x | | 1 | 2 | 1 | 0 | 0 | | 2 | 4 | 1 | 0 | 0 | | 3 | 10 | 10 | 1 | 6 | | 4 | 28 | 55 | 2 | 42 | | 5 | 82 | 1 | 0 | 42 | | 6 | 244 | 244 | 1 | 204 |
Also z. B. 2^6 = 10 mod 27 oder schließlich 2^204 = 37 mod 3^6 |
|
