Hey,
Okay, ich bin nicht so gut in Mathe. Ich versuche mal mein Problem und meinen Ansatz so gut wie es mir möglich ist zu erklären. Fermats Little Theorem besagt folgendes:
Ein Beispiel:
a=3
m=11
Die Gleichung ist für x=4 erfüllt. 4 ist das modular multiplikative inverse.
Ich möchte x selbst wählen und ein random a und ein random m finden die die Gleichung erfülen.
Der Input kann von 1 bis long.MaxValue alles sein, wie kann ich eine effiziente Funktion schreiben die ein a und ein m finden, damit die Gleichung für mein selbst gewähltes x lösbar ist?
Ich habe folgendes geschrieben, es funktioniert für kleine Zahlen, braucht aber mehrere tausend versuche, und bei großen Zahlen dauert es unendlich lange (evtl OutOfRange-Problem (?), bzw keine gültigen a oder m findbar?)
Später möchte ich das ganze auch für long Werte als Input machen aber jetzt bin ich schon zufrieden wenn es für Int32 funktioniert.
Ich bin mir sicher dass man mithilfe von cleveren Mathetricks das Problem effizient lösen kann ?
Okay, ich bin nicht so gut in Mathe. Ich versuche mal mein Problem und meinen Ansatz so gut wie es mir möglich ist zu erklären. Fermats Little Theorem besagt folgendes:
Ein Beispiel:
a=3
m=11
Die Gleichung ist für x=4 erfüllt. 4 ist das modular multiplikative inverse.
Ich möchte x selbst wählen und ein random a und ein random m finden die die Gleichung erfülen.
Der Input kann von 1 bis long.MaxValue alles sein, wie kann ich eine effiziente Funktion schreiben die ein a und ein m finden, damit die Gleichung für mein selbst gewähltes x lösbar ist?
Ich habe folgendes geschrieben, es funktioniert für kleine Zahlen, braucht aber mehrere tausend versuche, und bei großen Zahlen dauert es unendlich lange (evtl OutOfRange-Problem (?), bzw keine gültigen a oder m findbar?)
Später möchte ich das ganze auch für long Werte als Input machen aber jetzt bin ich schon zufrieden wenn es für Int32 funktioniert.
Ich bin mir sicher dass man mithilfe von cleveren Mathetricks das Problem effizient lösen kann ?
C# Developer
Learning C++
Learning C++
Dieser Beitrag wurde bereits 4 mal editiert, zuletzt von „Rikudo“ ()