Java Modulare Multiplikative Inverse

Question

Ich kann nicht für das Leben von mir herausfinden, wie man den modularen multiplikativen inversen Mod 5 findet. Ich habe alle Wiki-Artikel gelesen, Videos angeschaut und sogar Hilfe von Klassenkameraden gesucht und kann keine Lösung finden Dies. Alles, was ich gefunden habe, ist entweder in einer anderen Programmiersprache, in der ich nicht in Java übersetzen kann (neu in der Programmierung) und/oder Doppel statt Ganzzahlen verwendet, die ich nur ganze Zahlen nach meinen Professorangaben verwenden kann. Hier ist die Klasse, die ich bisher geschrieben haben, können die divide() Methode nicht tun, bis ich die inverse() Methode herauszufinden:

public class ModInt { 

    /** 
    * the integer modulo base 
    */ 
    private int base; 

    /** 
    * the number 
    */ 
    private int number; 

    /** 
    * creates the modulo 2 number 0 
    */ 
    public ModInt() 
    { 
     base = 2; 
     number = 0; 
    } 

    /** 
    * creates a modulo b number n 
    * @param n the number 
    * @param b the base 
    */ 
    public ModInt(int n, int b) 
    { 
     number = n; 
     base = b; 
    } 

    /** 
    * creates an equivalent number in the same integer modulo base as the specified integer modulo number. 
    * @param m an integer modulo number 
    */ 
    public ModInt(ModInt m) 
    { 
     number = m.number; 
     base = m.base; 
    } 

    /** 
    * gives the number of the integer modulo number. 
    * @return the number 
    */ 
    public int getNumber() 
    { 
     return number; 
    } 

    /** 
    * gives the base of the specified integer modulo number. 
    * @return the base 
    */ 
    public int getBase() 
    { 
     return base; 
    } 

    /** 
    * modifies the integer modulo number using the specified parameters 
    * @param n the new number 
    * @param b the new base 
    */ 
    public void setModInt(int n, int b) 
    { 
     number = n; 
     base = b; 
    } 

    /** 
    * adds this integer modulo number and the specified integer modulo number 
    * @param m an integer modulo number 
    * @return the sum of this number and the specified number 
    */ 
    public ModInt add(ModInt m) 
    { 
     return new ModInt((number + m.number) % base, base);  
    } 

    /** 
    * subtracts this integer modulo number and the specified integer modulo number 
    * @param m an integer modulo number 
    * @return the difference this number and the specified number 
    */ 
    public ModInt subtract(ModInt m) 
    { 
     return new ModInt(((base - number + m.number) % base, base); 
    } 

    /** 
    * multiplies this integer modulo number and the specified integer modulo number 
    * @param m an integer modulo number 
    * @return the product of this number and the specified number 
    */ 
    public ModInt multiply(ModInt m) 
    { 
     return new ModInt((number * m.number) % base, base); 
    }  

    /** 
    * computes the inverse of this integer modulo number 
    * @return the inverse of this number 
    */ 
    public ModInt inverse() 
    { 
     return new ModInt(); 
    } 

    /** 
    * divides this integer modulo number and the specified integer modulo number 
    * @param m an integer modulo number 
    * @return the quotient of this number and the specified number 
    */ 
    public ModInt divide(ModInt m) 
    { 
     return new ModInt(); 
    }  

    /** 
    * give the string representation of an integer modulo number in the format 
    * n(mod b), where n is the number and b is the base 
    * @return a string representation of the integer modulo number in the format 
    * n(mod b); for example 3(mod 5) is the representation of the number 
    * 3 in integer modulo base 5 
    */ 
    public String toString() 
    { 
     return String.format("%d(mod %d)", number, base); 
    } 

} 

Ich versuche, die inverse() Methode zu schreiben, so dass es die Umkehrung der ganzen Zahl Modulo Zahl zurückgibt (mod 5). Für jetzt habe ich es nur den Standardkonstruktor zurückgeben, also würde der Fehler weggehen, wenn er den Code laufen lässt. Kann jemand versuchen, zu erklären, wie man die modulare multiplikative Umkehrung findet, die NUR ganzzahlige Typen, keine Doppelten oder irgendwelche anderen Typen verwendet? Hier ist mein Professor ist Erklärung dafür, aber ich verstehe es nicht:

multiplikativ invers oder einfach die Inverse einer Zahl n, bezeichnet n^(- 1), in integer Modulo Basis b ist eine Zahl, die, wenn multipliziert mit n kongruent zu 1 ist; das heißt, n × n^(- 1) 1 (mod b). Für Beispiel ist 5^(- 1) ganzzahlig modulo 7 ist 3, da (5 × 3) mod 7 = 15 mod 7 ≡ 1. Die Zahl 0 hat keine inverse. Nicht jede Zahl ist invertierbar. Für Beispiel 2^(- 1) Ganzzahl modulo 4 in da keine ganze Zahl unbestimmt ist {0, 1, 2, 3} können mit 2 multipliziert werden, um zu erhalten, 1.

Jede Hilfe geschätzt wird, dank .

Answer 1

Ich nahm den Brute-Force-Algorithmus von https://comeoncodeon.wordpress.com/2011/10/09/modular-multiplicative-inverse/, es ist in C++ aber fast kompiliert als Java. Die meiste meiner Arbeit war es, sie so anzupassen, dass sie in Ihre Klasse passt. Dies ist das Ergebnis:

/** 
* computes the inverse of this integer modulo number 
* 
* @return the inverse of this number 
*/ 
public ModInt inverse() { 
    int a = number % base; 
    for (int x = 1; x < base; x++) { 
     if ((a * x) % base == 1) { 
      return new ModInt(x, base); 
     } 
    } 
    throw new ArithmeticException("No inverse of " + toString()); 
}