Finding modulo of large numbers squared

Question

I am currently writing a program that requires the calculation of:

(x^2) mod y

Both these numbers are integers. Both can be large numbers, though they never exceed 10^9.

That is still enough to overflow integer for x squared. Speed is crucial for this code so gradual multiplication is not usable.

Thank you.

Possible duplicate of [Calculate a\*a mod n without overflow](https://stackoverflow.com/questions/10076011/calculate-aa-mod-n-without-overflow) — phuclv, May 30 '19 at 15:58

score 0 · Answer 1 · edited Apr 13 '17 at 12:19

0

You can take a reference from this post

This should be a relatively easy example. 4^23=2^46. Now, since 2^5=32≡1(mod31),

2^46=(2^5)9×2=32^9×2≡1×2≡2(mod31)

edited Apr 13 '17 at 12:19

Community

answered Mar 19 '14 at 05:07

Vivek Kothari

score 0 · Answer 2 · answered Mar 19 '14 at 12:14

0

The solution was really simple. I used Long, instead of int and it works.

answered Mar 19 '14 at 12:14

Simon

2 Answers2