Was macht diese Funktion.

  • C#
  • .NET (FX) 4.0

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

    Was macht diese Funktion.

    Hallo,

    Ich könnte mal ein wenig Erklärungs-Hilfe gebrauchen ^^.
    Ich versuche zu verstehe was diese Klasse, bzw die modInv()-Funktion genau macht und wie sie funktioniert.

    C#-Quellcode

    1. ​public static class MathsUtils {
    2. const ulong MODULO32 = 0x100000000;
    3. public static ulong modInv(ulong num, ulong mod) {
    4. ulong a = mod, b = num % mod;
    5. ulong p0 = 0, p1 = 1;
    6. while (b != 0) {
    7. if (b == 1) return p1;
    8. p0 += (a / b) * p1;
    9. a = a % b;
    10. if (a == 0) break;
    11. if (a == 1) return mod - p0;
    12. p1 += (b / a) * p0;
    13. b = b % a;
    14. }
    15. return 0;
    16. }
    17. public static uint modInv(uint num) {
    18. return (uint)modInv(num, MODULO32);
    19. }
    20. public static byte modInv(byte num) {
    21. return (byte)modInv(num, 0x100);
    22. }
    23. }


    Für diejenigen die es interessiert, diese Klasse stammt aus dem Open Source-Projekt ConfuserEx.
    Der Name würde mich auf "modInverse" oder "modInvoke" schließen lassen, - allerdings ist bei der Klasse keine weitere Dokumentation vorhanden.
    Was genau macht die Funktion und wie funktioniert sie?
    C# Developer
    Learning C++
    Ist das nicht der erweitere euklidische Algorithmus?

    Kenne ich aus RSA
    de.wikipedia.org/wiki/Prime_Restklassengruppe



    Sieht ziemlich danach aus.
    de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus
    Und Gott alleine weiß alles am allerbesten und besser.
    Hmm, scheint nicht so zu sein..
    Der erweiterte euklidische Algorithmus dient doch dazu den ggtT zu finden oder?
    Wenn ich bspw 12 und 15 als input gebe sollte demnach 3 rauskommen, tuts aber nicht.
    Folglich ist entweder die Funktion eine andere oder ich mach was falsch .s
    C# Developer
    Learning C++
    Eeeehhh...ich hab mal "modInv" gegoogelt: tutorialspoint.com/java/math/biginteger_modinverse.htm

    Hoff es hilft weiter
    Lg Radinator
    In general (across programming languages), a pointer is a number that represents a physical location in memory. A nullpointer is (almost always) one that points to 0, and is widely recognized as "not pointing to anything". Since systems have different amounts of supported memory, it doesn't always take the same number of bytes to hold that number, so we call a "native size integer" one that can hold a pointer on any particular system. - Sam Harwell
    Hallo Rikudo

    Es stellt sich wohl immer wieder die Frage was beschreibt den nun die ModInverse.

    Hier mal ne Erklärung.

    Definition:
    Eine Inverse besteht nur, wenn ggt(n,m) = 1 ist, was soviel heisst wie:

    Quellcode

    1. 'zu einer Multiplikation N, mit n*n^(-1) ist gleich kongruent 1 mod n.


    Und nur in diesem Falle 'funktioniert' der erweiterte Euklid, da beide natürlichen Zahlen n,m von ggt(n,m) relativ Prim sind, oder anders ausgedrückt,
    m ist teilfremd zu n.

    Ein Beispiel:


    Wie im Bild ersichtlich wird m mit dem einfachen Euklid zu m = 1.
    Das ermöglicht nun den erweiterten Euklid zu verwenden und daraus die folgende Gleichung abzuleiten. Wobei die Inverse zu m = 7 wie dargestellt y = 3 ist. Die Gleichung lautet:

    Quellcode

    1. 3 x 12 + -5 x 7

    Zur Gleichung y = 3 x 12 = 36 gibt es also eine Inverse, die es ermöglicht die 'ursprüngliche' Zahl abzuleiten.

    Hier der Beweis

    Quellcode

    1. z = eine Zahl von 1 bis (m-1) nehmen wird
    2. z = 6
    3. Berechnen
    4. (6 x n) mod m = 2.
    5. Und wieder zurück mit der Inverse
    6. (2 x y) mod m = 6
    7. was der ursrünglichen Zahl entspricht


    Das Ganze kann man noch intensiver betreiben, in dem man grosse Primzahlen verwendet. Darum wird es auch in der Cryptographie verwendet, obwohl so gar nicht als sicher gilt. Nur in der richtigen Kombination sollte es verwendet werden.

    Freundliche Grüsse

    exc-jdbi