Skip to content

Commit 21ef2ea

Browse files
BobHansonBobHanson
committed
BigInt.modPow fix for large int*int overflow
1 parent 3b6b3c9 commit 21ef2ea

File tree

6 files changed

+67
-11
lines changed

6 files changed

+67
-11
lines changed

‎sources/net.sf.j2s.java.core/dist/SwingJS-site.zip

-1.64 KB
Binary file not shown.

‎sources/net.sf.j2s.java.core/dist_to_jsmol/Jmol-j2s-site.zip

-28 Bytes
Binary file not shown.

‎sources/net.sf.j2s.java.core/src/java/math/BigInteger.java

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2754,7 +2754,8 @@ private static int[] montReduce(int[] n, int[] mod, int mlen, int inv) {
27542754

27552755
do {
27562756
int nEnd = n[n.length-1-offset];
2757-
int carry = mulAdd(n, mod, offset, mlen, inv * nEnd);
2757+
// BH JavaScript does not roll over int multiplication
2758+
int carry = mulAdd(n, mod, offset, mlen, (int)((long)inv * nEnd));
27582759
c += addOne(n, offset, mlen, carry);
27592760
offset++;
27602761
} while (--len > 0);

‎sources/net.sf.j2s.java.core/src/test/Test_BigInt.java

Lines changed: 31 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,7 @@
22
package test;
33

44
import java.math.BigInteger;
5+
import java.util.Arrays;
56

67
//import test.math.BigInteger;
78
//import test.math.MutableBigInteger;
@@ -10,13 +11,38 @@ public class Test_BigInt extends Test_ {
1011

1112
public static void main(String[] args) {
1213

14+
BigInteger n = new BigInteger("10473");
15+
BigInteger exp = new BigInteger("9261");
16+
BigInteger mod = new BigInteger("17947");
17+
BigInteger p = n.modPow(exp, mod);
18+
// System.out.println(p.toString()); // 815 but is 3908
19+
20+
int v = 0;
21+
// for 10473, 29
22+
// n = new BigInteger("14");
23+
// exp = new BigInteger("3");
24+
n = new BigInteger("10473");
25+
exp = new BigInteger("9261");
26+
// first failure is 2195, giving 197 in JS and 1658 in Java
27+
// also 2287, 2431, 2443, 2455, and several more
28+
for (int i = 1; i < 3000; i++) {
29+
mod = BigInteger.valueOf(i);
30+
p = n.modPow(exp, mod);
31+
v += p.intValue();
32+
System.out.println(i + "." + p.toString());// + "\t" + v);
33+
// System.out.println(Arrays.toString(p.toByteArray()));
34+
}
35+
System.out.println(v);
36+
if (true)
37+
return;
1338
// // working with full long support.
14-
15-
// three tweaks needed:
16-
39+
40+
// three tweaks needed:
41+
1742
// 1) MutableBigInteger.compare explicit int check (x)|0
18-
// 2) MutableBigInteger.inverseMod32 requires long rather than int for Newton's method
19-
// 1) BigInteger needs alias valueOf for toString;
43+
// 2) MutableBigInteger.inverseMod32 requires long rather than int for Newton's
44+
// method
45+
// 1) BigInteger needs alias valueOf for toString;
2046
testModPow();
2147
testShift();
2248
testSub();

‎sources/net.sf.j2s.java.core/src/test/Test_BigIntJava.java

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -13,6 +13,31 @@ public class Test_BigIntJava extends Test_ {
1313

1414
public static void main(String[] args) {
1515

16+
BigInteger n = new BigInteger("10473");
17+
BigInteger exp = new BigInteger("9261");
18+
BigInteger mod = new BigInteger("17947");
19+
BigInteger p = n.modPow(exp, mod);
20+
// System.out.println(p.toString()); // 815 but is 3908
21+
22+
int v = 0;
23+
// for 10473, 29
24+
n = new BigInteger("14");
25+
exp = new BigInteger("3");
26+
// n = new BigInteger("10473");
27+
// exp = new BigInteger("9261");
28+
// first failure is 2195, giving 197 in JS and 1658 in Java
29+
// also 2287, 2431, 2443, 2455, and several more
30+
for (int i = 2497; i < 2498; i++) {
31+
mod = BigInteger.valueOf(i);
32+
p = n.modPow(exp, mod);
33+
v += p.intValue();
34+
System.out.println(i + "." + p.toString());// + "\t" + v);
35+
// System.out.println(Arrays.toString(p.toByteArray()));
36+
}
37+
System.out.println(v);
38+
if (true)
39+
return;
40+
1641
System.out.println(inverseMod32(5));
1742

1843
// testMulOdd();

‎sources/net.sf.j2s.java.core/src/test/math/BigInteger.java

Lines changed: 9 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -2497,7 +2497,7 @@ public BigInteger modPow(BigInteger exponent, BigInteger m) {
24972497
// Combine results using Chinese Remainder Theorem
24982498
BigInteger y1 = m2.modInverse(m1);
24992499
BigInteger y2 = m1.modInverse(m2);
2500-
2500+
25012501
if (m.mag.length < MAX_MAG_LENGTH / 2) {
25022502
result = a1.multiply(m2).multiply(y1).add(a2.multiply(m1).multiply(y2)).mod(m);
25032503
} else {
@@ -2514,7 +2514,7 @@ public BigInteger modPow(BigInteger exponent, BigInteger m) {
25142514
return (invertResult ? result.modInverse(m) : result);
25152515
}
25162516

2517-
static int[] bnExpModThreshTable = {7, 25, 81, 241, 673, 1793,
2517+
static int[] bnExpModThreshTable = {7, 25, 81, 241, 673, 1793,
25182518
Integer.MAX_VALUE}; // Sentinel
25192519

25202520
/**
@@ -2633,6 +2633,8 @@ private BigInteger oddModPow(BigInteger y, BigInteger z) {
26332633
}
26342634

26352635
// Set b to the square of the base
2636+
2637+
26362638
int[] b = squareToLen(table[0], modLen, null);
26372639
b = montReduce(b, mod, modLen, inv);
26382640

@@ -2648,6 +2650,7 @@ private BigInteger oddModPow(BigInteger y, BigInteger z) {
26482650
// Pre load the window that slides over the exponent
26492651
int bitpos = 1 << ((ebits-1) & (32-1));
26502652

2653+
26512654
int buf = 0;
26522655
int elen = exp.length;
26532656
int eIndex = 0;
@@ -2686,11 +2689,12 @@ private BigInteger oddModPow(BigInteger y, BigInteger z) {
26862689
buf <<= 1;
26872690

26882691
if (elen != 0) {
2692+
26892693
buf |= ((exp[eIndex] & bitpos) != 0) ? 1 : 0;
26902694
bitpos >>>= 1;
26912695
if (bitpos == 0) {
26922696
eIndex++;
2693-
bitpos = 1 << (32-1);
2697+
bitpos = (1 << (32-1));
26942698
elen--;
26952699
}
26962700
}
@@ -2743,7 +2747,7 @@ private BigInteger oddModPow(BigInteger y, BigInteger z) {
27432747
return new BigInteger(1, t2);
27442748
}
27452749

2746-
/**
2750+
/**
27472751
* Montgomery reduce n, modulo mod. This reduces modulo mod and divides
27482752
* by 2^(32*mlen). Adapted from Colin Plumb's C library.
27492753
*/
@@ -2754,7 +2758,7 @@ private static int[] montReduce(int[] n, int[] mod, int mlen, int inv) {
27542758

27552759
do {
27562760
int nEnd = n[n.length-1-offset];
2757-
int carry = mulAdd(n, mod, offset, mlen, inv * nEnd);
2761+
int carry = mulAdd(n, mod, offset, mlen, (int)((long)inv * nEnd));
27582762
c += addOne(n, offset, mlen, carry);
27592763
offset++;
27602764
} while (--len > 0);

0 commit comments

Comments
 (0)