Lehmann素性检验

Question

我正在做雷曼的测试，下面的函数不能给出100%准确的输出。它说所有的p都是质数。我一直在搜索，算法似乎是正确的。请问问题出在哪里？

private static boolean lehmanTest(int p, int tries) {

        boolean isPrime = true;

        int a = randomGenerator();

        int e = (p - 1 )/2;
        int result = (a^e) % p;

        System.out.println ("Result: " + result);

        while (tries!=0)
        {
            if(result % p != 1 && result % p != p - 1)
            {
                a = randomGenerator();
                tries--;
            }
                else
                {
                    isPrime = false;
                }
        }
        return isPrime;

}

修改后的代码

private static boolean lehmanTest(int p, int tries) {

        //boolean isPrime = true;

        //generate random number a
        int a = randomGenerator(p);


        int e = (p - 1 )/2;
        int result = ((int)Math.pow(a,e)) % p;


        while (tries!=0)
        {
            result = ((int)Math.pow(a,e)) % p;


            if(result % p != p - 1)
            //if(result % p != 1 && result % p != p - 1)
            {
                a = randomGenerator(p);             
                tries--;
            }
                else
                {
                    return false;
                }
        }
        return true;

    }
private static int randomGenerator (int p) {        
        //generate random numbers a, n times        
        Random rand = new Random();

        int randomInt = rand.nextInt(p);
        return randomInt;       
    }

Answer 1

你的第一个问题就是下面这行：

    int result = (a^e) % p;

a^e是"a xor e“，而不是"a to the eth power”。您需要Math.pow(a，e)或类似的东西。您可能应该重新阅读算法的描述。

Answer 2

在你的算法中有三件事需要修正：

1. 将int result = (a^e) % p;更改为：int result = ((int)Math.pow(a,e))% p；
2. 以随机选择的一组数字的形式计算现在的数字(目前您只为一个随机生成的数字计算它，无论此条件是否正确：return false.

确保randomGenerator()返回小于p.

• Change randomGenerator()的isPrime=false：

我还没有检查实现这些点的代码，我认为我在第3点中描述的代码可能存在问题。