PHP Overflow Modulus

Question

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?

How can you fix what? That floating-point/integral mod isn't available? — Lightness Races in Orbit
– Lightness Races in Orbit, Commented Jan 7, 2012 at 17:37
Well, obviously a modulo isn't going to return a negative number, yet that is what's occurring here. Is there a special PHP function for the modulus of a float and an integer? — Andrew Latham
– Andrew Latham, Commented Jan 7, 2012 at 17:39
What's wrong with modulus returning a negative number? I don't think floating-point has anything to do with it; it's just an overflowed integer. — Lightness Races in Orbit
– Lightness Races in Orbit, Commented Jan 7, 2012 at 17:42
Sorry, I meant the modulus of two positive integers won't return a negative number, as in the example I showed. So what's happening here? I thought that as soon as an integer overflowed in PHP, its type was changed to a floating point number. So after 661224^2 overflow, 4372178176 becomes a float, and then it's trying to compute the modulus of a positive float and a positive integer. — Andrew Latham
– Andrew Latham, Commented Jan 7, 2012 at 17:47
I doubt that's easy to reimplement with a productive runtime behaviour (you'd need to work on strings and simulate integer arithmentic). Which is why bcpowmod() exists. — mario
– mario, Commented Jan 7, 2012 at 17:49

Community · Accepted Answer · 2023-11-20 22:45:59Z

1

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

edited Nov 20, 2023 at 22:45

CommunityBot

11 silver badge

answered Jan 7, 2012 at 17:59

hackartist

5,2745 gold badges36 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

PHP Overflow Modulus

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related