将 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 = 1for 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 % nreturn 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计算。但在你的翻译中：U

U = (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 中，但这没有任何区别。）