我試圖取回正確的指數，當我插入示例數字（exampleA、exampleB、exampleP）時該程式有效，因為它們回傳它們應該回傳的值，但是當我插入長數字（A、B、p )，回圈繼續。我相信插入 B 和 p 時我應該得到 2099。我在這里做錯了什么？
public static void main(String[] args) {
//g = 5//
//let i run from 0 to p -1//
//compute g^a mod p and see if it is A, if you find A, then a is the solution for A//
//compute g^a mod p and see if it is B, if you find B, then a is the solution for B//
long A = 1958258942L;
long B = 670001116L;
long p = 3267000013L;
//example p to plug in for example a and example b//
long exampleP = 23;
//plugging this in should return 4//
long exampleA = 4;
//plugging this in should return 3//
long exampleB = 10;
int newNum;
int a = 0;
int g = 5;
for (int i = 0; i < (p - 1); i ) {
a = i;
System.out.println(a);
newNum = powMod(g, a, exampleP);
if (newNum == exampleB) break;
}
System.out.println(a);
}
public static int powMod(int g, int exponent, long p) {
int result = 1;
while (exponent > 0)
{
// exponent is odd
if (exponent % 2 == 1)
{
result = (int) ((result * g) % p);
}
// divide exponent in half
exponent /= 2;
// square base and take remainder
g = (int) ((g * g) % p);
}
return result;
}
uj5u.com熱心網友回復：
p相當高。大約30億。
一個int只到20億多一點，永遠達不到30億。
在for (int i = 0; i < (p - 1); i )中，i是一個int，所以i絕對不會大于 2147483647，i永遠達不到p - 130 億左右。i在此之前將變為負數，并開始從零開始計數，從零開始，直到剛好超過 20 億，然后仍然永遠不會達到 30 億。所以回圈條件總是為真，回圈永遠不會結束。
簡單的解決方案：制作i一個long.
中也有錯誤powMod，產品（不僅僅是余數）必須按照longs 完成，否則它們可以在減少模數之前包裝模 2 32 （并且產品作為 an可以是負數，這與 Java 中的余數結合得不好使用負輸入）。例如應該是（見下文進一步修改）pint(int) ((g * g) % p)(int) (((long)g * g) % p)
modPow接受一個int作為指數，但是如果回圈被固定為實際從 0 回圈到p - 1那么指數也需要是一個long。或者，它可以保持為int，但隨后需要將其視為無符號整數，這將對代碼進行更多更改。
最高的中間產品（減少模數之前的產品p）可能是 32670000122（產品的兩個運算元p - 1最多）。這不適合 63 位，因此long它可能是負數，這意味著您需要Long.remainderUnsigned?而不是%運算子。該產品確實適合 64 位，因此仍然不需要BigInteger.
所以使用類似的東西Long.remainderUnsigned?((long)g * g, p)
在這種情況下，您可以完全避免powMod，而不是modPow(g, i, p)在每次迭代中從頭開始計算，而是通過將先前的值乘以g(mod p) 來計算。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/536575.html
標籤：爪哇for循环取模模组
上一篇：IntielliJ使用檔案夾“${project.build.directory}”而不是“target”作為Maven構建/運行目標