Solovay–Strassen primality test in Scala
Solovay-Strassenの素数判定アルゴリズムをScalaで実装してみた．
Scalaでまともなプログラムを書いたのは初めてだったので苦労した
import java.math.BigInteger;
import java.util.Random;
import java.util.Scanner;
object SolovayStrassen {
def main(args: Array[String]):Unit = {
var sc = new Scanner(System.in)
var i = 0
while(sc.hasNextLine){
var s = System.currentTimeMillis()
var line = sc.nextLine()
if(!line.equals("")){
println(i+=1)
if(PrimeTest(new BigInt(new BigInteger(line)),1))println("probably prime, time:"+(System.currentTimeMillis()-s)+"ms")
else println("composite number"+(System.currentTimeMillis()-s)+"ms")
}
}
}
def PrimeTest(n:BigInt, k:Int):Boolean={
if(n<=1)return false
if(n==2)return true
if(n%2==0)return false
for(i <- (1 to k)){
var a = Rand(n)
var x = Jacobi(n,a))%n
if(x==0||(a.modPow((n-1)/2,n)-x!=0)return false
}
return true
}
def Jacobi(n:BigInt,a:BigInt):Int=J(n,a,1)
def J(n:BigInt,a:BigInt,c:Int):Int=if(n.gcd(a)!=1) 0
else if(n==1) c
else if(a==0) 0
else if(a==2){if(n%8==1||n%8==7) c else -c}
else if(a>=n) J(n,a%n,c)
else if(a*2>n) J(n,n-a,c*(if(n%4==1) 1 else -1))
else if(a%2==0) J(n,a/2,c*(if(n%8==1||n%8==7) 1 else -1))
else if(n%4==3&&a%4==3) J(a,n,-c)
else J(a,n,c)
var r = new Random(System.currentTimeMillis())
def Rand(n:BigInt):BigInt={
var p:BigInt = 0
while(p==0||p>=n)p = new BigInt(new BigInteger(n.bitLength,r))
return p
}
}
