Проблема с модульным возведением в степень

Я пытаюсь решить проблему, когда нам нужно вывести последнюю цифру заданного числа n^p.

int modularExponentiation(int n, long long p, int m){
    if(p == 0) return 1;
    if(p & 1)
        return (n % m * modularExponentiation((n*n) % m, p / 2, m) % m) % m;//line 4
    return modularExponentiation((n*n) % m, p / 2, m) % m;
}

В этом рекурсивном коде мы меняем временный результат, применяя по модулю в строке 4. Не внесет ли это никаких изменений в окончательный ответ? например, если на любом промежуточном этапе ответ будет 81^4, применив %10 к 81 и заменив его на 1, не изменит ли это окончательный результат?


c++ modular-arithmetic number-theory
person Pranav Venkata    schedule 31.03.2020    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Нет, на результат это не влияет, т.к. (a*b)%m == ((a%m) * (b%m))%m. Возведение в степень — это, конечно, просто повторное умножение, поэтому применяется тот же принцип.

(81^4)%10 достаточно мал, чтобы попробовать это вручную. Давай, пиши.

person MSalters    schedule 31.03.2020
comment
Я ищу математический термин для этого уравнения. Не могли бы вы помочь мне, пожалуйста? :D - person RoQuOTriX; 31.03.2020
comment
@RoQuOTriX Я не думаю, что кто-то заботился о том, чтобы назвать это равенство. Обычно вы изучаете это и то, как это доказать, когда изучаете модульную арифметику. - person molbdnilo; 31.03.2020
comment
Я думал, что у него есть имя, поскольку мы обсуждали его в криптографии. Но, может быть, существует только название метода шифрования, основанного на уравнении - person RoQuOTriX; 31.03.2020
comment
@MSalters Я понимаю, что (a*b)%m == ((a%m) * (b%m))%m. Но моя проблема здесь в том, что если b — небольшое число, мы используем тот же алгоритм, но нигде без модуля. Но поскольку мы заменяем результаты их модулем, не повлияет ли это на окончательное вычисление a^b, и если окончательный результат не пострадает, не могли бы вы упомянуть, как мы выбираем число по модулю (m в этом случае) (рассмотрите a %m и a›m). Заранее спасибо. - person Pranav Venkata; 31.03.2020
comment
@PranavVenkata: Логика в том, что мы можем написать a как (a/m)*m + (a%m), и то же самое для b. Помните, что в C++ a/m округляется в меньшую сторону. Теперь (a/m)*m, очевидно, кратно m, поэтому ((a/m)*m)%m == 0. Итак, все, что нам нужно сделать, это записать a*b, чтобы получить (a/m*b/m)*m*m + (a/m*b%m+b/m*a%m)*m + (a%m)*(b%m). Опять же, все числа, кратные m, равны 0 по модулю m. - person MSalters; 31.03.2020

arrow_upward
0
arrow_downward

Для модульного сложения и умножения можно брать мод на каждом шагу и на результат это не повлияет. На самом деле именно так вы должны выполнять модульное возведение в степень, чтобы избежать переполнения. Поэтому ваша окончательная функция будет выглядеть так:

long long modExp(long long n, long long p, long long m) {
    if (p == 0) {
        // m could be 1 you never know
        return 1 % m;
    }
    n %= m;
    return (n * modExp(n, p - 1, m)) % m;
}
person Aplet123    schedule 31.03.2020
comment
давайте рассмотрим (3 ^ 3)% 10, что можно записать как (3% 10 * 3% 10 * 3% 10)% 10, что получается 27% 10, что равно 7. если мы заменим основание 27 на 7 (учитывая, что 27 является промежуточным результатом в процессе рекурсии), не даст ли это нам неверный результат в решении? Заранее спасибо! - person Pranav Venkata; 31.03.2020
comment
Как мне рассматривать m (по модулю) выше? - person Pranav Venkata; 31.03.2020
comment
@PranavVenkata 7 % 10 тоже 7. Я думаю, вам нужно больше узнать о модульной арифметике. - person molbdnilo; 31.03.2020
comment
@PranavVenkata: Модули 10, 27 и 7 конгруэнтны. Для совместимых операций вы можете заменить конгруэнтные числа. Обратите внимание, что не все операции совместимы. √4 равно 2, но √64 = 8. Однако 64%10=4, но 8%10 не равно 2. Однако умножение совместимо. - person MSalters; 31.03.2020
comment
Сложение, вычитание и умножение полностью работают с модульной арифметикой. Разделение действительно работает, вам просто нужно сделать несколько дополнительных шагов. - person Aplet123; 31.03.2020