Modulo Problem bei elliptischen Kurven |
28.05.2018, 18:37 | Klingone | Auf diesen Beitrag antworten » | ||
Modulo Problem bei elliptischen Kurven ich befasse mich gerade mit Elliptischen Kurven im Bereich der Kryptografie, also endliche Körper. Vom Prinzip her verstehe ich die Thematik, allerdings verstehe ich die Anwendung des Modulos nicht so ganz. Angenommen folgende elliptische Kurve: über F101 Es sollen die Punkte P+Q=R für P=(2,0) und Q(1,3) auf diese Kurve hinzugefügt werden. Also wende ich diese Formeln an: s = (yP – yQ) / (xP – xQ) mod p xR = s2 – xP – xQ mod p yR = -yP + s*(xP – xR) mod p Setze ich nun bei s folgendes ein: s = (yP – yQ) / (xP – xQ) mod p = (0 – 3) / (2 – 1) mod 17 = -3 Kommt bei mir -3 raus. Laut Lösung soll aber 14 rauskommen, also der Ausdruck (0 – 3) / (2 – 1) mod 17 = 14 Ich verstehe nicht wie man hier auf 14 kommen soll. Ich dachte erst dass die Lösung falsch sei, aber bei einer anderen elliptischen Kurve habe ich das gleiche Problem. Wie muss man das hier rechnen, damit 14 rauskommt? Oder anderes Beispiel der Ausdruck ergibt bei mir 1,608181 Laut Lösung soll aber raus kommen. Das hat was mit dem erweiterten Euklidischen Algorithmus zu tun, ich verstehe aber nicht, warum ich den da anwenden muss. Wieso darf man dass nicht einfach ausrechnen? |
||||
28.05.2018, 18:52 | tatmas | Auf diesen Beitrag antworten » | ||
Hallo, es gilt , denn die Differenz der beiden Werte ist ja gerade 17. Aber wieso rechnest du überhaupt modulo 17? Davor schreibst du was von , also modulo 101. Das sind keine rationalen Zahlen. Du sollst das Inverse von 88 modulo 101 berechnen. Also diejenige Zahl berechnen mit .
Doch darf man. Du machst es halt nur komplett falsch. Da bist du auch nicht allein, ist ein klassischer Anfängerfehler. |
||||
28.05.2018, 19:08 | Klingone | Auf diesen Beitrag antworten » | ||
Mist das mit 101 ist ein Tippfehler, das bezieht sich auf das untere Beispiel. Beim oberen ist F17. Wie muss ich das denn richtig rechnen? |
||||
28.05.2018, 19:22 | tatmas | Auf diesen Beitrag antworten » | ||
Was ist das? Das Inverse modulo n? Das dürfte in deinen Unterlagen stehen, da wo auch das mit dem erweuterten eukl. Algorithmus steht. |
||||
30.05.2018, 02:11 | Klingone | Auf diesen Beitrag antworten » | ||
Mein Problem ist, dass ich nie weiß, wann was äquivalent ist. Hier ein Beispiel: Woher weiß ich, dass äquivalent zu ist? Wie kommt man darauf? Gibt es hierfür eine Formel oder irgendwas, durch ausprobieren finde ich es jedenfalls nicht. |
||||
30.05.2018, 07:20 | tatmas | Auf diesen Beitrag antworten » | ||
15*60^2=54000=504*107 + 72 also oder z.B. (das letzte geht im Kopf; bedenke 2*107=214) Ich rate dir dazu dir die Grundlagen der Modulorechnnng nochmal abzuschauen. |
||||
Anzeige | ||||
|
||||
30.05.2018, 16:17 | Klingone | Auf diesen Beitrag antworten » | ||
Ah danke, die erste Version ist recht angenehm mit dem Taschenrechner lösbar. Ich meine mich dunkel daran zu erinnern, dass man das auch mit dem kleinen Satz von Fermat lösen kann. Aber ich verstehe nicht so recht, wie ich da ansetzen soll. Die Form ist auch ganz anders wie . Weiterhin hat man ja dann auch das Problem mit den Carmichael Zahlen. |
||||
30.05.2018, 17:16 | tatmas | Auf diesen Beitrag antworten » | ||
Der kleine Fermat bringt hier gar nichts. Und mit Carmichaelzahlen hat auch nichts zu tun. |
||||
30.05.2018, 18:49 | Klingone | Auf diesen Beitrag antworten » | ||
Ok, gut zu Wissen . Eine letzte Ungewissheit habe ich noch beim Modulo. Woher weiß ich, wann ich den Modulo direkt (also z.B per Taschenrechner) berechnen kann und wann ich den erweiterten Euklid anwenden muss? Das kann man auch einfach per Taschenrechner berechnen. ABER kann ich nicht direkt berechnen, hier muss ich den erweiterten Euklid anwenden. Ich meine auch auf andere Probleme gestoßen zu sein, bei denen das nicht so einfach ging. Wieso ist das so? Liegt das an der Division? Wenn ja, gilt das immer bei Divisionen? |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|