Math.pow() returning same result with different inputs

Question

I have two empty arrays and some variables:

static int p = 41;
static int q = 67;
static int d = 83;
static int n = p * q;

static int[] encryptedBlocks = new int[charArray.length];
static int[] decryptedArray = new int[charArray.length];

the first of which is filled with the following (I've checked, and it is):

The second array I'm attempting to fill with the results of an equation in a for loop:

for (int i = 0; i < encryptedBlocks.length; i++) {
            int M = (int)Math.pow(encryptedBlocks[i], d) % n;
            decryptedArray[i] = M;
        }

Problem is I get the same result for M for each iteration.. I'm totally clueless as to what is going on:

Just in case I've double checked encryptedBlocks[i] is indeed the next value each iteration, and it is. Am I missing something in relation to using int and Math.pow()?

First two iteration values for encryptedBlocks[i], d and n:

1573 83 2747 
1978 83 2747

Looks like something might be overflowing, hence the constant result. — MikaelF, Mar 27 '17 at 00:29
Show us sample values of `encryptedBlocks[i]`, `d`, and `n`. — DYZ, Mar 27 '17 at 00:31
You may have to change this `int M = (int)Math.pow(encryptedBlocks[i], d) % n;` with this `int M = (int)(Math.pow(encryptedBlocks[i], d) % n);` — Kh.Taheri, Mar 27 '17 at 00:35
Ah, overflow makes sense thanks guys. @OusmaneMahyDiaw how about using long instead? — notAChance, Mar 27 '17 at 00:37
@xeon48 sure but i think KH.Taheri has just solved your problem — Ousmane D., Mar 27 '17 at 00:38
I guess you better implement modpow to prevent overflowing. Something like https://www.tutorialspoint.com/java/math/biginteger_modpow.htm — justhalf, Mar 27 '17 at 00:39
@OusmaneMahyDiaw he did indeed, thank you very much Kh.Taheri. — notAChance, Mar 27 '17 at 00:41

score 2 · Answer 1 · answered Mar 27 '17 at 00:38

In your line of code

int M = (int)Math.pow(encryptedBlocks[i], d) % n;

You are calculating Math.pow(encryptedBlocks[i], d), then casting it to an int, then using modulo m on the int result. What you probably wanted to do was only cast to int after all the math was done:

int M = (int) (Math.pow(encryptedBlocks[i], d) % n);

which yields:

1147 2564 1457 2351 2414 982 1073 2480 923 1526 704 427 235

for the given input data.

score 2 · Accepted Answer · edited May 23 '17 at 12:02

2

As mentioned here:

a cast takes precedence over a division operation

Therefore, and as I mentioned in the comments, you have to replace this:

int M = (int)Math.pow(encryptedBlocks[i], d) % n;

With this:

int M = (int)(Math.pow(encryptedBlocks[i], d) % n);

edited May 23 '17 at 12:02

Community

1
1

answered Mar 27 '17 at 00:41

Kh.Taheri

946
1
10
25

1

This still won't produce correct answers. The output of the first operation shall be 13 according to this https://www.wolframalpha.com/input/?i=(1573%5E83)+mod+(41*67), but the code will produce different answer due to overflow – Islam Hassan Mar 27 '17 at 00:49
@IslamHassan 13 is the exact value I need.. what am I doing wrong? – notAChance Mar 27 '17 at 00:51
Does the code produce 13 for you? for me it's 1147 for the first value. – Islam Hassan Mar 27 '17 at 00:52
It produces 1147 in the code for me, I have been banging my head against the wall for days! P.S. I did not know of the existence of wolframalpha... I wish I had.. – notAChance Mar 27 '17 at 00:53
1

The easiest way is to use BigInteger. Check my answer. – Islam Hassan Mar 27 '17 at 00:54
@IslamHassan; he just had a problem with the precedence. So, when he get larger values, he will, for sure, use a larger variables. – Kh.Taheri Mar 27 '17 at 00:54
The values he's providing in the question will fail to be stored in int or even long. Precedence is not the only problem. – Islam Hassan Mar 27 '17 at 00:59
@IslamHassan you are mistaken! you can easily try it in your computer with `int` and it will work probably. If you still have an error, please, post your code somewhere and we'll give a hand. – Kh.Taheri Mar 27 '17 at 01:12
As I commented, the problem is a wrong output. For the first number 1573, the output should be 13 as the link I posted says, however the above code will produce 1147. The code produces different outputs than what the op's mentioned, but still not the correct ones. – Islam Hassan Mar 27 '17 at 01:16
The code above will produce {1147, 2564, 1457, 2351, 2414, 982, 1073, 2480, 923, 1526, 704, 427, 235}, however the correct output is {13, 590, 570, 28, 301, 2068, 1720, 1379, 1891, 2018, 424, 2545, 25} – Islam Hassan Mar 27 '17 at 01:20

score 1 · Answer 3 · answered Mar 27 '17 at 00:40

1

Just precedence mistake
change this int M = (int)Math.pow(encryptedBlocks[i], d) % n; to
int M = (int)(Math.pow(encryptedBlocks[i], d) % n);

answered Mar 27 '17 at 00:40

kourouma_coder

1,078
2
13
24

score 1 · Answer 4 · answered Mar 27 '17 at 00:44

Yes, you are casting to int to early and that is causing the output to be same always. You can check this in the below output.

package test;

public class MathPow {

    static int p = 41;
    static int q = 67;
    static int d = 83;
    static int n = p * q;

    static int[] encryptedBlocks = {1573,
            1978,
            385,
            1092,
            1022,
            857,
            856,
            1387,
            225,
            606,
            2293,
            1339,
            1630};
    static int[] decryptedArray = new int[13];

    public static void main (String []args){

        for (int i = 0; i < encryptedBlocks.length; i++) {
            double power = Math.pow(encryptedBlocks[i], d);
            System.out.println("Power : "+power);
            double pwer = power % n;
            int M = (int)pwer;
            decryptedArray[i] = M;
            System.out.println("M : "+M);
        }

    }

}

Output when the casting to int is done at the end.

Power : 2.1305119658955046E265
M : 1147
Power : 3.8617294369074443E273
M : 2564
Power : 3.9195891716526933E214
M : 1457
Power : 1.4875753889539146E252
M : 2351
Power : 6.087295034019223E249
M : 2414
Power : 2.7378409793777127E243
M : 982
Power : 2.4849775423187883E243
M : 1073
Power : 6.199351610800489E260
M : 2480
Power : 1.702742606656262E195
M : 923
Power : 8.815111415893474E230
M : 1526
Power : 8.194765730142982E278
M : 704
Power : 3.332636081546012E259
M : 427
Power : 4.0885674380373943E266
M : 235

And output when the casting is done just after the Math.pow operation.

Power : 2.147483647E9
M : 2662
Power : 2.147483647E9
M : 2662
Power : 2.147483647E9
M : 2662
Power : 2.147483647E9
M : 2662
Power : 2.147483647E9
M : 2662
Power : 2.147483647E9
M : 2662
Power : 2.147483647E9
M : 2662
Power : 2.147483647E9
M : 2662
Power : 2.147483647E9
M : 2662
Power : 2.147483647E9
M : 2662
Power : 2.147483647E9
M : 2662
Power : 2.147483647E9
M : 2662
Power : 2.147483647E9
M : 2662

You can see that the power operation result is same hence M is same as well.

Ah, very interesting regarding the power operation. – notAChance Mar 27 '17 at 00:45 — notAChance, Mar 27 '17 at 00:45

score 1 · Answer 5 · answered Mar 27 '17 at 00:45

The result of the power operation is too large to be stored in an integer. 1573 ^ 83 alone is a 122-digits number, and you're doing the mod operation after calculating the power, so it has already overflowed.

If performance is not a concern, you can use BigInteger class. This should work:

BigInteger bigN = BigInteger.valueOf(n);
for (int i = 0; i < encryptedBlocks.length; i++) {
    BigInteger M = BigInteger.valueOf(encryptedBlocks[i]).pow(d).mod( bigN );
    decryptedArray[i] = Integer.valueOf(M.toString());
}
for(int i : decryptedArray) System.out.println(i);

However, BigInteger operations are a bit slow. If you prefer a faster solution you can implement your own power function so you can do a mod operation whenever you're near to overflow an integer value.

score 1 · Answer 6 · answered Mar 27 '17 at 00:48

Your issue is in the parentheses. This is how the compiler sees what you wrote:

((int) Math.pow(encryptedBlocks[i], d)) % n

It's subtle but what's happening it's casting to an int before taking the modulo. Ordinarily, this wouldn't make a difference but in your case, Math.pow is returning such a large number that casting it to an int truncates it to 2147483647 the maximum value an int can store, then it takes the module of that which will return 2662.

Now, to get the correct answer all we need to do is make sure it calculates the modulo first:

(int) (Math.pow(encryptedBlocks[i], d) % n)

Math.pow() returning same result with different inputs

6 Answers6