Kongruencje (Java)

Kongruencje (Java)

Podstawy teoretyczne kongruencji były omówione wcześniej. A oto zestaw klas Java pozwalających pracować z kongruencjami.

Klasy

Klasa Congruence

package congruence;

public final class Congruence {
    private final long a;
    private final long b;
    private final long m;

    public Congruence(long a, long b, long m) {
        if (((a - b) % m) == 0) {
            this.a = a;
            this.b = b;
            this.m = m;
        } else {
            throw new ArithmeticException("Dane nieprawidłowe");
        }
    }

    public long getA() {
        return a;
    }

    public long getB() {
        return b;
    }

    public long getM() {
        return m;
    }

    @Override
    public int hashCode() {
        return 3 * Long.valueOf(a).hashCode() + 5 * Long.valueOf(b).hashCode() + 7 * Long.valueOf(m).hashCode();
    }

    @Override
    public boolean equals(Object o) {
        if (o == null) {
            return false;
        }
        if (this.getClass() != o.getClass()) {
            return false;
        }
        Congruence other = (Congruence) o;
        return (this.a == other.getA()) && (this.b == other.getB()) && (this.m == other.getM());
    }

    @Override
    public String toString() {
        return a + "\u2261" + b + "(mod " + m + ")";
    }

    public static Congruence add(Congruence cong1, Congruence cong2) {
        if (cong1.getM() == cong2.getM()) {
            return new Congruence(Math.addExact(cong1.getA(), cong2.getA()), Math.addExact(cong1.getB(), cong2.getB()), cong1.getM());
        }
        return null;
    }

    public static Congruence sub(Congruence cong1, Congruence cong2) {
        if (cong1.getM() == cong2.getM()) {
            return new Congruence(Math.subtractExact(cong1.getA(), cong2.getA()), Math.subtractExact(cong1.getB(), cong2.getB()), cong1.getM());
        }
        return null;
    }

    public static Congruence mult(Congruence cong1, Congruence cong2) {
        if (cong1.getM() == cong2.getM()) {
            return new Congruence(Math.multiplyExact(cong1.getA(), cong2.getA()), Math.multiplyExact(cong1.getB(), cong2.getB()), cong1.getM());
        }
        return null;
    }

    public static Congruence mult(Congruence cong, long num) {
        return new Congruence(Math.multiplyExact(cong.getA(), num), Math.multiplyExact(cong.getB(), num), cong.getM());
    }

    public static Congruence pow(Congruence cong, int exp) {
        return new Congruence(ModUtil.powExact(cong.getA(), Math.abs(exp)), ModUtil.powExact(cong.getB(), Math.abs(exp)), cong.getM());
    }

    public static Congruence div(Congruence kong, long num) {
        long a = kong.getA();
        long b = kong.getB();
        long m = kong.getM();
        if ((a % num == 0) && (b % num == 0) && (m % num == 0)) {
            return new Congruence(a / num, b / num, m / num);
        } else {
            throw new ArithmeticException("'Dane nieprawidłowe");
        }
    }
}

Klasa ModUtil

package congruence;

public class ModUtil {
    private ModUtil() {
    }

    /**
     * Zwraca resztę z dzielenia w znaczeniu kongruencji.
     * Różni się od % tym, że:
     * 1) nie przyjmuje ujemnego modulusa
     * 2) jeśli dzielna jest ujemna, a więc i reszta % jest ujemna zwraca resztę %
     * powiększona o modulus.
     * -10 % 3 = -1
     * mod(-10, 3) = -1 + 3 = 2
     *
     * @param dzielna - dzielna
     * @param modulus - dzielnik
     * @return - zwraca resztę z dzielenia w znaczeniu kongruencji
     */
    public static long mod(long dzielna, long modulus) {
        if (modulus <= 0) {
            throw new ArithmeticException("Nieprawidłowy argument");
        }
        long i = dzielna % modulus;
        if (i < 0) {
            i = (modulus + i);
        }
        return i;
    }

    public static long modAdd(long a, long b, long modulus) {
        return mod(Math.addExact(a, b), modulus);
    }
    public static long modSub(long a, long b, long modulus) {
        return mod(Math.subtractExact(a, b), modulus);
    }
    public static long modMult(long a, long b, long modulus) {
        return mod(Math.multiplyExact(a, b), modulus);
    }
    public static long powExact(long a, long exp) {
        if (exp < 0) {
            throw new ArithmeticException("Wykładnik mniejszy od 0");
        }
        long w = 1L;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                w = Math.multiplyExact(w, Math.multiplyExact(w, a));
            } else {
                w = Math.multiplyExact(w, w);
            }
            exp >>= 1;
        }
        return w;
    }

    public static long modPow(long a, long exp, long modulus) {
        return mod(powExact(a, exp), modulus);
    }
}

Klasa CongruenceTestAdd

package congruence;

public class CongruenceTestAdd {
    public static void main(String[] args) {
        Congruence k1 = new Congruence(12, 7, 5);
        Congruence k2 = new Congruence(27, 42, 5);
        System.out.println(Congruence.add(k1, k2));
    }
}

Po uruchomieniu na konsoli zobaczymy:

39≡49(mod 5)

Klasa CongruenceTestSubtract

package congruence;

public class CongruenceTestSubtract {
    public static void main(String[] args) {
        Congruence k3 = new Congruence(15, 6, 9);
        Congruence k4 = new Congruence(12, 21, 9);
        System.out.println(Congruence.sub(k3, k4));
    }
}

Po uruchomieniu na konsoli zobaczymy:

3≡-15(mod 9)

Klasa CongruenceTestMult

package congruence;

public class CongruenceTestMult {
    public static void main(String[] args) {
        Congruence k5 = new Congruence(15, 8, 7);
        Congruence k6 = new Congruence(3, 10, 7);
        System.out.println(Congruence.mult(k5, k6));
        //-
        Congruence k7 = new Congruence(5, 2, 3);
        long num1 = 3;
        System.out.println(Congruence.mult(k7, num1));
    }
}

Po uruchomieniu na konsoli zobaczymy:

45≡80(mod 7)
15≡6(mod 3)

Klasa CongruenceTestPow

package congruence;

public class CongruenceTestPow {
    public static void main(String[] args) {

        Congruence k8 = new Congruence(5, 2, 3);
        System.out.println(k8);
        int exp2 = 3;
        System.out.println(Congruence.pow(k8, exp2));
    }
}

Po uruchomieniu na konsoli zobaczymy:

5≡2(mod 3)
125≡8(mod 3)

Klasa CongruenceTestDiv

package congruence;

public class CongruenceTestDiv {
    public static void main(String[] args) {

        Congruence k9 = new Congruence(15, 6, 9);
        int num2 = 3;
        System.out.println(Congruence.div(k9, 3));
    }
}

Po uruchomieniu na konsoli zobaczymy:

5≡2(mod 3)

2019-07-20 10:55:40