CODEWITHSUNDEEP
phpoverflowmodulus
Andrew Latham
Andrew Latham

Reputation: 6132

PHP Overflow Modulus

I am writing an algorithm that uses successive squaring to solve a^k mod m. Because of the way successive squaring works, the maximum number that the algorithm will ever have to compute is 2147483646^2 (I limited the user input to 214738364). Unfortunately, it still has to compute this. It seems to get the squaring part right, and then turns the overflowing number into a float, but then can't compute the modulus of a float and an integer.

A sample line is:

3422422^2 mod 715924 = 661224^2 mod 715924 = 437217178176 mod 715924 = -354280

How can I fix this, and how does one find one's way around integer overflow in PHP?

Upvotes: 0

Views: 180

Answers (1)

hackartist
hackartist

Reputation: 5264

I would suggest checking out the GMP extension and reading this question.

Upvotes: 1

Related Questions