Java Modular Multiplicative Inverse

Question

モジュラ乗法逆MODを見つける方法がわかりません。私はすべてのWiki記事、ビデオを読んだり、クラスメートの助けを求めて解決策を見つけることさえできませんこの。私が見つけたものは、Javaに変換できないプログラミング言語であり、整数の代わりに倍精度を使うプログラミング言語です。私は教授の仕様ごとに整数しか使用できません。

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); 
    } 

} 

私はそれが整数の剰余数の逆数を返すようinverse()方法を記述しようとしています：ここで私はinverse()方法を見つけ出すまでdivide()方法を行うことはできません、私がこれまでに書かれているクラスであります（mod 5）。今のところ、コードを実行するときにエラーが消えるように、デフォルトのコンストラクタだけを返します。誰もが、倍精度型または他の型を持たない整数型のみを使用して、モジュラ乗法逆行列を見つける方法を説明しようとしますか？

逆数または単に数の逆数nは、 は表記のn ^（ - 1）、整数モジュロベースBに、されています。ここでの私の教授の説明があるが、私はそれを理解していません にnを乗じた数値が1に一致する数値。すなわち、n×n ^（ - 1）≡1（mod b）である。 の例では、（5×3）mod 7 = 15 mod 7≡1であるため5を法とする5 ^（-1）整数です。 数字0には逆もありません。すべての数値が可逆であるとは限りません。 例えば、2 ^（ - 1）の整数モジュロ4は、{0、 1 2、3}でない整数ので不定である任意の助けを理解されたい。1.

を得るために2で乗算することができ、感謝。

Answer 1

私はhttps://comeoncodeon.wordpress.com/2011/10/09/modular-multiplicative-inverse/からブルートフォースアルゴリズムをとりましたが、それはC++ですが、ほぼはJavaとしてコンパイルされます。だから、私の仕事の大部分はあなたのクラスに合うように調整していました。これは結果です：

/** 
* 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()); 
}