import java.math.BigInteger;

public class Square_roots{
    public static void main(String args[]){
        //BigInteger p = new BigInteger("9887776666555554443322101223334567890098776665554887");
        //BigInteger q = new BigInteger("9887776666555554443322101223334567890098776665555559");
        BigInteger p       = new BigInteger("31");
        BigInteger q       = new BigInteger("167");
        BigInteger n       = p.multiply(q);
        //BigInteger c       = new BigInteger("19336090032491776169004164782266292979565869131353601147082739724731818240371345455590182356111961936550");
        BigInteger c       = new BigInteger("97");
        BigInteger one     = new BigInteger("1");
        BigInteger four    = new BigInteger("4");
        BigInteger m1, m2, r1, r2, r3, r4, sr1, sr2, sr3, sr4, exp, minus_c;

        exp = p.add(one).divide(four);
        r1 = c.modPow(exp, p);
        r2 = r1.negate().mod(p);

        exp = q.add(one).divide(four);
        r3 = c.modPow(exp, q);
        r4 = r3.negate().mod(q);

        m1 = q.modInverse(p);
        m2 = p.modInverse(q);

        System.out.println("c  = " + c.toString());
        System.out.println("p  = " + p.toString());
        System.out.println("q  = " + q.toString());
        System.out.println("n  = " + n.toString());
        System.out.println("m1 = " + m1.toString());
        System.out.println("m2 = " + m2.toString());
        System.out.println("r1 = " + r1.toString());
        System.out.println("r2 = " + r2.toString());
        System.out.println("r3 = " + r3.toString());
        System.out.println("r4 = " + r4.toString());

        sr1 = ((r1.multiply(m1).multiply(q)).add(r3.multiply(m2).multiply(p))).mod(n);
        sr2 = ((r1.multiply(m1).multiply(q)).add(r4.multiply(m2).multiply(p))).mod(n);
        sr3 = ((r2.multiply(m1).multiply(q)).add(r3.multiply(m2).multiply(p))).mod(n);
        sr4 = ((r2.multiply(m1).multiply(q)).add(r4.multiply(m2).multiply(p))).mod(n);

        System.out.println("Square roots of c mod n:");
        System.out.println(sr1.toString());
        System.out.println(sr2.toString());
        System.out.println(sr3.toString());
        System.out.println(sr4.toString());
    }
}