费马素性测试的实施

我尝试使用BigIntegers在Java中实现Fermat's primality test。我的实现如下，但不幸的是它不起作用。有任何想法吗？

public static boolean checkPrime(BigInteger n, int maxIterations) 
{ 
    if (n.equals(BigInteger.ONE)) 
     return false; 

    BigInteger a; 
    Random rand = new Random(); 

    for (int i = 0; i < maxIterations; i++) 
    { 
     a = new BigInteger(n.bitLength() - 1, rand); 
     a = a.modPow(n.subtract(BigInteger.ONE), n); 

     if (!a.equals(BigInteger.ONE)) 
      return false; 
    } 

    return true; 
}

我是BigIntegers的新手。

谢谢！

来源

2010-10-26 Donald Taylor

如果您明确说明“不起作用”的样子，那么运气会更好。 – duffymo 2010-10-26 19:24:10

“不行”我的意思是它没有给出正确的结果。例如，当我对诸如2,3,5和7等素数进行测试时，它会返回“false”，并返回“true”。 – 2010-10-26 19:30:04

你是否检查过a = new BigInteger（n.bitLength（） - 1，rand）;打印时确实是一个正常值，并且rand从1正确初始化为n（我没有看到那部分）？ – extraneon 2010-10-26 19:30:29

您对特定BigInteger构造函数的使用是合理的，但您应该使用rejection method来选择一个fermat基底a。以下是对类中的一个轻微修改，该类也只使用一个Random对象：

import java.math.BigInteger; 
import java.util.Random; 

public class FermatTestExample 
{ 

    private final static Random rand = new Random(); 

    private static BigInteger getRandomFermatBase(BigInteger n) 
    { 
     // Rejection method: ask for a random integer but reject it if it isn't 
     // in the acceptable set. 

     while (true) 
     { 
      final BigInteger a = new BigInteger (n.bitLength(), rand); 
      // must have 1 <= a < n 
      if (BigInteger.ONE.compareTo(a) <= 0 && a.compareTo(n) < 0) 
      { 
       return a; 
      } 
     } 
    } 

    public static boolean checkPrime(BigInteger n, int maxIterations) 
    { 
     if (n.equals(BigInteger.ONE)) 
      return false; 

     for (int i = 0; i < maxIterations; i++) 
     { 
      BigInteger a = getRandomFermatBase(n); 
      a = a.modPow(n.subtract(BigInteger.ONE), n); 

      if (!a.equals(BigInteger.ONE)) 
       return false; 
     } 

     return true; 
    } 

    public static void main(String[] args) 
    { 
     System.out.printf("checkprime(2) is %b%n", checkPrime(BigInteger.valueOf(2L), 20)); 
     System.out.printf("checkprime(5) is %b%n", checkPrime(BigInteger.valueOf(5L), 20)); 
     System.out.printf("checkprime(7) is %b%n", checkPrime(BigInteger.valueOf(7L), 20)); 
     System.out.printf("checkprime(9) is %b%n", checkPrime(BigInteger.valueOf(9L), 20)); 
    } 
}

来源

2010-10-26 20:48:01

一个应该是“选择一个随机范围（1，N - 1]”我实在不明白发生这种情况你可以打印一张以检查

至于如何做到这一点。：

BigInteger a = BigInteger.valueOf(random.nextInt(n-2)+2);

例如，你不应该用随机参数使用的BigInteger构造，这只是一个随机源，但一个应该是一个随机值

的“岭。 ndom.nextInt（n-1）+1'来自nextInt的定义，给定参数k，它返回一个随机值0直到并包括k-1。并且你想要a大于1且小于n。

来源

2010-10-26 19:31:43 extraneon

好点 - 我认为这是问题所在。但是，如何将范围应用于Java中的Random对象？ – 2010-10-26 19:40:31

@ DT3增加了一些代码。 – extraneon 2010-10-26 20:00:35

@ DT3您可以在简单明了的问题中获得最多的答案。很多人都有答案，并阅读你的答案。 – extraneon 2010-10-26 20:07:37

费马素性测试的实施

回答

相关问题