algorithm - 拉宾米勒算法

Question

我想了解 Rabin Miller 算法，但我对其中的一小部分感到困惑。请帮助理解它。

我的理解:我们在 2^d*s 中计算 's'，然后我们取一个随机整数 'a' 并计算 a^s%p，如果它等于 1，则 p 是可能的素数。否则，如果对于任何 'r' a^(r*s)%p = -1 那么我们将在下一次平方中得到 1，因此 p 是素数。在第一次迭代中，如果 x=1；然后我们在 if 语句中检查它，但是在第一次迭代之后 if 语句的意义是什么，我不明白。请帮助...

令人困惑的部分:

if(mod!=p-1 && temp%2==0){
                return false;
            }

原始米勒实现:

bool Miller(long long p,int iteration){
    if(p<2){
        return false;
    }
    if(p!=2 && p%2==0){
        return false;
    }
    long long s=p-1;
    while(s%2==0){
        s/=2;
    }
    for(int i=0;i<iteration;i++){
        long long a=rand()%(p-1)+1,temp=s;
        long long mod=modulo(a,temp,p);
        while(temp!=p-1 && mod!=1 && mod!=p-1){
            mod=mulmod(mod,mod,p);
            temp *= 2;
        }
        if(mod!=p-1 && temp%2==0){
            return false;
        }
    }
    return true;
}

Answer 1

M-R witness 的定义是 a 使得 a**s != 1 (modulo p) 和 a**(2**r * s) != -1 (modulo p) 对于所有 r。当值为 a**(2**r * s) 的 mod 满足 mod == 1 (modulo p)< 时，循环退出 或 mod == -1(模 p)。

如果 mod == 1 (modulo p)，则满足作为 M-R witness 的第二个属性，因为 a**(2**r * s) 的每个值 到目前为止与 -1 (mod p) 不一致，并且 future 的值都不一致，因为它们都是 1 (mod p) .鉴于第二个属性成立，第一个属性 a**s != 1 (modulo p) 当且仅当循环体至少执行一次时才成立。最初，temp == s，最多为 (p - 1)/2，第二个 mod != p - 1属性(property)。当且仅当循环体至少执行一次时，我们才有 temp % 2 == 0。