Последовательные квадраты в Python

Question

Я пишу программу на python, которая включает в себя повышение числа до чрезвычайно высокого показателя. Для этого я пытаюсь реализовать метод последовательных квадратов, чтобы уменьшить время вычисления и устранить риск ошибки переполнения.

Последовательные квадратов означает делать то же самое, как base**exponent % modulo и текущая функция Я написал это:

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 

Когда я проверить функцию с ssp(7, 13, 93) я получаю ответ 8, когда оно должно быть 19. Может кто-нибудь дать намек на то, что я сделал неправильно?

Answer 1

Вы делаете pow(7, 93, 13) =>8 но то, что вы хотите pow(7, 13, 93) =>19

своп вашей функцией второй и третий аргумент.

>>> 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 

Answer 2

Я думаю, что вы просто получили порядок аргументов. Третий аргумент - показатель степени; второй - модуль. Вероятно, это не то, что вы хотели.