模幂运算

    public static int modPowerShow(int a, int k, int n){
        System.out.println("*************************************************************************");
        System.out.println("****NOTICE:[\"\\\" area should be replaced by blank so there is nothing]****");
        System.out.println("****NOTICE:[\"(3=))\" area should be replaced by three line equal]*********");
        System.out.println("*************************************************************************");
        System.out.println("i\t\tki\t\tx\t\ty");
        int now, x = 1, y = a, power;
        for(int i = 0;;i++){
            now = k % 2;
            System.out.print(i + "\t\t" + now + "\t\t");
            power = (x * y) % n;
            if(now == 1) {
                System.out.print(x + "x" + y + "(3=)" + power + "\t\t");
                x = power;
            }
            else System.out.print(x + "\t\t");
            y = (y * y) % n;
            System.out.println(a + "^(2^" + (i+1) + ")" + "(3=)" + y);
            k /= 2;
            if(k == 1)break;
        }
        power = (x * y) % n;
        System.out.println("\\\t\t\\\t\t" + x + "x" + y + "(3=)" + power);
        return power;
    }

模逆运算

    public static int modInverseShow(int d, int n){
        System.out.println("*************************************************************************");
        System.out.println("****NOTICE:[\"\\\" area should be replaced by blank so there is nothing]****");
        System.out.println("*************************************************************************");
        int up = n;
        int down = d;
        int inverseUp = 0;
        int inverse = 1;
        int times, temp;
        System.out.println("\\\t\tu\t\tv\t\tq");
        System.out.println(up + "\t\t1\t\t0\t\t\\");
        System.out.print(down + "\t\t0\t\t1\t\t");
        for(;;) {
            times = up / down;
            System.out.println(times);
            temp = up - down * times;
            up = down;
            down = temp;
            temp = inverseUp - inverse * times;
            inverseUp = inverse;
            inverse = temp;
            System.out.print(down + "\t\t\\\t\t" + inverse + "\t\t");
            if(down == 1)return (inverse > 0) ? inverse : (inverse + n);
            if(down <= 0)return -1;
        }
    }

注意：如果返回值为-1，可能出现意外情况（两数不互素等原因），请自行验算

【Java】正数模幂运算、模逆运算方法（有步骤）

原文：https://www.cnblogs.com/blueflameashe/p/13168387.html