我正在嘗試將 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實現，我可以使用它！
2 回答
慕俠2389804
TA貢獻1719條經驗 獲得超6個贊
我可以看到發生偏差的一個地方是您對這一行的翻譯，以及三個類似的翻譯：
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;
同樣，這也需要為其他并行分配完成。
嗶嗶one
TA貢獻1854條經驗 獲得超8個贊
如果您觀察到循環重復使用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 中，但這沒有任何區別。）
添加回答
舉報
0/150
提交
取消