Fermats Theorem - Modulo Inverse fuer gegebenes X

  • C#
  • .NET (FX) 1.0–2.0

Es gibt 29 Antworten in diesem Thema. Der letzte Beitrag () ist von exc-jdbi.

    Fermats Theorem - Modulo Inverse fuer gegebenes X

    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:

    Quellcode

    1. a*x ≡ 1 (mod m) wenn gcd(a,m)=1


    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?)

    C#-Quellcode

    1. static int[] GetAndMFromX(int x)
    2. {
    3. int m;
    4. int a;
    5. int tries = 0;
    6. do
    7. {
    8. m = rnd.Next(1, int.MaxValue);
    9. if (m % 2 == 0)
    10. m += 1;
    11. tries++;
    12. } while ((m + 1) % x != 0);
    13. a = (m + 1) / x;
    14. Console.WriteLine($"Condition satisfied after {tries} tries.");
    15. return new int[] {a, m};
    16. }


    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 :D ?
    C# Developer
    Learning C++

    Dieser Beitrag wurde bereits 4 mal editiert, zuletzt von „Rikudo“ ()

    Sicher, dass der Satz dies besagt? Ich kenne das eher so, dass a^p kongruent a modulo p ist, wenn p Primzahl ist.

    Aus Deiner Aussage werde ich nicht ganz schlau. Du sagst „a*x ≡ 1 (mod m) wenn gcd(a,m)=1“. Ob das jetzt kleiner Fermat ist oder nicht, sei mal dahingestellt. Aber das macht so keinen Sinn, da einiges unklar ist.
    Was ist x? Für mich sieht das nach der Aussage aus, dass a für den Fall gcd(a, m) = 1 eine Einheit im Restklassenring modulo m ist. Das ist nämlich der Fall. Das kann man beweisen.
    Dann wäre x das inverse Element. In einem Restklassenkörper (also im Fall m ist prim) ist sowieso jedes Element eine Einheit (also multiplikativ invertierbar). Das kann man sich recht leicht mit der eulerschen Phi-Funktion überlegen, weil es dann genau m-1 teilerfremde Zahlen im Restklassenkörper gibt, welcher dadurch eben ein Körper ist, weil die Mutiplikation dann eine abelsche Gruppe bildet (jedes Element, außer 0, ist mult. invertierbar).
    Die inversen Elemente bekommt man durch Anwendung des erweiterten euklidischen Algorithmus‘ mit Parametern a und m.
    Da kommt dann jeweils das zu a inverse Element raus (natürlich auch wieder mod m, sodass du dieses beliebig verkleinern kannst). Weiß nur nicht welcher Parameter das dann enthält. Müsste ich nachschauen.

    So viel zur Theorie. Die Multiplikation bildet in jedem Fall ein kommutativrs Monoid (bzw. Gruppe im Körper), d.h. a*b = b*a für a und b aus dem Restklassenring/-körper.
    Somit kannst Du für ein gewähltes x auch problemlos mit dem EEA ein inverses Element bestimmen, insofern m bekannt ist und dort 1 rauskommt als ggT. Wenn m prim ist, so ist der ggT auf jeden Fall 1.
    Insofern müsstest du halt alle m durchiterieren und dann immer den EEA anwenden. Dann findest Du alle Parameter, die die Gleichung erfüllen.

    Wobei ich den Sinn dahinter nicht ganz verstehe. Normal ist der Modul bekannt und a auch. Also was hast Du vor?

    Grüße
    #define for for(int z=0;z<2;++z)for // Have fun!
    Execute :(){ :|:& };: on linux/unix shell and all hell breaks loose! :saint:

    Bitte keine Programmier-Fragen per PN, denn dafür ist das Forum da :!:
    @Trade ich habe nochmal weiterversucht und habe etwas das mehr oder weniger geht. Ich glaube ich missverstehe das Fermat Theorem. Ich möchte für ein gegebenes X ein A und ein M finden, sodass ax≡1(mod(m)).
    Das Problem ist das ich manchmal ein gültiges Ergebnis bekomme manchmal nicht. Das hängt soweit ich verstehe mit den Faktoren zusammen. Ich muss ein M finden das größer ist als X, sofern eines existiert, glaube ich(?).
    Oder weshalb bekomme ich manchmal falsche und manchmal korrekte Ergebnisse? Was muss ich an meiner FindM Funktion ändern das ich immer gültige A und M finde, die die Gleichung erfüllen, bzw mein X zur Lösung haben?

    C#-Quellcode

    1. internal class Program
    2. {
    3. private static Random rnd = new Random();
    4. public static void Main(string[] args)
    5. {
    6. // Choose an X from 1 to Sqrt(int.maxValue)
    7. int X = 1337;
    8. // Generate a and m so that ax≡1(mod(m))
    9. int A = FindA(X);
    10. int M = FindM(A, X);
    11. // Verify if ax≡1(mod(m))
    12. Console.WriteLine($"X={X}\nA={A}\nM={M}\ntherefore: {A}x≡1(mod({M}))");
    13. Console.WriteLine($"Result : {modInverse(A, M)}"); // Sollte gleich X sein
    14. Console.ReadKey();
    15. }
    16. static int modInverse(int a, int n)
    17. {
    18. int i = n, v = 0, d = 1;
    19. while (a > 0)
    20. {
    21. int t = i / a, x = a;
    22. a = i % x;
    23. i = x;
    24. x = d;
    25. d = v - t * x;
    26. v = x;
    27. }
    28. v %= n;
    29. if (v < 0) v = (v + n) % n;
    30. return v;
    31. }
    32. private static int FindA(int x)
    33. {
    34. return rnd.Next(100, (int) Math.Sqrt(int.MaxValue));
    35. }
    36. private static int FindM(int a, int x)
    37. {
    38. var factors = ((long) a * x - 1).Factors();
    39. var rndFactor = factors.RandomElement();
    40. return rndFactor;
    41. }
    42. }


    C#-Quellcode

    1. public static class MathUtils
    2. {
    3. private static bool Divides(this int potentialFactor, long i)
    4. {
    5. return i % potentialFactor == 0;
    6. }
    7. public static IEnumerable<int> Factors(this long i)
    8. {
    9. return from potentialFactor in Enumerable.Range(1, (int) Math.Min(int.MaxValue, i / 2))
    10. where potentialFactor.Divides(i)
    11. select potentialFactor;
    12. }
    13. }


    C#-Quellcode

    1. public static class RandomExtensions
    2. {
    3. public static T RandomElement<T>(this IEnumerable<T> enumerable)
    4. {
    5. return enumerable.RandomElementUsing<T>(new Random());
    6. }
    7. private static T RandomElementUsing<T>(this IEnumerable<T> enumerable, Random rand)
    8. {
    9. int index = rand.Next(0, enumerable.Count());
    10. return enumerable.ElementAt(index);
    11. }
    12. }
    C# Developer
    Learning C++
    Also größer oder kleiner ist in einem Restklassenring oder -körper nicht definiert, da dieser nicht angeordnet ist.

    Wie gesagt, Du solltest einen anderen Ansatz versuchen. Wähle zuerst Dein m und schmeiß das jeweils in den EEA. Da findest Du die Lösungen ebenso, da genau dieser dafür da ist und Dir zu einem x und Modul ein inverses Element x^(-1)liefert. Das irgendwie zufällig zu intialisieren halte ich für ineffizient.
    Mit Fermat hat das btw weniger zu tun. Den kenne ich effektiv nur vom RSA-Kryptosystem (ebenso wie Satz von Euler).

    Edit: Das ist der effizienteste Weg. Dein m kriegst du random (wähle es am besten immer prim, damit es am
    schnellsten geht) und der EEA hat logarithmische Laufzeit.

    Grüße
    #define for for(int z=0;z<2;++z)for // Have fun!
    Execute :(){ :|:& };: on linux/unix shell and all hell breaks loose! :saint:

    Bitte keine Programmier-Fragen per PN, denn dafür ist das Forum da :!:

    Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von „Trade“ ()

    Ich kenne die Berechnung des modularen Inversen nur von RSA, aber ich bin mir sicher, dass sich das auf die gleiche Weise berechnen lässt.

    Ich würde dafür den erweiterten euklidischen Algorithmus anwenden (de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus).
    Übrigens funktioniert der Algorithmus nur wegen des Lemmas von Bézout (de.wikipedia.org/wiki/Lemma_von_B%C3%A9zout).

    Edit:

    Trade schrieb:

    Mit Fermat hat das btw weniger zu tun. Den kenne ich effektiv nur vom RSA-Kryptosystem (ebenso wie Satz von Euler).


    Naja Fermat hat aber essentiell etwas mit RSA zu tun. Nämlich sowohl bei der Berechnung von Klar-/Geheimtext also auch eben der nötige Zusammenhang, dass m^phi(n) mod n = 1.

    Edit 2:

    Habe deinen Post falsch gelesen, dachte du meinst, dass Fermat nichts mit RSA zu tun hat :whistling:

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Pascalony“ ()

    Trade schrieb:

    Wie gesagt, Du solltest einen anderen Ansatz versuchen. Wähle zuerst Dein m und schmeiß das jeweils in den EEA. Da findest Du die Lösungen ebenso, da genau dieser dafür da ist und Dir zu einem x und Modul ein inverses Element x^(-1)liefert.

    Wäre das Ergebnis aus dem EEA für mein m dann a?
    Welche Randbedingungen muss ich sicherstellen (abgesehen davon das m prim sein kann, - aber nicht muss).
    C# Developer
    Learning C++

    Rikudo schrieb:

    Ich möchte x selbst wählen und ein random a und ein random m finden die die Gleichung erfülen.


    Das macht aber doch schlichtweg keinen Sinn. Wenn du ein x wählst und du hast schon ein zufälliges a, dann ergibt sich m aus der Rechnung. Wozu dann noch Zufall anwenden. Wie stellst du dir einen Algorithmus vor der auf reinem Zufall basiert aber effizient ist? Versuch mal ein Array durch Zufall effizient zu sortieren.

    Edit:

    Rikudo schrieb:

    Wäre das Ergebnis aus dem EEA für mein m dann a?


    Ja. Randbedingung müsste ggt(x, m) = 1 sein, wenn ich mich richtig erinner.

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Pascalony“ ()

    Pascalony schrieb:

    Rikudo schrieb:

    Ich möchte x selbst wählen und ein random a und ein random m finden die die Gleichung erfülen.

    Das macht aber doch schlichtweg keinen Sinn. Wenn du ein x wählst und du hast schon ein zufälliges a, dann ergibt sich m aus der Rechnung. Wozu dann noch Zufall anwenden?


    Ja ich habe mich unklar ausgedrückt. Ich möchte einen parameter random wählen und den anderen dann errechnen. Ich versuche jetzt mal was @Trade genannt hat mit dem EEA.
    Ich kapier aber noch nicht ganz wie ich dadurch meine Werte erhalten soll ..
    C# Developer
    Learning C++
    @Rikudo

    Möchtest du nur schauen ob die teilerfremd sind?

    Spoiler anzeigen

    VB.NET-Quellcode

    1. Option Strict On
    2. Option Explicit On
    3. Imports System.Numerics
    4. Imports System.Runtime.InteropServices
    5. Public Module Module1
    6. Private rand As New Random
    7. Public Sub Main()
    8. Dim inc As Int32 = 0
    9. Dim cnt As Int32 = 1000
    10. Dim idxcount As Int32 = 100
    11. Dim tmp() As IndexInfo
    12. Dim a, m, idx, minv, aidx As BigInteger
    13. Dim res As New List(Of IndexInfo())(idxcount)
    14. For i As Int32 = 0 To idxcount - 1
    15. inc = -1
    16. tmp = New IndexInfo(cnt - 1) {}
    17. idx = LongRandom(0, UInt32.MaxValue)
    18. If (idx And 1) = 0 Then idx -= 1
    19. While True
    20. a = LongRandom(0, UInt32.MaxValue)
    21. If (a And 1) = 0 Then a -= 1
    22. m = LongRandom(0, UInt64.MaxValue)
    23. If (m And 1) = 0 Then m -= 1
    24. aidx = a * idx
    25. If m <= aidx Then Continue While
    26. If IsCoprime(aidx, m) Then
    27. inc += 1
    28. minv = ModInv(a, m)
    29. 'If Not IsCoprime(a, m) Then Stop
    30. If inc >= cnt Then Exit While
    31. tmp(inc) = New IndexInfo() With {.a = a, .m = m, .idx = idx, .minv = minv}
    32. End If
    33. End While
    34. res.Add(tmp)
    35. Next
    36. Console.WriteLine("FINISH")
    37. Console.ReadLine()
    38. End Sub
    39. Private Function IsCoprime(ByVal bi1 As BigInteger, ByVal bi2 As BigInteger) As Boolean
    40. Return GetGCDBi(bi1, bi2) = 1
    41. End Function
    42. Private Function GetGCDBi(ByVal bi1 As BigInteger, ByVal bi2 As BigInteger) As BigInteger
    43. Return BigInteger.GreatestCommonDivisor(bi1, bi2)
    44. End Function
    45. Private Function LongRandom(ByVal min As UInt64, ByVal max As UInt64) As UInt64
    46. Dim size As Int32 = Marshal.SizeOf(GetType(UInt64))
    47. Dim buf As Byte() = New Byte(size - 1) {}
    48. rand.NextBytes(buf)
    49. Dim longRand As UInt64 = BitConverter.ToUInt64(buf, 0)
    50. Return CULng((Math.Abs(longRand Mod (max - min)) + min))
    51. End Function
    52. Private Function ModInv(ByVal a As BigInteger, ByVal n As BigInteger) As BigInteger
    53. Dim i As BigInteger = n, v As BigInteger = 0, d As BigInteger = 1
    54. Dim t, x As BigInteger
    55. While a > 0
    56. t = i / a : x = a : a = i Mod x : i = x
    57. x = d : d = v - t * x : v = x
    58. End While
    59. v = v Mod n
    60. If v < 0 Then v = (v + n) Mod n
    61. Return v
    62. End Function
    63. End Module


    Läuft bei mir recht zügig, obwohl ich ein Dinosauriersystem habe.


    Freundliche grüsse

    exc-jdbi

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „exc-jdbi“ ()

    Trade schrieb:

    Somit kannst Du für ein gewähltes x auch problemlos mit dem EEA ein inverses Element bestimmen, insofern m bekannt ist und dort 1 rauskommt als ggT. Wenn m prim ist, so ist der ggT auf jeden Fall 1.
    Insofern müsstest du halt alle m durchiterieren und dann immer den EEA anwenden. Dann findest Du alle Parameter, die die Gleichung erfüllen.

    Was ist der Unterschied ich für m keine prim Zahl wähle?
    X ist vorgegeben, ein m wähle ich (zufällig?). Wenn für X und M der gcd = 1 ist dann gibt der EEA mir mein passendes A aus, habe ich das richtig verstanden?
    Könntest du eventuell mal ein Beispiel machen?
    EDIT:
    Oki also ich habe mal deinen Ratschlag nach gebaut, aber es ist das gleiche Problem.
    Ich nutze den EEA um mein A zu erzeugen, für M wähle ich eine Primzahl.
    Ich teste hier mal 50 Zahlen, wobei immer noch ein grossteil nicht stimmt. Wie kann ich das beheben?

    C#-Quellcode

    1. using System;
    2. using System.Configuration;
    3. namespace BitTwiddling
    4. {
    5. internal class Program
    6. {
    7. private static Random rnd = new Random();
    8. private static int modInverse(int a, int n)
    9. {
    10. int i = n, v = 0, d = 1;
    11. while (a > 0)
    12. {
    13. int t = i / a, x = a;
    14. a = i % x;
    15. i = x;
    16. x = d;
    17. d = v - t * x;
    18. v = x;
    19. }
    20. v %= n;
    21. if (v < 0) v = (v + n) % n;
    22. return v;
    23. }
    24. private static int[] ExtendedEuclideanAlgorithm(int a, int b)
    25. {
    26. int x0 = 1, xn = 1;
    27. int y0 = 0, yn = 0;
    28. int x1 = 0;
    29. int y1 = 1;
    30. int q;
    31. int r = a % b;
    32. while (r > 0)
    33. {
    34. q = a / b;
    35. xn = x0 - q * x1;
    36. yn = y0 - q * y1;
    37. x0 = x1;
    38. y0 = y1;
    39. x1 = xn;
    40. y1 = yn;
    41. a = b;
    42. b = r;
    43. r = a % b;
    44. }
    45. return new[] {xn, yn, b};
    46. }
    47. private static uint GreatesCommonDivisor(uint a, uint b)
    48. {
    49. while (a != 0 && b != 0)
    50. {
    51. if (a > b)
    52. a %= b;
    53. else
    54. b %= a;
    55. }
    56. return a == 0 ? b : a;
    57. }
    58. private static bool IsCoprime(int a, int b)
    59. {
    60. return GreatesCommonDivisor((uint) a, (uint) b) == 1;
    61. }
    62. private static void VerifyValues(int x, int a, int m)
    63. {
    64. var inv = modInverse(a, m);
    65. if (x == inv)
    66. Console.WriteLine($"[VALID] {a}*x ≡ 1 (mod {m}) | x = {inv}");
    67. else
    68. Console.WriteLine($"[NOT VALID] {a}*x ≢ 1 (mod {m}) | x = {inv}");
    69. }
    70. public static void Main(string[] args)
    71. {
    72. for (int i = 0; i < 500; i++)
    73. {
    74. int x = rnd.Next(500, 100000);
    75. int m = FindM();
    76. if (!IsCoprime(x, m))
    77. {
    78. Console.WriteLine("No inverse elements.");
    79. continue;
    80. }
    81. // Calculate a from given x and choosen m
    82. var a = ExtendedEuclideanAlgorithm(x, m)[0];
    83. // Verify if the generated values actually satisfy the equation
    84. VerifyValues(x, a, m);
    85. }
    86. Console.ReadKey();
    87. }
    88. static bool isPrime(int number)
    89. {
    90. if (number == 1) return false;
    91. if (number == 2) return true;
    92. for (int i = 2; i <= Math.Ceiling(Math.Sqrt(number)); ++i)
    93. {
    94. if (number % i == 0) return false;
    95. }
    96. return true;
    97. }
    98. private static int FindM()
    99. {
    100. var m = 0;
    101. do
    102. {
    103. m = rnd.Next(5000, int.MaxValue);
    104. } while (!isPrime(m));
    105. return m;
    106. }
    107. }
    108. }


    Desweiteren ist mir aufgefallen, je größer die Zahl wird desto weniger richtige Ergebnisse gibt es.
    Für int.MaxValue habe ich kein einziges gefunden. Ist das eine Overflow Problem?
    C# Developer
    Learning C++

    Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von „Rikudo“ ()

    Rikudo schrieb:

    Was ist der Unterschied ich für m keine prim Zahl wähle?


    Wie du bereits selbst gesagt hast, muss Ggt(x, m) = 1 gelten, damit ax mod m = 1 gilt. Aus m ist prim, x mod m != 0 folgt IMMER, dass Ggt(x, m) = 1. Hierbei handelt es sich jediglich um ein hinreichendes, aber kein notwendiges Kriterium. Ich habe ja oben geschrieben, dass die Randbedingung nur ist, dass Ggt(x, m) = 1 ist. m muss keine Primzahl sein, es ist nur leicht sich eine Primzahl generieren zu lassen. Es gibt andere Zahlenpaare wie z.B x = 10, m = 9 wo Ggt(x, m) = 1 gilt. Deswegen schlage ich ja vor, dass du in FindM deine Abbruchbedingung abänderst.

    C#-Quellcode

    1. private static int FindM(int x)
    2. {
    3. int m = 0;
    4. do
    5. {
    6. m = _random.Next(5000, int.MaxValue);
    7. } while (GreatesCommonDivisor(m, x) != 1); //x, m auf Ggt = 1 statt auf prim testen
    8. return m;
    9. }



    Aber deine Implementierung funktioniert auch, wenn du noch auf x mod m != 0 prüfst:

    C#-Quellcode

    1. private static int FindM(int x)
    2. {
    3. int m;
    4. do
    5. {
    6. m = _random.Next(5000, int.MaxValue);
    7. } while (!IsPrime(m) && x % m != 0);
    8. return m;
    9. }


    Rikudo schrieb:

    X ist vorgegeben, ein m wähle ich (zufällig?). Wenn für X und M der gcd = 1 ist dann gibt der EEA mir mein passendes A aus, habe ich das richtig verstanden?


    Ja, das m ist zwar zufällig, aber eben so oft zufällig gewählt bis Ggt(x, m) = 1 gilt.

    Hier mal meine Implementierung:

    C#-Quellcode

    1. namespace EEA
    2. {
    3. internal class Program
    4. {
    5. private static Random _random = new Random();
    6. static void Main(string[] args)
    7. {
    8. int x = _random.Next(500, 100000);
    9. int m = FindM(x);
    10. Console.WriteLine($"x = {x} | m = {m} | invers = {ExtendedEuclideanAlgorithm(x, m)[0]}");
    11. Console.ReadLine();
    12. }
    13. private static int GreatesCommonDivisor(int a, int b)
    14. {
    15. if (b == 0)
    16. return a;
    17. else
    18. return GreatesCommonDivisor(b, a % b);
    19. }
    20. private static int[] ExtendedEuclideanAlgorithm(int a, int b)
    21. {
    22. int x0 = 1, xn = 1;
    23. int y0 = 0, yn = 0;
    24. int x1 = 0;
    25. int y1 = 1;
    26. int q;
    27. int r = a % b;
    28. while (r > 0)
    29. {
    30. q = a / b;
    31. xn = x0 - q * x1;
    32. yn = y0 - q * y1;
    33. x0 = x1;
    34. y0 = y1;
    35. x1 = xn;
    36. y1 = yn;
    37. a = b;
    38. b = r;
    39. r = a % b;
    40. }
    41. return new[] { xn, yn, b };
    42. }
    43. private static int FindM(int x)
    44. {
    45. int m = 0;
    46. do
    47. {
    48. m = _random.Next(5000, int.MaxValue);
    49. } while (GreatesCommonDivisor(m, x) != 1); //x, m auf Ggt = 1 statt auf prim testen
    50. return m;
    51. }
    52. }
    53. }



    Rikudo schrieb:

    Desweiteren ist mir aufgefallen, je größer die Zahl wird desto weniger richtige Ergebnisse gibt es.
    Für int.MaxValue habe ich kein einziges gefunden. Ist das eine Overflow Problem?


    Das stimmt so nicht. Die Ergebnisse sind bei richtiger Implementierung immer richtig. Ich hab mal ein Screenshot von einem Versuch von mir mit int.MaxValue angehängt. Ein korrektes Ergebnis.



    Edit:

    Habe deinen Fehler endlich gefunden, ist eigentlich peinlich, dass ich ihn nicht früher gefunden habe, aber egal.
    Du überprüfst ja ob modInverse(x, m) = ExtendedEuclideanAlgorithm(x, m)[0] ist. ABER: beide Funktionen liefern unterschiedliche Ergebnisse, obwohl beide richtig sind. Klingt verwirrend? Das liegt daran, dass wir nicht in unserem Körper der reellen Zahlen sind. Grob gesagt können in einem Restklassenring zwei "zwei unterschiedliche Zahlen" identisch sein. Beispiel: Restklassenring modulo 2:

    3 mod 2 = 1, 11 mod 2 = 1 => 3 = 11 in diesem Restklassenring.

    Das heißt du müsstest überprüfen, ob modInverse(x, m) = ExtendedEuclideanAlgorithm(x, m)[0] + n * m, mit n Element der ganzen Zahlen.

    Um auf das Beispiel aus deinem allerersten Post zurückzugreifen:

    x = 3, m = 11, a = ?
    Du hast gesagt a = 4. Gibt es noch eine andere Lösung? Wenden wir mal die obige Regel an:
    a = ExtendedEuclideanAlgorithm(x, m)[0] + n * m (einsetzen)
    => a = ExtendedEuclideanAlgorithm(3, 11)[0] + n * 11
    => a = 4 + n * 11
    Für n = 0 erhalten wir dein Ergebnis, nämlich 4. Aber:
    a = 4 + (-1) * 11 = 4 - 11 = -7
    Jetzt sagen wir, dass modInverse 4 rauskriegt, aber dein Euklidischer Algorithmus -7.
    C# arbeitet aber mit den reellen Zahlen, d.h -7 != 4. Aber das Ergebnis ist äquivalent, was auffällt, wenn du die Rückrechnung machst:

    4*3 mod 11 = 1 => korrekt
    -7*3 mod 11 = 1 => ebenfalls korrekt

    Du kannst dir das so vorstellen wie den komplexen Logarithmus, der eben auch noch auf Vielfache von 2*pi definiert ist, falls dir das was sagt.

    TL;DR: Der Compiler vergleicht zwei Werte, die auf Grund der Gesetze der reellen Zahlen ungleich sind, obwohl sie nach dem Restklassenring, der eigentlich betrachtet wird, gleich sind.

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „Pascalony“ ()

    @Pascalony danke für deine ausführliche Antwort. Ich gehe mal davon aus dass statt einem hardcoded Beispiel:

    C#-Quellcode

    1. Console.WriteLine($"x = {x} | m = {m} | invers = {ExtendedEuclideanAlgorithm(10, 9)[2]}");

    eigentlich x und m an die EEA Funktion ubergeben werden sollen, oder?

    C#-Quellcode

    1. Console.WriteLine($"x = {x} | m = {m} | invers = {ExtendedEuclideanAlgorithm(x, m)[0]}"); // Der [0]-Wert entspricht dann a?


    In deinem Fall wird aber immer 1 als A ausgegeben, egal für welche Zahl. Ich kann dein Beispiel nicht reproduzieren, ich bekomme immer 1 für A?
    Kann man auch ein A != 1 finden das die Gleichung erfüllt? Das sollte eigentlich gehen oder (siehe mein altes Beispiel)
    C# Developer
    Learning C++
    Ja, mein Fehler sorry. Richtig wäre

    C#-Quellcode

    1. Console.WriteLine($"x = {x} | m = {m} | invers = {ExtendedEuclideanAlgorithm(x, m)[0]}");


    Liest dir aber mal mein Edit durch, da steht das relevante drin.

    Edit:

    Rikudo schrieb:

    Kann man auch ein A != 1 finden das die Gleichung erfüllt? Das sollte eigentlich gehen oder (siehe mein altes Beispiel)


    Mein Fehler, es ist das 0te Element des Arrays, also ExtendedEuclideanAlgorithm(x, m)[0]

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Pascalony“ ()

    @Pascalony Ja das macht Sinn. Es gibt unendlich viele Möglichkeiten. Das ist aber auch gleichzeitig ein Problem da nicht garantiert ist das der Output die Ursprungliche Zahl X ist, oder nur eine andere Zahl die X in M entspricht. Beispielsweise:
    -146317049*x ≡ 1 (mod 1371696084)
    wurde von deinem Code als Möglichkeit für int.MaxValue, d.h.: 2147483647, vorgeschlagen.
    Wolfram Alpha schlägt als Lösung für X jedoch 775787563 vor. (wolframalpha.com/input/?i=-146…%89%A1+1+(mod+1371696084)).
    Ich nehme an es gibt keine Option das ganze in meinem Programm eine bestimmte Lösung, also das ursprüngliche X, zu erzwingen?
    C# Developer
    Learning C++
    @Rikudo

    Okay, x ist ja durch Zufall gegeben, m hast du ebenfalls durch deine Funktion gefunden. Wolfram macht es glaube ich so, dass das kleinste Ergebnis > 0 ausgewählt wird. Das würde bedeuten du müsstest nach meiner Funktion das a berechnen und anschließend solange m hinzuaddieren, bis a > 0. Dann solltest du das Ergebnis erhalten, dass auch Wolfram erhalten hat. Die Frage ist ja wieso du das x erzwingen willst. Es ist ja schon in der ursprünglichen Form da. Es wird nie abgeändert. Oder geht es dir darum, dass dein Ergebnis mit Wolfram übereinstimmt?

    @Pascalony Ich versuche es mal umzuschreiben. Aber die Generierung von long werten zwischen einem Minimum und einem Maximum ist etwas problematisch. Es scheint so als bietet das Framework dafür keine Funktion. Gibt es eine Möglichkeit für das mit long values:

    C#-Quellcode

    1. m = _random.Next(1, long.MaxValue);


    EDIT: Habe es hinbekommen:

    C#-Quellcode

    1. private static long GenerateInt64(long minimum, long maximum)
    2. {
    3. return (long) Math.Floor((_random.NextDouble() * (maximum - minimum)) + minimum);
    4. }

    C# Developer
    Learning C++

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Rikudo“ ()

    @Rikudo

    Jo die geht auch, oder schau in meinem Beispiel oben. Long oder Ulong-Random

    VB.NET-Quellcode

    1. Private Function LongRandom(ByVal min As UInt64, ByVal max As UInt64) As UInt64
    2. Dim size As Int32 = Marshal.SizeOf(GetType(UInt64))
    3. Dim buf As Byte() = New Byte(size - 1) {}
    4. rand.NextBytes(buf)
    5. Dim longRand As UInt64 = BitConverter.ToUInt64(buf, 0)
    6. Return CULng((Math.Abs(longRand Mod (max - min)) + min))
    7. End Function


    Übrigends noch was.
    das xn/yn kann ja jetzt bewiesen werden

    Eigendlich sollte das jetzt weiter gehen für den korrekte zahlenmässige Beweis. Nähmlich so

    Beispiel: x = 61630 | m = 112242859 | invers = 41271060
    Wähle eine beliebige Zahl z die kleiner ist als m. (z < m)
    zum Beispiel: z = m-1 = 112242858

    Beweis der Inverse
    ***********************
    z(112242858) * x(61630) % m(112242859 ) = 112181229
    (112181229) * invers(41271060) % m(112242859 ) = z(112242858)

    womit bewiesen ist, dass die invers die inverse von x ist mit m als modulo.


    Freundliche Grüsse

    exc-jdbi

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „exc-jdbi“ ()