Zahlentheorie - N faktorisieren |
| 05.06.2010, 13:12 | Fletcher | Auf diesen Beitrag antworten » | ||||||||||
| Zahlentheorie - N faktorisieren ich möchte gerne eine RSA-Zahl faktorisieren und habe dabei folgende Hilfsmittel. Es sei eine Funktion, so das in mehr als 75% der Fälle eine Quadratwurzel von a mod N geliefert wird. Faktorisiere N.
Ich habe mir mit Maple erstmal zu verschiedenen Werten von a einen Wert w(a) bestimmen lassen und dann geprüft, ob es sich dabei um eine Quadratwurzel von a mod N handelt. Mit diesem Wert habe ich dann logischerweise schon mal zwei Lösungen mod N. Allerdings bräuchte ich noch eine weitere Lösung um N faktorisieren zu können. Wie mache ich das am besten? Hier komme ich einfach nicht mehr weiter. Ich hoffe ihr könntet mir behilflich sein. MfG Fletcher |
||||||||||||
| 05.06.2010, 14:00 | Mystic | Auf diesen Beitrag antworten » | ||||||||||
| RE: Zahlentheorie - N faktorisieren Zunächst ist die Aufgabenstellung Unsinn - irgendjemand hat da Mist gebaut - und nach früheren Erfahrungen vermute ich mal den Fehler bei dir: Eine Quadratwurzel aus a mod N für N=pq kann nur existieren, wenn sie sowohl mod p, als auch mod q existiert, und die Wahrscheinlichkeit, dass beides zutrifft ist etwa 25%... Im übrigen ist die Aufgabe kinderleicht: Ist das vorgegebene w(a) nur Wurzel mod p, aber nicht mod q, wie kann man dann p ermitteln? Derive hat für p=639485762397845689237465893468972634895623894756892374660217 weniger als 10 ms gebraucht... Edit: Poste doch bitte mal die Original Aufgabe, die würde mich echt interessieren... |
||||||||||||
| 06.06.2010, 11:09 | Fletcher | Auf diesen Beitrag antworten » | ||||||||||
1) Es sind nicht 75% wie geschrieben, sondern 0,75%. 2) Warum sollte w(a) nur Wurzel mod p sein? Wie kommst du zu der Annahme und wie kommst du auf dein p? |
||||||||||||
| 06.06.2010, 13:03 | Mystic | Auf diesen Beitrag antworten » | ||||||||||
Na toll, also eh nur um den Faktor 100 daneben... 
Ich vermute übigens, dass diese Wahrscheinlichkeit in Wahrheit beträgt, da w(a) für einen quadratischer Rest a mod p offenbar mit der Wahrscheinlichkeit 1/4 auch wirklich Wurzel mod p ist und die entsprechende Wahrscheinlichkeit 1/8 ist für q, aber das ist nur jetzt auf empirischer Basis aufgrund von Simulationsläufen und muss nicht genau stimmen...
Ganz einfach, weil ich mir nicht vorstellen kann, wie anders die Faktorisierung funktionieren kann... Wie kann es anders sein, dass w(a) manchmal Wurzel aus a mod N ist und manchmal nicht? Da gehört nicht viel Fantasie dazu, um auf meine Antwort zu kommen... Wie komme ich auf mein p? Ist es wirklich so schwer, aus der Annahme, dass wir ein a gefunden haben, sodass gilt das p zu ermitteln?... Diese triviale Frage werde ich sicher nicht für dich beantworten, die Antwort must du schon selber finden... Man muss also ein a finden, für welches obige Beziehung (oder die analoge mit vertauschten Rollen von p und q) gilt...Mit wievielen Versuchen muss man also rechnen, um so ein a bei einem entsprechenden RP-Algorithmus zu finden? Die Antwort (mit obigen Wahrscheinlichkeiten) ist etwa und das stimmt auch recht gut mit meinen Erfahrungswerten überein... |
||||||||||||
| 06.06.2010, 16:19 | AD | Auf diesen Beitrag antworten » | ||||||||||
Ich finde, mit diesem "trivial" kannst du den Fragesteller ganz schön einschüchtern. Jedenfalls gebe ich offen zu, dass ich ganz schön lange nachdenken musste, bis ich auf die (im Nachhinein zugegebenermaßen nicht übermäßig schwere) Idee gekommen bin, wie man so ermitteln kann. Das mag allerdings auch an der Tatsache liegen, dass ich nie eine Zahlentheorievorlesung gehört habe, und mir deswegen diese Denkweisen nicht so vertraut sind. 
|
||||||||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
Verschoben!