c++ - 莱曼算法没有意义

Question

我尝试实施 Lehmann 测试，但它第一次不起作用。我按照每个人的描述

1. 计算 r = [ a^( (p -1) / 2) ] mod p
2. 如果 r 不是 1 或 –1，那么 p 肯定不是素数。
3. 如果 r = 1 或 –1，p 不是素数的可能性最多为 50%。

不管我怎么做，它永远不会奏效。我什至尝试过硬编码

p = 7; //definitely a prime number

double e = (p - 1 )/2;

int f = (int)pow(3, e) % p;

cout << f <<endl;

f 最终为 6

任何帮助将不胜感激

Answer 1

通过计算f，您已经完成了第 1 步，但您忽略了第 2 步和第 3 步。

p = 7; //definitely a prime number

double e = (p - 1 )/2;

int f = (int)pow(3, e) % p;

// Step 2
if(f % p != 1 && f % p != p - 1)
    cout << p << " is definitely not prime." << endl;
else // If not step 2, then step 3
    cout << p << " has 50% probability of being prime." << endl;

运算符%是 mod 运算符。它减少了左边的数字 mod 右边的数字。喜欢10 % 8是2。重要的是要注意，当左边的数字是正数时，结果总是正数。所以 if a = b - 1, a % bis a, 也就是说, if a = -1 mod b, then a % b == a。

英语的条件f % p != 1 && f % p != p - 1是(f % p not equal 1) AND (f % p not equal p - 1)

一个问题是这会溢出 big p。

如果您想避免使用 bignum 库，您可以像这样定义自己的 pow：

unsigned int my_pow(unsigned int base, unsigned int expon, unsigned int mod){
    unsigned int result = base;
    for(int i = 1;i < expon;i++)
        result = (result * base) % mod;
    return result
}

你会像这样使用它int f = pow(3, e, p);。我不确定当它溢出时如何绑定，但它会比正常的大很多pow。

Answer 2

f 最终为 6，因为 6 等于 -1 mod 7，希望它有所帮助。