Hey,
Ich habe gerade versucht ModPow selbst zu implementieren, basierend auf den Erklärungen des Wikipedia Pseudocodes.
Allerdings hat er einen Bug bei einem großen Modulus, und ich bekomm nicht raus was der Fehler ist? Kann mir jemand helfen?
Mein Unit-Test:
Bei folgendem Datensatz wird ein falsches Ergbnis returned:
Wenn ich das mit BigInteger.ModPow teste, wird das richtige Ergebnis returned. Was ist bei meiner Implementation falsch?
Ich habe gerade versucht ModPow selbst zu implementieren, basierend auf den Erklärungen des Wikipedia Pseudocodes.
Allerdings hat er einen Bug bei einem großen Modulus, und ich bekomm nicht raus was der Fehler ist? Kann mir jemand helfen?
C#-Quellcode
- /// <summary>
- /// Modular exponentiation using right-to-left binary method
- /// </summary>
- /// <param name="basis">The base</param>
- /// <param name="exponent">The exponent</param>
- /// <returns>The power under the specified modulo</returns>
- public uint Pow(uint basis, uint exponent)
- {
- if (_modulo == 1)
- return 0;
- uint res = 1;
- basis %= _modulo;
- while (exponent > 0)
- {
- if ((exponent & 1) == 1)
- res = res * basis % _modulo;
- exponent >>= 1;
- basis = basis * basis % _modulo;
- }
- return res;
- }
Mein Unit-Test:
C#-Quellcode
- [Theory]
- [InlineData(2, 5, 3, 2)]
- [InlineData(7, 0, 4, 1)]
- [InlineData(uint.MaxValue, 1337, 420, 75)]
- [InlineData(1337, uint.MaxValue, 420, 413)]
- [InlineData(1337, 420, uint.MaxValue, 486672706)]
- [InlineData(uint.MaxValue, uint.MaxValue, 1337, 986)]
- public void FiniteFieldPowTest(uint a, uint b, uint m, uint expectedResult)
- {
- var finiteField = new FiniteFieldArithmetic(m);
- var result = finiteField.Pow(a, b);
- Assert.Equal(expectedResult, result);
- }
Bei folgendem Datensatz wird ein falsches Ergbnis returned:
[InlineData(1337, 420, uint.MaxValue, 486672706)]
Wenn ich das mit BigInteger.ModPow teste, wird das richtige Ergebnis returned. Was ist bei meiner Implementation falsch?
C# Developer
Learning C++
Learning C++