Dieser Beitrag wurde bereits 7 mal editiert, zuletzt von „exc-jdbi“ ()
Fermats Theorem - Modulo Inverse fuer gegebenes X
- C#
- .NET (FX) 1.0–2.0
Sie verwenden einen veralteten Browser (%browser%) mit Sicherheitsschwachstellen und können nicht alle Funktionen dieser Webseite nutzen.
Hier erfahren Sie, wie einfach Sie Ihren Browser aktualisieren können.
Hier erfahren Sie, wie einfach Sie Ihren Browser aktualisieren können.
Es gibt 29 Antworten in diesem Thema. Der letzte Beitrag () ist von exc-jdbi.
-
-
Und So sieht das programmiert aus.
VB VB.NET-Quellcode
- Option Strict On
- Option Explicit On
- Imports System.Numerics
- Public Module Module1
- Public Sub Main()
- Dim x1 = XModSolve(5, 2, 11)
- Dim x2 = XModSolve(101, 15, 89)
- Dim x3 = XModSolve(123456, 15, 89)
- Dim x4 = XModSolve(123456789, 15, 89)
- Dim xx1 = XModSolve(5, 2, 11, 1000)
- Dim xx2 = XModSolve(101, 15, 89, 1000)
- Dim xx3 = XModSolve(123456, 15, 89, 1000)
- Dim xx4a = XModSolve(123456789, 15, 89, 1000)
- Stop
- End Sub
- Private Function XModSolve(ByVal a As Int32, ByVal r As Int32, ByVal m As Int32) As Int32
- If GetGCD(a, m) = 1 Then
- Dim t = (m - a) Mod m, tt = t * m - r
- Dim inc As Int32 = -1, x As Int32 = -1
- While Not x = 0
- inc += 1
- x = (tt - m * inc) Mod t
- End While
- Return (tt - m * inc) \ t
- End If
- Return -1
- End Function
- Private Function XModSolve(ByVal a As Int32, _
- ByVal r As Int32, _
- ByVal m As Int32, _
- ByVal xmax As Int32) As Int32()
- If GetGCD(a, m) = 1 Then
- Dim res As New List(Of Int32)
- Dim inc As Int32 = -1, aa As Int64 = a mod m
- While inc <= xmax
- inc += 1
- If (aa * inc) Mod m = r Then
- res.Add(inc)
- End If
- End While
- Return res.ToArray
- End If
- Return Nothing
- End Function
- Private Function GetGCD(ByVal i1 As Int32, ByVal i2 As Int32) As Int32
- Return If(i2 = 0, i1, GetGCD(i2, i1 Mod i2))
- End Function
- End Module
CS C#-Quellcode
- using System;
- using System.Linq;
- using System.Text;
- using System.Diagnostics;
- using System.Collections.Generic;
- namespace XModSolver
- {
- class Program
- {
- static void Main()
- {
- int x1 = XModSolve(5, 2, 11);
- int x2 = XModSolve(101, 15, 89);
- int x3 = XModSolve(123456, 15, 89);
- int x4 = XModSolve(123456789, 15, 89);
- int[] xx1 = XModSolve(5, 2, 11, 1000);
- int[] xx2 = XModSolve(101, 15, 89, 1000);
- int[] xx3 = XModSolve(123456, 15, 89, 1000);
- int[] xx4 = XModSolve(123456789, 15, 89, 1000);
- Debugger.Break();
- }
- private static int XModSolve(int a, int r, int m)
- {
- if (GetGCD(a, m) == 1)
- {
- int inc = -1, x = -1;
- int t = (m - a) % m, tt = t * m - r;
- while (x != 0)
- {
- inc += 1;
- x = (tt - m * inc) % t;
- }
- return (tt - m * inc) / t;
- }
- return -1;
- }
- private static int[] XModSolve(int a, int r, int m, int xmax)
- {
- if (GetGCD(a, m) == 1)
- {
- int inc = -1; long aa = a % m;
- List<int> res = new List<int>();
- while (inc <= xmax)
- {
- inc += 1;
- if ((aa * inc) % m == r)
- res.Add(inc);
- }
- return res.ToArray();
- }
- return null;
- }
- private static int GetGCD(int i1, int i2)
- {
- return i2 == 0 ? i1 : GetGCD(i2, i1 % i2);
- }
- }
- }
Freundliche Grüsse
exc-jdbi
Dieser Beitrag wurde bereits 5 mal editiert, zuletzt von „exc-jdbi“ ()
-
@exc-jdbi Danke für deine ausführliche Antwort. Ich verstehe nicht was der zweite Parameter von XModSolve bedeutet, kannst du das nochmal erklären?C# Developer
Learning C++
-
Hallo @Rikudo
Die Gleichung:ax ≡ r mod m
es gilt ggT(a,m) = 1
Die Parameter vonx = XModSolve(a,r,m)
sind genau so zugeordnet.
a
steht für den Koeffizienten vonx
,r
für den Restwert (der aus Modulo entstanden ist) undm
ist der Modulowert.
Beim der zweiten XModSolve-Funktion, bei der ein Array zurückgegeben wird, kommt noch am Schluss dasSorry falsch.kmax
hinzu. Es bezieht sich auf den maximalen Incrementwert, also hier 1000. D.H. die Funktion nutzt alsk
die Werte 0 - 1000.
In der zweiten XModSolve-Funktion, bei der ein Array zurückgegeben wird, kommt noch am Schluss daskmax
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 derkmax
der maximale Incrementwert fürx
. Es wird also für x die Werte 0 - 1000 eingesetzt. Habe es oben im Codee umgeändert kmax zuxmax
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.
ist laut Wolfram Alpha genau
Deine Funktion kommt aber gar nicht zum ende (habe nach ein paar Minuten abgebrochen)
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
- public class Generator
- {
- private readonly int _number;
- private static readonly Random _random = new Random();
- public Generator(int number)
- {
- _number = number;
- }
- public int[] GenerateAandM()
- {
- int m = FindM(_number);
- int a = ExtendedEuclideanAlgorithm(_number, m)[1];
- Console.WriteLine($"[x = {_number} | m = {m} | a = {a}]");
- Console.WriteLine($"{a}*x ≡ 1 (mod {m}) | {_number}");
- return new[] {a, m};
- }
- private static int GreatesCommonDivisor(int a, int b)
- {
- if (b == 0)
- return a;
- return GreatesCommonDivisor(b, a % b);
- }
- static int[] ExtendedEuclideanAlgorithm(int a, int b)
- {
- int s = 0, t = 1, u = 1, v = 0;
- while (a != 0)
- {
- int q = b / a | 0, r = b % a;
- int m = s - u * q, n = t - v * q;
- b = a;
- a = r;
- s = u;
- t = v;
- u = m;
- v = n;
- }
- return new[] {b, s, t};
- }
- private static int FindM(int x)
- {
- int m = 0;
- do
- {
- m = _random.Next(3000, int.MaxValue);
- } while (GreatesCommonDivisor(m, x) != 1);
- return m;
- }
- }[b]
Solver.cs
C#-Quellcode
- public class Solver
- {
- private readonly int _a;
- private readonly int _m;
- public Solver(int a, int m)
- {
- _a = a;
- _m = m;
- }
- public void Solve()
- {
- Console.WriteLine(ModInverse(_a, _m));
- }
- static int Mod(int n, int m)
- {
- return (n % m + m) % m;
- }
- static int ModInverse(int z, int n)
- {
- var result = ExtendedEuclideanAlgorithm(z, n);
- if (result[0] != 1)
- throw new Exception("GCD must be 1");
- return Mod(result[1], n);
- }
- static int[] ExtendedEuclideanAlgorithm(int a, int b)
- {
- int s = 0, t = 1, u = 1, v = 0;
- while (a != 0)
- {
- int q = b / a | 0, r = b % a;
- int m = s - u * q, n = t - v * q;
- b = a;
- a = r;
- s = u;
- t = v;
- u = m;
- v = n;
- }
- return new[] {b, s, t};
- }
- }
Testing:
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:
Gebe ich diese Werte in meinem Solver an, erhalte ich genau
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:
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 Wert111222333
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
- Richtig:
- [x = 111111111 | m = 1920041414 | a = 48813355]
- 48813355*x ≡ 1 (mod 1920041414) | 111111111
- [x = 222222222 | m = 1883323625 | a = 880426558]
- 880426558*x ≡ 1 (mod 1883323625) | 222222222
- [x = 333333333 | m = 1470422987 | a = -131482446]
- -131482446*x ≡ 1 (mod 1470422987) | 333333333
- [x = 444444444 | m = 2100474613 | a = 786023953]
- 786023953*x ≡ 1 (mod 2100474613) | 444444444
- [x = 555555555 | m = 1383048137 | a = 252785280]
- 252785280*x ≡ 1 (mod 1383048137) | 555555555
- [x = 666666666 | m = 1224606413 | a = -120539455]
- -120539455*x ≡ 1 (mod 1224606413) | 666666666
- Falsch:
- [x = 777777777 | m = 754469410 | a = -188801767]
- -188801767*x ≡ 1 (mod 754469410) | 777777777
- [x = 888888888 | m = 601511051 | a = -277152805]
- -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 wennr mod ggT(a,m) = 0
VB VB.NET-Quellcode
- Option Strict On
- Option Explicit On
- Imports System.Numerics
- Public Module Module1
- Dim rand As New Random
- Public Sub Main()
- Test()
- End Sub
- Private Sub Test()
- Dim m, x, g, r As Int32
- For a As Int32 = -10000000 To 10000000
- If (a > -2) AndAlso (a < 2) Then Continue For
- Do
- m = rand.Next(5, 1000)
- Loop While Not GetGCD(a, m) = 1
- r = rand.Next(m)
- x = XModSolve(a, r, m)
- g = CheckMod(a, x, m)
- If Not g = r Then Stop
- Next
- End Sub
- Private Function XModSolve(ByVal a As Int32, ByVal m As Int32) As Int32
- If a = m Then Return 1
- Dim gcd = GetGCD(a, m)
- If gcd > 1 Then
- a = If(a = gcd, a, a \ gcd)
- m = If(m = gcd, m, m \ gcd)
- gcd = GetGCD(a, m)
- Return If(gcd > 1, gcd, m)
- End If
- Return m
- End Function
- Private Function XModSolve(ByVal a As Int32, ByVal r As Int32, ByVal m As Int32) As Int32
- If (r > 0) AndAlso (m > r) Then
- Dim gcd = GetGCD(a, m)
- If r Mod gcd = 0 Then
- gcd = Math.Abs(gcd)
- a \= gcd : r \= gcd : m \= gcd
- Dim sign = If(a > 0, True, False)
- a = If(a > 0, a, -a)
- Dim x = r * ExtInv(EEA(a, m)(1), m)
- If sign AndAlso x < 0 Then Return -x
- If Not sign AndAlso x > 0 Then Return -x
- Return x
- End If
- Throw New Exception("GCD must be divisor of r")
- End If
- If r = 0 Then Return XModSolve(a, m)
- Return 0
- End Function
- Private Function ExtInv(ByVal i1 As Int32, ByVal m As Int32) As Int32
- i1 = i1 Mod m
- Return CInt((CLng(i1) + m) Mod m)
- End Function
- Private Function EEA(ByVal a As Int32, ByVal b As Int32) As Int32()
- a = If(a > 0, a, -a)
- Dim q As New List(Of Int32)(30)
- Dim aa As Int32 = a, bb As Int32 = b, r As Int32 = b
- While r > 0
- q.Add(a \ b)
- r = a Mod b
- a = b : b = r
- End While
- Dim rr As Int32 = a, ax = 1I, by = 0I
- For i As Int32 = q.Count - 2 To 0 Step -1
- r = CInt(by - (q(i) * CLng(ax)))
- by = ax : ax = r
- Next
- Dim check As Int64 = CLng(ax) * aa + CLng(by) * bb
- If (Not check = 1) OrElse (Not check = -1) Then
- Dim t As Int32 = ax
- ax = by : by = t
- End If
- Return New Int32() {rr, ax, by}
- End Function
- Private Function CheckMod(ByVal a As Int32, ByVal x As Int32, ByVal m As Int32) As Int32
- Dim aa = New BigInteger(a), xx = New BigInteger(x)
- Return CInt((aa * xx) Mod m)
- End Function
- Private Function GetGCD(ByVal i1 As Int32, ByVal i2 As Int32) As Int32
- Return If(i2 = 0, i1, GetGCD(i2, i1 Mod i2))
- End Function
- End Module
CS C#-Quellcode
- using System;
- using System.Linq;
- using System.Text;
- using System.Numerics;
- using System.Diagnostics;
- using System.Collections.Generic;
- namespace CSModGleichungLösen
- {
- class Program
- {
- static Random rand = new Random();
- static void Main(string[] args)
- {
- Test();
- }
- private static void Test()
- {
- int m, x, g, r;
- for (int a = -10000000; a <= 10000000; a++)
- {
- if ((a > -2) && (a < 2)) continue;
- do {
- m = rand.Next(5, 1000);
- } while (GetGCD(a, m) != 1);
- r = rand.Next(m);
- x = XModSolve(a, r, m);
- g = CheckMod(a, x, m);
- if (g != r) Debugger.Break();
- }
- }
- private static int XModSolve(int a, int m)
- {
- if (a == m) return 1;
- int gcd = GetGCD(a, m);
- if (gcd > 1)
- {
- a = (a == gcd) ? a : a / gcd;
- m = (m == gcd) ? m : m / gcd;
- gcd = GetGCD(a, m);
- return gcd > 1 ? gcd : m;
- }
- return m;
- }
- private static int XModSolve(int a, int r, int m)
- {
- if ((r > 0) && (m > r))
- {
- int gcd = GetGCD(a, m);
- if (r % gcd == 0)
- {
- gcd = Math.Abs(gcd);
- a /= gcd; r /= gcd; m /= gcd;
- var sign = a > 0 ? true : false;
- a = a > 0 ? a : -a;
- int x = r * ExtInv(EEA(a, m)[1], m);
- if (sign && x < 0) return -x;
- if (!sign && x > 0) return -x;
- return x;
- }
- throw new Exception("GCD must be divisor of r");
- }
- if (r == 0) return XModSolve(a, m);
- return 0;
- }
- private static int[] EEA(int a, int b)
- {
- a = a > 0 ? a : -a;
- int aa = a, bb = b;
- List<int> q = new List<int>(30);
- int r = b;
- while (r > 0)
- {
- q.Add(a / b);
- r = a % b;
- a = b; b = r;
- }
- int rr = a; int ax = 1;int by = 0;
- for (int i = q.Count - 2; i >= 0; i--)
- {
- r = (int)(by - (q[i] * (long)ax));
- by = ax; ax = r;
- }
- long check = ((long)ax * (long)aa) + ((long)by * (long)bb);
- if ((check != 1) || (check != -1))
- {
- int t = ax;
- ax = by; by = t;
- }
- return new int[] { rr, ax, by };
- }
- private static int ExtInv(int i1, int m)
- {
- i1 = i1 % m;
- return (int)(((long)i1 + (long)m) % (long)m);
- }
- private static int CheckMod(int a, int x, int m)
- {
- long aa = a, xx = x, mm = m;
- return (int)((aa * xx) % mm);
- }
- private static int GetGCD(int i1, int i2)
- {
- return i2 == 0 ? i1 : GetGCD(i2, i1 % i2);
- }
- }
- }
Testlauf VB.NET-Quellcode
- Private Sub Test()
- Dim m, x, g, r As Int32
- For a As Int32 = -10000000 To 10000000
- If (a > -2) AndAlso (a < 2) Then Continue For
- r = rand.Next(5, 1000)
- Do
- m = rand.Next(r + 1, 2000)
- Loop While Not (r Mod GetGCD(a, m) = 0)
- x = XModSolve(a, r, m)
- g = CheckMod(a, x, m)
- If Not g = r Then Stop
- Next
- End Sub
Testlauf 1 mod m VB.NET-Quellcode
- Private Sub Test()
- Dim m, x, g, r As Int32
- For a As Int32 = -10000000 To 10000000
- If (a > -2) AndAlso (a < 2) Then Continue For
- r = 1 ' rand.Next(5, 1000)
- Do
- m = rand.Next(r + 1, 2000)
- Loop While Not (r Mod GetGCD(a, m) = 0)
- x = XModSolve(a, r, m)
- g = CheckMod(a, x, m)
- If Not g = r Then Stop
- Next
- End Sub
Testlauf Random VB.NET-Quellcode
- Private Sub Test()
- 'Zum suchen von m gilt 'r mod ggT(a,m) = 0'
- 'Zufälliges a und r. Daraus dann m suchen.
- Dim m, x, g, r, a, p As Int32
- Dim cnt As Int32 = 10000000
- Dim inc As Int32 = -10000000
- Dim wurz = CInt(Math.Sqrt(Int32.MaxValue))
- While inc < cnt
- inc += 1
- a = rand.Next(Int32.MinValue, Int32.MaxValue)
- If (a > -2) AndAlso (a < 2) Then Continue While
- 'Bedingung
- 'm * r < Int32.MaxValue, r > 0, m > r
- r = rand.Next(1, wurz - 20)
- p = Int32.MaxValue \ r
- Do
- m = rand.Next(r + 1, p)
- Loop While Not (r Mod GetGCD(a, m) = 0)
- x = XModSolve(a, r, m)
- g = CheckMod(a, x, m)
- If Not g = r Then Stop
- End While
- 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
einen entsprechenden Wert generiert. Ob das jetzt beim Solver oder beim Generator entstanden ist, muss ich genauer anscheuen.
Freundliche Grüsse
exc-jdbiDieser 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
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 FunktionMod()
beim Solver
Bei mir lauft es richtig.
VB VB.NET-Quellcode
- Option Strict On
- Option Explicit On
- Public Module Module1
- Public Sub Main()
- Dim solve As New Solver()
- Dim generator As New Generator(3000, Int32.MaxValue)
- Dim res() As Int32
- For i As Int32 = 0 To 100000
- res = generator.GenerateAandM()
- solve.Solve(res(0), res(1))
- Next
- Console.ReadKey()
- End Sub
- End Module
- Public Class Solver
- Public Sub Solve(ByVal a As Int32, ByVal m As Int32)
- Dim eeax = EEA(a, m)
- Dim xx = eeax(1), x As Int32 = xx
- 'If xx < 0 Then Stop
- If (a < 0) AndAlso (xx > 0) Then x = ExtInv(xx, a, m)
- If (a > 0) AndAlso (xx < 0) Then x = ExtInv(xx, a, m)
- Console.WriteLine("[x = {0} | m = {1} | a = {2}]", x, m, a)
- Console.WriteLine("({0} * {1}) mod {2} = {3}", a, x, m, (CLng(a) * x) Mod m)
- Console.WriteLine() : Console.WriteLine()
- 'If Not (CLng(a) * x) Mod m = 1 Then Stop
- End Sub
- Private Function ExtInv(ByVal x As Int32, ByVal a As Int32, ByVal m As Int32) As Int32
- Dim t = CInt((CLng(x) + m) Mod m)
- If (a < 0) AndAlso t > 0 Then Return -t
- If (a > 0) AndAlso t < 0 Then Return -t
- Return t
- End Function
- Private Function EEA(ByVal a As Int32, ByVal b As Int32) As Int32()
- a = If(a > 0, a, -a)
- Dim aa As Int32 = a, bb As Int32 = b, m As Int32 = b
- Dim q As New List(Of Int32)(30), r As Int32 = b
- While r > 0
- q.Add(a \ b)
- r = a Mod b
- a = b : b = r
- End While
- Dim rr As Int32 = a, ax = 1I, by = 0
- For i As Int32 = q.Count - 2 To 0 Step -1
- r = CInt(by - (q(i) * CLng(ax)))
- by = ax : ax = r
- Next
- Dim check As Int64 = CLng(ax) * aa + CLng(by) * bb
- If (Not check = 1) OrElse (Not check = -1) Then
- Dim t As Int32 = ax
- ax = by : by = t
- End If
- check = CLng(ax) * aa + CLng(by) * bb
- Return New Int32() {rr, ax, by}
- End Function
- Private Function GCD(ByVal i1 As Int32, ByVal i2 As Int32) As Int32
- Return If(i2 = 0, i1, Me.GCD(i2, i1 Mod i2))
- End Function
- End Class
- Public Class Generator
- Private _random As New Random
- Private ReadOnly _maxnum As Int32
- Private ReadOnly _minnum As Int32
- Public Function GenerateAandM() As Int32()
- Dim x = Me._maxnum
- Dim m = Me.FindM(x)
- Dim a = ExtInv(EEA(x, m)(1), x, m)
- 'If Not GCD(a, m) = 1 Then Stop
- Console.WriteLine("[x = {0} | m = {1} | a = {2}]", x, m, a)
- Console.WriteLine("({0} * {1}) mod {2} = {3}", a, x, m, (CLng(a) * x) Mod m)
- Console.WriteLine()
- 'If Not (CLng(a) * x) Mod m = 1 Then Stop
- Return New Int32() {a, m}
- End Function
- Private Function ExtInv(ByVal a As Int32, ByVal x As Int32, ByVal m As Int32) As Int32
- Dim t = CInt((CLng(a) + m) Mod m)
- If (x < 0) AndAlso t > 0 Then Return -t
- If (x > 0) AndAlso t < 0 Then Return -t
- Return t
- End Function
- Private Function FindM(ByVal x As Int32) As Int32
- Dim m As Int32
- Do
- m = Me._random.Next(Me._minnum, Me._maxnum)
- Loop While Not Me.GCD(m, x) = 1
- Return m
- End Function
- Private Function EEA(ByVal a As Int32, ByVal b As Int32) As Int32()
- a = If(a > 0, a, -a)
- Dim aa As Int32 = a, bb As Int32 = b, m As Int32 = b
- Dim q As New List(Of Int32)(30), r As Int32 = b
- While r > 0
- q.Add(a \ b)
- r = a Mod b
- a = b : b = r
- End While
- Dim rr As Int32 = a, ax = 1I, by = 0
- For i As Int32 = q.Count - 2 To 0 Step -1
- r = CInt(by - (q(i) * CLng(ax)))
- by = ax : ax = r
- Next
- Dim check As Int64 = CLng(ax) * aa + CLng(by) * bb
- If (Not check = 1) OrElse (Not check = -1) Then
- Dim t As Int32 = ax
- ax = by : by = t
- End If
- 'check = ax * aa + by * bb;
- Return New Int32() {rr, ax, by}
- End Function
- Private Function GCD(ByVal i1 As Int32, ByVal i2 As Int32) As Int32
- Return If(i2 = 0, i1, Me.GCD(i2, i1 Mod i2))
- End Function
- Public Sub New(ByVal minnum As Int32, ByVal maxnum As Int32)
- If minnum >= maxnum Then Throw New Exception("min must be less than max")
- Me._maxnum = maxnum : Me._minnum = minnum
- End Sub
- End Class
CS C#-Quellcode
- namespace XModGeneratorSolver
- {
- class Program
- {
- static void Main()
- {
- Solver solve = new Solver();
- Generator generator = new Generator(3000, int.MaxValue);
- int[] res = null;
- for (int i = 0; i <= 100000; i++)
- {
- res = generator.GenerateAandM();
- solve.Solve(res[0], res[1]);
- }
- Console.ReadKey();
- }
- }
- }
- public class Solver
- {
- public void Solve(int a, int m)
- {
- int[] eeax = EEA(a, m);
- int xx = eeax[1], x = xx;
- if ((a < 0) && (xx > 0)) x = ExtInv(xx, a, m);
- if ((a > 0) && (xx < 0)) x = ExtInv(xx, a, m);
- Console.WriteLine("[x = {0} | m = {1} | a = {2}]", x, m, a);
- Console.WriteLine("({0} * {1}) mod {2} = {3}", a, x, m, ((long)a * x) % m);
- Console.WriteLine(); Console.WriteLine();
- //if (((long)a * x) % m != 1) Debugger.Break();
- }
- private int ExtInv(int x, int a, int m)
- {
- int t = (int)((long)x + m) % m;
- if ((a < 0) && t > 0) return -t;
- if ((a > 0) && t < 0) return -t;
- return t;
- }
- private int[] EEA(int a, int b)
- {
- a = a > 0 ? a : -a;
- int aa = a, bb = b, m = b;
- List<int> q = new List<int>(30);
- int r = b;
- while (r > 0)
- {
- q.Add(a / b);
- r = a % b;
- a = b; b = r;
- }
- int rr = a;
- int ax = 1; int by = 0;
- for (int i = q.Count - 2; i >= 0; i--)
- {
- r = (int)(by - (q[i] * (long)ax));
- by = ax; ax = r;
- }
- long check = (long)ax * aa + (long)by * bb;
- if ((check != 1) || (check != -1))
- {
- int t = ax;
- ax = by; by = t;
- }
- check = (long)ax * aa + (long)by * bb;
- return new int[] { rr, ax, by };
- }
- private int GCD(int i1, int i2)
- {
- return i2 == 0 ? i1 : this.GCD(i2, i1 % i2);
- }
- }
- public class Generator
- {
- private readonly int _maxnum;
- private readonly int _minnum;
- private Random _random = new Random();
- public Generator(int minnum, int maxnum)
- {
- if (minnum >= maxnum) throw new Exception("min must be less than max");
- this._maxnum = maxnum; this._minnum = minnum;
- }
- public int[] GenerateAandM()
- {
- int x = this._maxnum;
- int m = this.FindM(x);
- int a = this.ExtInv(this.EEA(x, m)[1], x, m);
- //if (GCD(a, m) != 1) Debugger.Break();
- Console.WriteLine("[x = {0} | m = {1} | a = {2}]", x, m, a);
- Console.WriteLine("({0} * {1}) mod {2} = {3}", a, x, m, ((long)a * x) % m);
- Console.WriteLine();
- //if (((long)a * (long)x) % m != 1) Debugger.Break();
- return new int[] { a, m };
- }
- private int ExtInv(int a, int x, int m)
- {
- int t = (int)(((long)a + (long)m) % (long)m);
- if ((x < 0) && (t > 0)) return -t;
- if ((x > 0) && (t < 0)) return -t;
- return t;
- }
- private int FindM(int x)
- {
- int m;
- do
- {
- m = this._random.Next(this._minnum, this._maxnum);
- }
- while (this.GCD(m, x) != 1);
- return m;
- }
- private int[] EEA(int a, int b)
- {
- a = a > 0 ? a : -a;
- int aa = a, bb = b, m = b;
- List<int> q = new List<int>(30);
- int r = b;
- while (r > 0)
- {
- q.Add(a / b);
- r = a % b;
- a = b; b = r;
- }
- int rr = a, ax = 1, by = 0;
- for (int i = q.Count - 2; i >= 0; i--)
- {
- r = (int)(by - ((long)q[i] * ax));
- by = ax; ax = r;
- }
- long check = (long)ax * aa + (long)by * bb;
- if ((check != 1) || (check != -1))
- {
- int t = ax; ax = by; by = t;
- }
- //check = ax * aa + by * bb;
- return new int[] { rr, ax, by };
- }
- private int GCD(int i1, int i2)
- {
- return i2 == 0 ? i1 : this.GCD(i2, i1 % i2);
- }
- }
Freundliche Grüsse
exc-jdbi
Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von „exc-jdbi“ ()
-
Benutzer online 1
1 Besucher
-
Ähnliche Themen