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.

    Rechnerisch



    Und das sollte man sich im Hinterkopf halten.



    Hier noch warum ich das so mache es gilt ggT(a,m) = 1
    In der Gleichung wo "immer" steht, kann das k incrementiert werden, bis mod x = 0.
    So lässt sich das x sehr einfach und sicher lösen.




    Freundliche Grüsse

    exc-jdbi

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

    Und So sieht das programmiert aus.

    VB

    VB.NET-Quellcode

    1. Option Strict On
    2. Option Explicit On
    3. Imports System.Numerics
    4. Public Module Module1
    5. Public Sub Main()
    6. Dim x1 = XModSolve(5, 2, 11)
    7. Dim x2 = XModSolve(101, 15, 89)
    8. Dim x3 = XModSolve(123456, 15, 89)
    9. Dim x4 = XModSolve(123456789, 15, 89)
    10. Dim xx1 = XModSolve(5, 2, 11, 1000)
    11. Dim xx2 = XModSolve(101, 15, 89, 1000)
    12. Dim xx3 = XModSolve(123456, 15, 89, 1000)
    13. Dim xx4a = XModSolve(123456789, 15, 89, 1000)
    14. Stop
    15. End Sub
    16. Private Function XModSolve(ByVal a As Int32, ByVal r As Int32, ByVal m As Int32) As Int32
    17. If GetGCD(a, m) = 1 Then
    18. Dim t = (m - a) Mod m, tt = t * m - r
    19. Dim inc As Int32 = -1, x As Int32 = -1
    20. While Not x = 0
    21. inc += 1
    22. x = (tt - m * inc) Mod t
    23. End While
    24. Return (tt - m * inc) \ t
    25. End If
    26. Return -1
    27. End Function
    28. Private Function XModSolve(ByVal a As Int32, _
    29. ByVal r As Int32, _
    30. ByVal m As Int32, _
    31. ByVal xmax As Int32) As Int32()
    32. If GetGCD(a, m) = 1 Then
    33. Dim res As New List(Of Int32)
    34. Dim inc As Int32 = -1, aa As Int64 = a mod m
    35. While inc <= xmax
    36. inc += 1
    37. If (aa * inc) Mod m = r Then
    38. res.Add(inc)
    39. End If
    40. End While
    41. Return res.ToArray
    42. End If
    43. Return Nothing
    44. End Function
    45. Private Function GetGCD(ByVal i1 As Int32, ByVal i2 As Int32) As Int32
    46. Return If(i2 = 0, i1, GetGCD(i2, i1 Mod i2))
    47. End Function
    48. End Module


    CS

    C#-Quellcode

    1. using System;
    2. using System.Linq;
    3. using System.Text;
    4. using System.Diagnostics;
    5. using System.Collections.Generic;
    6. namespace XModSolver
    7. {
    8. class Program
    9. {
    10. static void Main()
    11. {
    12. int x1 = XModSolve(5, 2, 11);
    13. int x2 = XModSolve(101, 15, 89);
    14. int x3 = XModSolve(123456, 15, 89);
    15. int x4 = XModSolve(123456789, 15, 89);
    16. int[] xx1 = XModSolve(5, 2, 11, 1000);
    17. int[] xx2 = XModSolve(101, 15, 89, 1000);
    18. int[] xx3 = XModSolve(123456, 15, 89, 1000);
    19. int[] xx4 = XModSolve(123456789, 15, 89, 1000);
    20. Debugger.Break();
    21. }
    22. private static int XModSolve(int a, int r, int m)
    23. {
    24. if (GetGCD(a, m) == 1)
    25. {
    26. int inc = -1, x = -1;
    27. int t = (m - a) % m, tt = t * m - r;
    28. while (x != 0)
    29. {
    30. inc += 1;
    31. x = (tt - m * inc) % t;
    32. }
    33. return (tt - m * inc) / t;
    34. }
    35. return -1;
    36. }
    37. private static int[] XModSolve(int a, int r, int m, int xmax)
    38. {
    39. if (GetGCD(a, m) == 1)
    40. {
    41. int inc = -1; long aa = a % m;
    42. List<int> res = new List<int>();
    43. while (inc <= xmax)
    44. {
    45. inc += 1;
    46. if ((aa * inc) % m == r)
    47. res.Add(inc);
    48. }
    49. return res.ToArray();
    50. }
    51. return null;
    52. }
    53. private static int GetGCD(int i1, int i2)
    54. {
    55. return i2 == 0 ? i1 : GetGCD(i2, i1 % i2);
    56. }
    57. }
    58. }


    Freundliche Grüsse

    exc-jdbi

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

    Hallo @Rikudo

    Die Gleichung: ax ≡ r mod m es gilt ggT(a,m) = 1
    Die Parameter von x = XModSolve(a,r,m) sind genau so zugeordnet.

    a steht für den Koeffizienten von x, r für den Restwert (der aus Modulo entstanden ist) und m ist der Modulowert.

    Beim der zweiten XModSolve-Funktion, bei der ein Array zurückgegeben wird, kommt noch am Schluss das kmax hinzu. Es bezieht sich auf den maximalen Incrementwert, also hier 1000. D.H. die Funktion nutzt als k die Werte 0 - 1000.

    Sorry falsch.
    In der zweiten XModSolve-Funktion, bei der ein Array zurückgegeben wird, kommt noch am Schluss das kmax hinzu.
    Das ist jetzt wirklich Missverständlich, das habe ich ursprünglich bei mir anders gelöst. Diese Funktion simuliert die Gleichung
    ax mod m = r. Somit ist der kmax der maximale Incrementwert für x. Es wird also für x die Werte 0 - 1000 eingesetzt. Habe es oben im Codee umgeändert kmax zu xmax

    Freundliche Grüsse

    exc-jdbi

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

    @exc-jdbi Danke schonmal für deine Antwort :)
    Also ich mache dann wohl irgendwas falsch.

    C#-Quellcode

    1. 394184853*x ≡ 1 (mod 1319133736)
    ist laut Wolfram Alpha genau

    C#-Quellcode

    1. 111222333

    Deine Funktion kommt aber gar nicht zum ende (habe nach ein paar Minuten abgebrochen)

    C#-Quellcode

    1. Console.WriteLine(XModSolve(394184853, 1, 1319133736));


    Generell dachte ich das man wenn man a und m (und r) hat, x ganz effizient berechnen kann, aber irgendwie scheitn das ja sehr rechenintensiv zu sein. ? :/



    @exc-jdbi Ich hab nochmal weitergebastelt und mit deiner und der Hilfe der anderen Post und des Internets folgendes auf die Beine gestellt bekommen:

    Generator.cs

    C#-Quellcode

    1. public class Generator
    2. {
    3. private readonly int _number;
    4. private static readonly Random _random = new Random();
    5. public Generator(int number)
    6. {
    7. _number = number;
    8. }
    9. public int[] GenerateAandM()
    10. {
    11. int m = FindM(_number);
    12. int a = ExtendedEuclideanAlgorithm(_number, m)[1];
    13. Console.WriteLine($"[x = {_number} | m = {m} | a = {a}]");
    14. Console.WriteLine($"{a}*x ≡ 1 (mod {m}) | {_number}");
    15. return new[] {a, m};
    16. }
    17. private static int GreatesCommonDivisor(int a, int b)
    18. {
    19. if (b == 0)
    20. return a;
    21. return GreatesCommonDivisor(b, a % b);
    22. }
    23. static int[] ExtendedEuclideanAlgorithm(int a, int b)
    24. {
    25. int s = 0, t = 1, u = 1, v = 0;
    26. while (a != 0)
    27. {
    28. int q = b / a | 0, r = b % a;
    29. int m = s - u * q, n = t - v * q;
    30. b = a;
    31. a = r;
    32. s = u;
    33. t = v;
    34. u = m;
    35. v = n;
    36. }
    37. return new[] {b, s, t};
    38. }
    39. private static int FindM(int x)
    40. {
    41. int m = 0;
    42. do
    43. {
    44. m = _random.Next(3000, int.MaxValue);
    45. } while (GreatesCommonDivisor(m, x) != 1);
    46. return m;
    47. }
    48. }[b]
    [/b]

    Solver.cs

    C#-Quellcode

    1. public class Solver
    2. {
    3. private readonly int _a;
    4. private readonly int _m;
    5. public Solver(int a, int m)
    6. {
    7. _a = a;
    8. _m = m;
    9. }
    10. public void Solve()
    11. {
    12. Console.WriteLine(ModInverse(_a, _m));
    13. }
    14. static int Mod(int n, int m)
    15. {
    16. return (n % m + m) % m;
    17. }
    18. static int ModInverse(int z, int n)
    19. {
    20. var result = ExtendedEuclideanAlgorithm(z, n);
    21. if (result[0] != 1)
    22. throw new Exception("GCD must be 1");
    23. return Mod(result[1], n);
    24. }
    25. static int[] ExtendedEuclideanAlgorithm(int a, int b)
    26. {
    27. int s = 0, t = 1, u = 1, v = 0;
    28. while (a != 0)
    29. {
    30. int q = b / a | 0, r = b % a;
    31. int m = s - u * q, n = t - v * q;
    32. b = a;
    33. a = r;
    34. s = u;
    35. t = v;
    36. u = m;
    37. v = n;
    38. }
    39. return new[] {b, s, t};
    40. }
    41. }


    Testing:

    C#-Quellcode

    1. Generator generator = new Generator(int.MaxValue); // Wert X, der verarbeitet werden soll
    2. var res = generator.GenerateAandM();
    3. Solver solver = new Solver(res[0], res[1]);
    4. solver.Solve();


    Ich gebe a und m and und erhalte x, sogar sehr schnell.
    Beispielsweise wähle ich für X = 111222333 wird z.B. als paar vorgeschlagen:

    C#-Quellcode

    1. A=-302580723
    2. M=1356587320


    Gebe ich diese Werte in meinem Solver an, erhalte ich genau

    C#-Quellcode

    1. 111222333


    Soweit so gut, ich habe aber immer noch das Problem das bei machen Werten wie Beispielsweise int.MaxValue oder anderen großen Werten Falsche Werte generiert werden oder ein die Anwendung einen Fehler wirft GCD != 1.

    Ein ein paar Beispiele:

    C#-Quellcode

    1. [x = 555666777 | m = 407644414 | a = -76139821]
    2. -76139821*x ≡ 1 (mod 407644414) | 555666777
    3. Ergebnis : 148022363 // Falsch sollte 555666777 sein.

    C#-Quellcode

    1. [x = 2147483647 | m = 1648192498 | a = 283582465]
    2. 283582465*x ≡ 1 (mod 1648192498) | 2147483647
    3. Ergebnis : 499291149 // Falsch sollte 2147483647 sein.


    Was ist das für ein Bug und wie kann ich dafür sorgen das für alle Werte von int.MinValue bis int.maxValue für meine A und M das korrekte X berechnet wird?
    Oder haben die falschen Werte wieder mit dem Zahlenring zu tun? wenn ja wie kann ich dafür sorgen das ich von den vielen Lösungen die nehme die mein X ist?

    Beiträge zusammengefügt. ~Thunderbolt
    C# Developer
    Learning C++

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

    Hallo @Rikudo

    Den Wert 111222333 kann ich auch bestätigen, habe den nähmlich gerade bekommen. Ich muss schon zugeben, mein Algo ist natürlich für solch grosse Zahlen nicht so geeignet. Musste den Biginteger kurz einspannen.

    Deinen Code werde ich morgen Abend oder am Samstag anschauen. Ich kann aber nicht versprechen, ob ich da was finde. Eventuell gibts ja noch andere Möglichkeiten zum Lösen solcher Gleichungen, also auch für grössere Zahlen.

    Hier noch die Primefactors, die ich errechnet habe.
    Sind also wirklich Teilfremd zueinander, wie errechnet.
    394184853 >>> Primefactors >>> 3*3*3*839*17401
    1319133736 >>> Primefactors >>> 2*2*2*164891717

    Freundliche Grüsse

    exc-jdbi
    @exc-jdbi Okay cool, dann bin ich mal gespannt ^^
    Der Fehler liegt irgendwo in der Generierung von A und M nicht im Solver.

    Hier ein Beispiel, die letzten beiden generierten paare für A und M ergeben nicht das gewünschte X:

    C#-Quellcode

    1. Richtig:
    2. [x = 111111111 | m = 1920041414 | a = 48813355]
    3. 48813355*x ≡ 1 (mod 1920041414) | 111111111
    4. [x = 222222222 | m = 1883323625 | a = 880426558]
    5. 880426558*x ≡ 1 (mod 1883323625) | 222222222
    6. [x = 333333333 | m = 1470422987 | a = -131482446]
    7. -131482446*x ≡ 1 (mod 1470422987) | 333333333
    8. [x = 444444444 | m = 2100474613 | a = 786023953]
    9. 786023953*x ≡ 1 (mod 2100474613) | 444444444
    10. [x = 555555555 | m = 1383048137 | a = 252785280]
    11. 252785280*x ≡ 1 (mod 1383048137) | 555555555
    12. [x = 666666666 | m = 1224606413 | a = -120539455]
    13. -120539455*x ≡ 1 (mod 1224606413) | 666666666
    14. Falsch:
    15. [x = 777777777 | m = 754469410 | a = -188801767]
    16. -188801767*x ≡ 1 (mod 754469410) | 777777777
    17. [x = 888888888 | m = 601511051 | a = -277152805]
    18. -277152805*x ≡ 1 (mod 601511051) | 888888888

    C# Developer
    Learning C++

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

    Hallo @Rikudo

    Meinen auch noch schnell angepasst. es gilt:
    Lösbar wenn r mod ggT(a,m) = 0

    VB

    VB.NET-Quellcode

    1. Option Strict On
    2. Option Explicit On
    3. Imports System.Numerics
    4. Public Module Module1
    5. Dim rand As New Random
    6. Public Sub Main()
    7. Test()
    8. End Sub
    9. Private Sub Test()
    10. Dim m, x, g, r As Int32
    11. For a As Int32 = -10000000 To 10000000
    12. If (a > -2) AndAlso (a < 2) Then Continue For
    13. Do
    14. m = rand.Next(5, 1000)
    15. Loop While Not GetGCD(a, m) = 1
    16. r = rand.Next(m)
    17. x = XModSolve(a, r, m)
    18. g = CheckMod(a, x, m)
    19. If Not g = r Then Stop
    20. Next
    21. End Sub
    22. Private Function XModSolve(ByVal a As Int32, ByVal m As Int32) As Int32
    23. If a = m Then Return 1
    24. Dim gcd = GetGCD(a, m)
    25. If gcd > 1 Then
    26. a = If(a = gcd, a, a \ gcd)
    27. m = If(m = gcd, m, m \ gcd)
    28. gcd = GetGCD(a, m)
    29. Return If(gcd > 1, gcd, m)
    30. End If
    31. Return m
    32. End Function
    33. Private Function XModSolve(ByVal a As Int32, ByVal r As Int32, ByVal m As Int32) As Int32
    34. If (r > 0) AndAlso (m > r) Then
    35. Dim gcd = GetGCD(a, m)
    36. If r Mod gcd = 0 Then
    37. gcd = Math.Abs(gcd)
    38. a \= gcd : r \= gcd : m \= gcd
    39. Dim sign = If(a > 0, True, False)
    40. a = If(a > 0, a, -a)
    41. Dim x = r * ExtInv(EEA(a, m)(1), m)
    42. If sign AndAlso x < 0 Then Return -x
    43. If Not sign AndAlso x > 0 Then Return -x
    44. Return x
    45. End If
    46. Throw New Exception("GCD must be divisor of r")
    47. End If
    48. If r = 0 Then Return XModSolve(a, m)
    49. Return 0
    50. End Function
    51. Private Function ExtInv(ByVal i1 As Int32, ByVal m As Int32) As Int32
    52. i1 = i1 Mod m
    53. Return CInt((CLng(i1) + m) Mod m)
    54. End Function
    55. Private Function EEA(ByVal a As Int32, ByVal b As Int32) As Int32()
    56. a = If(a > 0, a, -a)
    57. Dim q As New List(Of Int32)(30)
    58. Dim aa As Int32 = a, bb As Int32 = b, r As Int32 = b
    59. While r > 0
    60. q.Add(a \ b)
    61. r = a Mod b
    62. a = b : b = r
    63. End While
    64. Dim rr As Int32 = a, ax = 1I, by = 0I
    65. For i As Int32 = q.Count - 2 To 0 Step -1
    66. r = CInt(by - (q(i) * CLng(ax)))
    67. by = ax : ax = r
    68. Next
    69. Dim check As Int64 = CLng(ax) * aa + CLng(by) * bb
    70. If (Not check = 1) OrElse (Not check = -1) Then
    71. Dim t As Int32 = ax
    72. ax = by : by = t
    73. End If
    74. Return New Int32() {rr, ax, by}
    75. End Function
    76. Private Function CheckMod(ByVal a As Int32, ByVal x As Int32, ByVal m As Int32) As Int32
    77. Dim aa = New BigInteger(a), xx = New BigInteger(x)
    78. Return CInt((aa * xx) Mod m)
    79. End Function
    80. Private Function GetGCD(ByVal i1 As Int32, ByVal i2 As Int32) As Int32
    81. Return If(i2 = 0, i1, GetGCD(i2, i1 Mod i2))
    82. End Function
    83. End Module

    CS

    C#-Quellcode

    1. using System;
    2. using System.Linq;
    3. using System.Text;
    4. using System.Numerics;
    5. using System.Diagnostics;
    6. using System.Collections.Generic;
    7. namespace CSModGleichungLösen
    8. {
    9. class Program
    10. {
    11. static Random rand = new Random();
    12. static void Main(string[] args)
    13. {
    14. Test();
    15. }
    16. private static void Test()
    17. {
    18. int m, x, g, r;
    19. for (int a = -10000000; a <= 10000000; a++)
    20. {
    21. if ((a > -2) && (a < 2)) continue;
    22. do {
    23. m = rand.Next(5, 1000);
    24. } while (GetGCD(a, m) != 1);
    25. r = rand.Next(m);
    26. x = XModSolve(a, r, m);
    27. g = CheckMod(a, x, m);
    28. if (g != r) Debugger.Break();
    29. }
    30. }
    31. private static int XModSolve(int a, int m)
    32. {
    33. if (a == m) return 1;
    34. int gcd = GetGCD(a, m);
    35. if (gcd > 1)
    36. {
    37. a = (a == gcd) ? a : a / gcd;
    38. m = (m == gcd) ? m : m / gcd;
    39. gcd = GetGCD(a, m);
    40. return gcd > 1 ? gcd : m;
    41. }
    42. return m;
    43. }
    44. private static int XModSolve(int a, int r, int m)
    45. {
    46. if ((r > 0) && (m > r))
    47. {
    48. int gcd = GetGCD(a, m);
    49. if (r % gcd == 0)
    50. {
    51. gcd = Math.Abs(gcd);
    52. a /= gcd; r /= gcd; m /= gcd;
    53. var sign = a > 0 ? true : false;
    54. a = a > 0 ? a : -a;
    55. int x = r * ExtInv(EEA(a, m)[1], m);
    56. if (sign && x < 0) return -x;
    57. if (!sign && x > 0) return -x;
    58. return x;
    59. }
    60. throw new Exception("GCD must be divisor of r");
    61. }
    62. if (r == 0) return XModSolve(a, m);
    63. return 0;
    64. }
    65. private static int[] EEA(int a, int b)
    66. {
    67. a = a > 0 ? a : -a;
    68. int aa = a, bb = b;
    69. List<int> q = new List<int>(30);
    70. int r = b;
    71. while (r > 0)
    72. {
    73. q.Add(a / b);
    74. r = a % b;
    75. a = b; b = r;
    76. }
    77. int rr = a; int ax = 1;int by = 0;
    78. for (int i = q.Count - 2; i >= 0; i--)
    79. {
    80. r = (int)(by - (q[i] * (long)ax));
    81. by = ax; ax = r;
    82. }
    83. long check = ((long)ax * (long)aa) + ((long)by * (long)bb);
    84. if ((check != 1) || (check != -1))
    85. {
    86. int t = ax;
    87. ax = by; by = t;
    88. }
    89. return new int[] { rr, ax, by };
    90. }
    91. private static int ExtInv(int i1, int m)
    92. {
    93. i1 = i1 % m;
    94. return (int)(((long)i1 + (long)m) % (long)m);
    95. }
    96. private static int CheckMod(int a, int x, int m)
    97. {
    98. long aa = a, xx = x, mm = m;
    99. return (int)((aa * xx) % mm);
    100. }
    101. private static int GetGCD(int i1, int i2)
    102. {
    103. return i2 == 0 ? i1 : GetGCD(i2, i1 % i2);
    104. }
    105. }
    106. }


    Testlauf

    VB.NET-Quellcode

    1. Private Sub Test()
    2. Dim m, x, g, r As Int32
    3. For a As Int32 = -10000000 To 10000000
    4. If (a > -2) AndAlso (a < 2) Then Continue For
    5. r = rand.Next(5, 1000)
    6. Do
    7. m = rand.Next(r + 1, 2000)
    8. Loop While Not (r Mod GetGCD(a, m) = 0)
    9. x = XModSolve(a, r, m)
    10. g = CheckMod(a, x, m)
    11. If Not g = r Then Stop
    12. Next
    13. End Sub

    Testlauf 1 mod m

    VB.NET-Quellcode

    1. Private Sub Test()
    2. Dim m, x, g, r As Int32
    3. For a As Int32 = -10000000 To 10000000
    4. If (a > -2) AndAlso (a < 2) Then Continue For
    5. r = 1 ' rand.Next(5, 1000)
    6. Do
    7. m = rand.Next(r + 1, 2000)
    8. Loop While Not (r Mod GetGCD(a, m) = 0)
    9. x = XModSolve(a, r, m)
    10. g = CheckMod(a, x, m)
    11. If Not g = r Then Stop
    12. Next
    13. End Sub

    Testlauf Random

    VB.NET-Quellcode

    1. Private Sub Test()
    2. 'Zum suchen von m gilt 'r mod ggT(a,m) = 0'
    3. 'Zufälliges a und r. Daraus dann m suchen.
    4. Dim m, x, g, r, a, p As Int32
    5. Dim cnt As Int32 = 10000000
    6. Dim inc As Int32 = -10000000
    7. Dim wurz = CInt(Math.Sqrt(Int32.MaxValue))
    8. While inc < cnt
    9. inc += 1
    10. a = rand.Next(Int32.MinValue, Int32.MaxValue)
    11. If (a > -2) AndAlso (a < 2) Then Continue While
    12. 'Bedingung
    13. 'm * r < Int32.MaxValue, r > 0, m > r
    14. r = rand.Next(1, wurz - 20)
    15. p = Int32.MaxValue \ r
    16. Do
    17. m = rand.Next(r + 1, p)
    18. Loop While Not (r Mod GetGCD(a, m) = 0)
    19. x = XModSolve(a, r, m)
    20. g = CheckMod(a, x, m)
    21. If Not g = r Then Stop
    22. End While
    23. End Sub


    Zu deinem Code.
    Ich habe den aber noch nicht genau angeschaut. Nur kurz überflogen.
    Ich vermute aber, dass du einen Überlauf (muss nicht falsch sein) hast, der bei den Beispielen

    VB.NET-Quellcode

    1. [x = 555666777 | m = 407644414 | a = -76139821]'555666777 ist die -1 Mod m
    2. 'und
    3. [x = 2147483647 | m = 1648192498 | a = 283582465]'499291149 ist korrekt

    einen entsprechenden Wert generiert. Ob das jetzt beim Solver oder beim Generator entstanden ist, muss ich genauer anscheuen.


    Freundliche Grüsse

    exc-jdbi

    Dieser Beitrag wurde bereits 13 mal editiert, zuletzt von „exc-jdbi“ () aus folgendem Grund: Erweitert mit Solver wenn r = 0, Testlauf C# I.O.

    @exc-jdbi Danke für deine Mühen. Ich werde mal deinen Code in C# umschreiben und etwas damit rumprobieren.
    Wenn du den overflow-bug bzw das Problem in meinem Code findest wäre hammer :D
    Ich möchte nämlich das ich für den kompletten Integer Wertebereich (später evtl Long) gültige Werte erhalte^^
    C# Developer
    Learning C++
    @Rikudo

    Ich hab in deinen Code, meine EEA genommen.
    Bei dir entsteht der Fehler wahrscheinlich an mehreren Orten, unter anderem in der Funktion Mod() beim Solver

    C#-Quellcode

    1. return (n % m + m) % m;// Overflowprobleme



    Bei mir lauft es richtig.
    VB

    VB.NET-Quellcode

    1. Option Strict On
    2. Option Explicit On
    3. Public Module Module1
    4. Public Sub Main()
    5. Dim solve As New Solver()
    6. Dim generator As New Generator(3000, Int32.MaxValue)
    7. Dim res() As Int32
    8. For i As Int32 = 0 To 100000
    9. res = generator.GenerateAandM()
    10. solve.Solve(res(0), res(1))
    11. Next
    12. Console.ReadKey()
    13. End Sub
    14. End Module
    15. Public Class Solver
    16. Public Sub Solve(ByVal a As Int32, ByVal m As Int32)
    17. Dim eeax = EEA(a, m)
    18. Dim xx = eeax(1), x As Int32 = xx
    19. 'If xx < 0 Then Stop
    20. If (a < 0) AndAlso (xx > 0) Then x = ExtInv(xx, a, m)
    21. If (a > 0) AndAlso (xx < 0) Then x = ExtInv(xx, a, m)
    22. Console.WriteLine("[x = {0} | m = {1} | a = {2}]", x, m, a)
    23. Console.WriteLine("({0} * {1}) mod {2} = {3}", a, x, m, (CLng(a) * x) Mod m)
    24. Console.WriteLine() : Console.WriteLine()
    25. 'If Not (CLng(a) * x) Mod m = 1 Then Stop
    26. End Sub
    27. Private Function ExtInv(ByVal x As Int32, ByVal a As Int32, ByVal m As Int32) As Int32
    28. Dim t = CInt((CLng(x) + m) Mod m)
    29. If (a < 0) AndAlso t > 0 Then Return -t
    30. If (a > 0) AndAlso t < 0 Then Return -t
    31. Return t
    32. End Function
    33. Private Function EEA(ByVal a As Int32, ByVal b As Int32) As Int32()
    34. a = If(a > 0, a, -a)
    35. Dim aa As Int32 = a, bb As Int32 = b, m As Int32 = b
    36. Dim q As New List(Of Int32)(30), r As Int32 = b
    37. While r > 0
    38. q.Add(a \ b)
    39. r = a Mod b
    40. a = b : b = r
    41. End While
    42. Dim rr As Int32 = a, ax = 1I, by = 0
    43. For i As Int32 = q.Count - 2 To 0 Step -1
    44. r = CInt(by - (q(i) * CLng(ax)))
    45. by = ax : ax = r
    46. Next
    47. Dim check As Int64 = CLng(ax) * aa + CLng(by) * bb
    48. If (Not check = 1) OrElse (Not check = -1) Then
    49. Dim t As Int32 = ax
    50. ax = by : by = t
    51. End If
    52. check = CLng(ax) * aa + CLng(by) * bb
    53. Return New Int32() {rr, ax, by}
    54. End Function
    55. Private Function GCD(ByVal i1 As Int32, ByVal i2 As Int32) As Int32
    56. Return If(i2 = 0, i1, Me.GCD(i2, i1 Mod i2))
    57. End Function
    58. End Class
    59. Public Class Generator
    60. Private _random As New Random
    61. Private ReadOnly _maxnum As Int32
    62. Private ReadOnly _minnum As Int32
    63. Public Function GenerateAandM() As Int32()
    64. Dim x = Me._maxnum
    65. Dim m = Me.FindM(x)
    66. Dim a = ExtInv(EEA(x, m)(1), x, m)
    67. 'If Not GCD(a, m) = 1 Then Stop
    68. Console.WriteLine("[x = {0} | m = {1} | a = {2}]", x, m, a)
    69. Console.WriteLine("({0} * {1}) mod {2} = {3}", a, x, m, (CLng(a) * x) Mod m)
    70. Console.WriteLine()
    71. 'If Not (CLng(a) * x) Mod m = 1 Then Stop
    72. Return New Int32() {a, m}
    73. End Function
    74. Private Function ExtInv(ByVal a As Int32, ByVal x As Int32, ByVal m As Int32) As Int32
    75. Dim t = CInt((CLng(a) + m) Mod m)
    76. If (x < 0) AndAlso t > 0 Then Return -t
    77. If (x > 0) AndAlso t < 0 Then Return -t
    78. Return t
    79. End Function
    80. Private Function FindM(ByVal x As Int32) As Int32
    81. Dim m As Int32
    82. Do
    83. m = Me._random.Next(Me._minnum, Me._maxnum)
    84. Loop While Not Me.GCD(m, x) = 1
    85. Return m
    86. End Function
    87. Private Function EEA(ByVal a As Int32, ByVal b As Int32) As Int32()
    88. a = If(a > 0, a, -a)
    89. Dim aa As Int32 = a, bb As Int32 = b, m As Int32 = b
    90. Dim q As New List(Of Int32)(30), r As Int32 = b
    91. While r > 0
    92. q.Add(a \ b)
    93. r = a Mod b
    94. a = b : b = r
    95. End While
    96. Dim rr As Int32 = a, ax = 1I, by = 0
    97. For i As Int32 = q.Count - 2 To 0 Step -1
    98. r = CInt(by - (q(i) * CLng(ax)))
    99. by = ax : ax = r
    100. Next
    101. Dim check As Int64 = CLng(ax) * aa + CLng(by) * bb
    102. If (Not check = 1) OrElse (Not check = -1) Then
    103. Dim t As Int32 = ax
    104. ax = by : by = t
    105. End If
    106. 'check = ax * aa + by * bb;
    107. Return New Int32() {rr, ax, by}
    108. End Function
    109. Private Function GCD(ByVal i1 As Int32, ByVal i2 As Int32) As Int32
    110. Return If(i2 = 0, i1, Me.GCD(i2, i1 Mod i2))
    111. End Function
    112. Public Sub New(ByVal minnum As Int32, ByVal maxnum As Int32)
    113. If minnum >= maxnum Then Throw New Exception("min must be less than max")
    114. Me._maxnum = maxnum : Me._minnum = minnum
    115. End Sub
    116. End Class


    CS

    C#-Quellcode

    1. namespace XModGeneratorSolver
    2. {
    3. class Program
    4. {
    5. static void Main()
    6. {
    7. Solver solve = new Solver();
    8. Generator generator = new Generator(3000, int.MaxValue);
    9. int[] res = null;
    10. for (int i = 0; i <= 100000; i++)
    11. {
    12. res = generator.GenerateAandM();
    13. solve.Solve(res[0], res[1]);
    14. }
    15. Console.ReadKey();
    16. }
    17. }
    18. }
    19. public class Solver
    20. {
    21. public void Solve(int a, int m)
    22. {
    23. int[] eeax = EEA(a, m);
    24. int xx = eeax[1], x = xx;
    25. if ((a < 0) && (xx > 0)) x = ExtInv(xx, a, m);
    26. if ((a > 0) && (xx < 0)) x = ExtInv(xx, a, m);
    27. Console.WriteLine("[x = {0} | m = {1} | a = {2}]", x, m, a);
    28. Console.WriteLine("({0} * {1}) mod {2} = {3}", a, x, m, ((long)a * x) % m);
    29. Console.WriteLine(); Console.WriteLine();
    30. //if (((long)a * x) % m != 1) Debugger.Break();
    31. }
    32. private int ExtInv(int x, int a, int m)
    33. {
    34. int t = (int)((long)x + m) % m;
    35. if ((a < 0) && t > 0) return -t;
    36. if ((a > 0) && t < 0) return -t;
    37. return t;
    38. }
    39. private int[] EEA(int a, int b)
    40. {
    41. a = a > 0 ? a : -a;
    42. int aa = a, bb = b, m = b;
    43. List<int> q = new List<int>(30);
    44. int r = b;
    45. while (r > 0)
    46. {
    47. q.Add(a / b);
    48. r = a % b;
    49. a = b; b = r;
    50. }
    51. int rr = a;
    52. int ax = 1; int by = 0;
    53. for (int i = q.Count - 2; i >= 0; i--)
    54. {
    55. r = (int)(by - (q[i] * (long)ax));
    56. by = ax; ax = r;
    57. }
    58. long check = (long)ax * aa + (long)by * bb;
    59. if ((check != 1) || (check != -1))
    60. {
    61. int t = ax;
    62. ax = by; by = t;
    63. }
    64. check = (long)ax * aa + (long)by * bb;
    65. return new int[] { rr, ax, by };
    66. }
    67. private int GCD(int i1, int i2)
    68. {
    69. return i2 == 0 ? i1 : this.GCD(i2, i1 % i2);
    70. }
    71. }
    72. public class Generator
    73. {
    74. private readonly int _maxnum;
    75. private readonly int _minnum;
    76. private Random _random = new Random();
    77. public Generator(int minnum, int maxnum)
    78. {
    79. if (minnum >= maxnum) throw new Exception("min must be less than max");
    80. this._maxnum = maxnum; this._minnum = minnum;
    81. }
    82. public int[] GenerateAandM()
    83. {
    84. int x = this._maxnum;
    85. int m = this.FindM(x);
    86. int a = this.ExtInv(this.EEA(x, m)[1], x, m);
    87. //if (GCD(a, m) != 1) Debugger.Break();
    88. Console.WriteLine("[x = {0} | m = {1} | a = {2}]", x, m, a);
    89. Console.WriteLine("({0} * {1}) mod {2} = {3}", a, x, m, ((long)a * x) % m);
    90. Console.WriteLine();
    91. //if (((long)a * (long)x) % m != 1) Debugger.Break();
    92. return new int[] { a, m };
    93. }
    94. private int ExtInv(int a, int x, int m)
    95. {
    96. int t = (int)(((long)a + (long)m) % (long)m);
    97. if ((x < 0) && (t > 0)) return -t;
    98. if ((x > 0) && (t < 0)) return -t;
    99. return t;
    100. }
    101. private int FindM(int x)
    102. {
    103. int m;
    104. do
    105. {
    106. m = this._random.Next(this._minnum, this._maxnum);
    107. }
    108. while (this.GCD(m, x) != 1);
    109. return m;
    110. }
    111. private int[] EEA(int a, int b)
    112. {
    113. a = a > 0 ? a : -a;
    114. int aa = a, bb = b, m = b;
    115. List<int> q = new List<int>(30);
    116. int r = b;
    117. while (r > 0)
    118. {
    119. q.Add(a / b);
    120. r = a % b;
    121. a = b; b = r;
    122. }
    123. int rr = a, ax = 1, by = 0;
    124. for (int i = q.Count - 2; i >= 0; i--)
    125. {
    126. r = (int)(by - ((long)q[i] * ax));
    127. by = ax; ax = r;
    128. }
    129. long check = (long)ax * aa + (long)by * bb;
    130. if ((check != 1) || (check != -1))
    131. {
    132. int t = ax; ax = by; by = t;
    133. }
    134. //check = ax * aa + by * bb;
    135. return new int[] { rr, ax, by };
    136. }
    137. private int GCD(int i1, int i2)
    138. {
    139. return i2 == 0 ? i1 : this.GCD(i2, i1 % i2);
    140. }
    141. }


    Freundliche Grüsse

    exc-jdbi

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