Sollovay-Strassen algoritmus (test ci je cislo zlozene)
Created: 2012-01-09 - 15:24
import java.math.BigInteger;
import java.util.Random;
public class SollovayStrassen {
/**
* Solovay-Strassen algoritmus.
*
* Vracia TRUE (accept) ak n je zlozene cislo
* Vracia FALSE (reject) ak nevie
* rozhodnut
*
* @param n
* @return
*/
public static boolean test(BigInteger n, int iteration) {
if (n.intValue() < 3) {
System.err.println("Vstup je mensi ako 3.");
return true;
}
if (n.mod(new BigInteger("2")).equals(BigInteger.ZERO)) {
System.err.println("Vstup je parne cislo.");
return true;
}
for(int i = 0; i < iteration; i++) {
Random r = new Random();
BigInteger a = BigInteger.ZERO;
while(a.equals(BigInteger.ZERO))
a = new BigInteger(String.valueOf((long) (r.nextInt(n.intValue()-1))));
BigInteger gcd = a.gcd(n);
// System.out.println("a = " + a);
// System.out.println("gcd(a,n) = " + gcd);
if (!gcd.equals(BigInteger.ONE))
return true;
BigInteger jac_a_n = Jacobi(a, n);
// System.out.println("Jac[a,n] = " + jac_a_n);
BigInteger test = a.modPow(n, n.subtract(BigInteger.ONE).divide(new BigInteger("2")));
// System.out.println("Test = "+test);
if (jac_a_n.equals(test))
return false;
}
return true;
}
public static BigInteger Jacobi(BigInteger a, BigInteger n) {
if (a.equals(BigInteger.ONE))
return BigInteger.ONE;
if (a.equals(new BigInteger("2")) && (n.mod(new BigInteger("8")).equals(new BigInteger("3")) || n.mod(new BigInteger("8")).equals(new BigInteger("5"))))
return new BigInteger("-1");
if (a.equals(new BigInteger("2")) && (n.mod(new BigInteger("8")).equals(new BigInteger("1")) || n.mod(new BigInteger("8")).equals(new BigInteger("7"))))
return BigInteger.ONE;
if (a.mod(new BigInteger("2")).equals(BigInteger.ZERO)) {
BigInteger first = Jacobi(new BigInteger("2"), n);
BigInteger c = a.divide(new BigInteger("2"));
BigInteger second = Jacobi(c , n);
BigInteger multiply = first.multiply(second);
return multiply;
}
if (a.compareTo(n) == 1) {
return Jacobi(a.mod(n), n);
} else {
BigInteger first = (new BigInteger("-1")).pow(((a.intValue() - 1) * (n.intValue() - 1)) / 4);
BigInteger second = Jacobi(n.mod(a), a);
BigInteger multiply = first.multiply(second);
return multiply;
}
}
public static void main(String[] args) {
System.out.println(test(new BigInteger("1123"),10000)); //je prvocislo
System.out.println(test(new BigInteger("1125"),10000)); //je zlozene cislo
}
}