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 } }