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

Question

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

这是该测试的一部分（此 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};

}

有人可以帮帮我吗？这是整个 Python 脚本的可运行版本，如果有人感兴趣的话。这是我的整个 Java 翻译的粘贴箱。

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

Answer 1

我可以看到发生偏差的一个地方是您对这一行的翻译，以及三个类似的翻译：U, V = (P*U + V + n) >> 1, (D*U + P*V + n) >> 1这些是Python中的并行赋值，即使用语句之前的旧值V计算。但在你的翻译中：UU = (P*U + V + n) >> 1;V = (D*U + P*V + n) >> 1;V正在使用 的新值进行计算U。更好的翻译可能是：long old_U = U;U = (P*U + V + n) >> 1;V = (D*old_U + P*V + n) >> 1;同样，这也需要为其他并行分配完成。

Answer 2

如果您观察到循环重复使用P * U + VandD * U + P * V值，则有改进的余地。您根本不需要oldU接受的答案中提到的变量。只需在循环开始时计算这两个，稍后将它们用于条件和新值的U计算V。您在两个方面都获胜：使用单独的值将确保分配不再并行，并且您可以节省一些不必要的重新计算：if (k.testBit(i)) {  val PU_V = P * U + V  val DU_PV = D * U + P * V  if (IsEven(PU_V)) {    if (IsEven(DU_PV)) {      U = PU_V shr 1      V = DU_PV shr 1    }    else {      U = PU_V shr 1      V = (DU_PV + n) shr 1    }  }  else if (IsEven(DU_PV)) {    U = (PU_V + n) shr 1    V = DU_PV shr 1  }  else {    U = (PU_V + n) shr 1    V = (DU_PV + n) shr 1  }  subscript++  U %= n  V %= n}（这恰好是在 Kotlin 而不是 Java 中，但这没有任何区别。）