Modular Exponentiation Bug

  • C#
  • .NET (FX) 4.5–4.8

Es gibt 1 Antwort in diesem Thema. Der letzte Beitrag () ist von RodFromGermany.

    Modular Exponentiation Bug

    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?

    C#-Quellcode

    1. /// <summary>
    2. /// Modular exponentiation using right-to-left binary method
    3. /// </summary>
    4. /// <param name="basis">The base</param>
    5. /// <param name="exponent">The exponent</param>
    6. /// <returns>The power under the specified modulo</returns>
    7. public uint Pow(uint basis, uint exponent)
    8. {
    9. if (_modulo == 1)
    10. return 0;
    11. uint res = 1;
    12. basis %= _modulo;
    13. while (exponent > 0)
    14. {
    15. if ((exponent & 1) == 1)
    16. res = res * basis % _modulo;
    17. exponent >>= 1;
    18. basis = basis * basis % _modulo;
    19. }
    20. return res;
    21. }


    Mein Unit-Test:

    C#-Quellcode

    1. [Theory]
    2. [InlineData(2, 5, 3, 2)]
    3. [InlineData(7, 0, 4, 1)]
    4. [InlineData(uint.MaxValue, 1337, 420, 75)]
    5. [InlineData(1337, uint.MaxValue, 420, 413)]
    6. [InlineData(1337, 420, uint.MaxValue, 486672706)]
    7. [InlineData(uint.MaxValue, uint.MaxValue, 1337, 986)]
    8. public void FiniteFieldPowTest(uint a, uint b, uint m, uint expectedResult)
    9. {
    10. var finiteField = new FiniteFieldArithmetic(m);
    11. var result = finiteField.Pow(a, b);
    12. Assert.Equal(expectedResult, result);
    13. }


    Bei folgendem Datensatz wird ein falsches Ergbnis returned:
    [InlineData(1337, 420, uint.MaxValue, 486672706)]

    Quellcode

    1. Expected: 486672706
    2. Actual: 3079646561



    Wenn ich das mit BigInteger.ModPow teste, wird das richtige Ergebnis returned. Was ist bei meiner Implementation falsch?
    C# Developer
    Learning C++
    @Rikudo Welchen Wert hat _modulo?
    Wenn Du Deine Werte um Unit-Test in eine CSV-Datei packst, kannst Du die Liste erweitern, ohne das Projekt compilieren zu müssen.
    ====
    OK, _modulo ist der dritte Wert.
    Du arbeitest an der Grenze Deines Datentyps uint.
    Mach mal die Rechnung (nicht den Input) mit ulong und schon redet die Nachbarin mit Dir. :D
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

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