莱曼算法没有意义

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.重要的是要注意,当左数是正数时,结果总是正数.因此,如果a = b - 1,a % b是a,那就是说,如果a = -1 mod b,那么a % b == a.

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

一个问题是,这将溢出为大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.