読者です 読者をやめる 読者になる 読者になる

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


しかし,BigIntの計算がとても遅いので困る.
Haskellの10倍,C++ with GMPの50倍遅かった