java - 将 Baillie–PSW 测试从 Python 转换为 Java

Question

我正在尝试将 Baillie–PSW 素性测试的实现从 Python 转换为 Java。我认为我做得基本上是正确的，但是有一部分答案开始出现偏差，因此整个算法无法检测到任何素数。当算法开始使用卢卡斯素性测试时，这种偏差就开始出现。

这是该测试部分的原始代码( this repo 的一部分):

def U_V_subscript(k, n, U, V, P, Q, D):
k, n, U, V, P, Q, D = map(int, (k, n, U, V, P, Q, D))
digits = list(map(int, str(bin(k))[2:]))
subscript = 1

for digit in digits[1:]:

    U, V = U*V % n, (pow(V, 2, n) - 2*pow(Q, subscript, n)) % n

    subscript *= 2
    if digit == 1:

        if not (P*U + V) & 1:
            if not (D*U + P*V) & 1:

                U, V = (P*U + V) >> 1, (D*U + P*V) >> 1
            else:
                U, V = (P*U + V) >> 1, (D*U + P*V + n) >> 1
        elif not (D*U + P*V) & 1:
            U, V = (P*U + V + n) >> 1, (D*U + P*V) >> 1
        else:
            U, V = (P*U + V + n) >> 1, (D*U + P*V + n) >> 1
        subscript += 1
        U, V = U % n, V % n

return U, V

这是我的 Java 对应部分:

static long[] UVSubscript(long k, long n, long U, long V, long P, long Q, long D){
    BitSet bitDigits = convert(k);
    long subscript = 1;
    for (int i = bitDigits.length()-2; i >= 0; i--) {
        U = U*V % n;
        V = (powerModulus(V, 2, n) - 2*powerModulus(Q, subscript, n)) % n;

        subscript *= 2; 

        if (bitDigits.get(i)){


            if (((P * U + V) & 1) == 0){
                if (((D*U + P*V) & 1) == 0){

                     U = (P*U + V) >> 1;
                     V = (D*U + P*V) >> 1;
                }else{
                     U = (P*U + V) >> 1;
                     V = (D*U + P*V + n) >> 1;
                }
            } else if (((D * U + P * V) & 1) == 0){
                U = (P*U + V + n) >> 1;
                V = (D*U + P*V) >> 1;
            }else{
                U = (P*U + V + n) >> 1;
                V = (D*U + P*V + n) >> 1;
            }

            subscript += 1;
            U = U % n;
            V = V % n; 

        }
    }
    return new long[]{U, V};
}

有人可以帮我吗？这是a runnable version of the whole Python script ，如果有人有兴趣的话。这是 a pastebin of my whole Java translation .

PS 如果有人知道 Baillie-PSW 素性测试的现成 Java 实现，我可以使用它!

Answer 1

我可以看到发生偏差的一个地方是您对这一行的翻译，以及三个类似的翻译:

U, V = (P*U + V + n) >> 1, (D*U + P*V + n) >> 1

这些是 Python 中的并行赋值，即 V 正在使用 U 的旧值进行计算从声明之前开始。但在你的翻译中:

U = (P*U + V + n) >> 1;
V = (D*U + P*V + n) >> 1;

使用 U 的新值计算V。更好的翻译可能是这样的:

long old_U = U;
U = (P*U + V + n) >> 1;
V = (D*old_U + P*V + n) >> 1;

同样，其他并行作业也需要这样做。