CODEWITHSUNDEEP
pythonmath
Killasin
Killasin

Reputation: 21

Successive Squares in Python

I am writing a program in python that involves raising a number to an extremely high exponent. To do this, I am trying to implement the successive squares method to lower calculation time and remove the risk of overflow error.

Successive squares is meant to do the same thing as base**exponent % modulo and the current function I have written is this:

def ssp(b, m, n):
    ssp = 1
    while n>0:
        if n % 2 == 1:
            ssp = b*ssp % m
        b = b**2 % m
        n = n // 2
    return ssp

When I test the function with ssp(7, 13, 93) I get an answer of 8, when it should be 19. Can someone give a hint to what I did wrong?

Upvotes: 1

Views: 286

Answers (2)

Dan D.
Dan D.

Reputation: 74655

You are doing pow(7, 93, 13) => 8 but what you want is pow(7, 13, 93) => 19

Swap your function's second and third argument.

>>> def ssp(b, n, m):
...     ssp = 1
...     while n>0:
...         if n % 2 == 1:
...             ssp = b*ssp % m
...         b = b**2 % m
...         n = n // 2
...     return ssp
... 
>>> ssp(7, 13, 93)
19

Upvotes: 4

user2357112
user2357112

Reputation: 280648

I think you just got the order of the arguments wrong. The 3rd argument is the exponent; the second is the modulus. That's probably not what you wanted.

Upvotes: 1

Related Questions