Алгоритм возведения в степень по модулю

@Mad_Programmer · Регистрация: 22.02.2018

Студворк — интернет-сервис помощи студентам

Доброго времени суток! Пишу алгоритм для декодирования шифра RSA. В этом алгоритме требуется возводить очень большое число в очень большую степень по очень большому модулю. Написал алгоритм, верность его математически доказана.

C++
1
2
3
4
5
6
7
8
unsigned long long modexp (unsigned long long x, unsigned long long y, unsigned long long n)
    {
    if (y == 0) return 1;
 
    unsigned long long z = modexp (x, y / 2, n);
    if (y % 2 == 0) return (z * z) % n;
    else return (x * z * z) % n;
    }

Беда в том, что при больших x, y алгоритм начинает выводить неправильное значение. Например 4051753 ^ 6111579 = 111111 mod 9173503, а алгоритм выводит, что 4051753 ^ 6111579 = 6585669 mod 9173503.
Подскажите, пожалуйста, где ошибка.

@QuakerRUS · 14.07.2018, 01:29

Я в RSA не шарю, но имейте ввиду, что unsigned long long вмещает числа в диапазоне [0, 18 446 744 073 709 551 615].

@Mad_Programmer · 14.07.2018, 01:33 **[ТС]**

Дело в том, что все числа, которые могут появится в возведении в степень, намного меньше предела unsigned long long. Проверено. Тут проблема в чём-то другом. А что до самого RSA - так тут его знания и не нужны, тут просто алгоритм возведения в степень по модулю.

@nonedark2008 · 14.07.2018, 01:45

Сообщение от Mad_Programmer

x * z * z

При достаточно больших значениях x и z у тебя будет переполнение.

@QuakerRUS · 14.07.2018, 01:47

C++
1
2
3
4
5
6
7
8
9
unsigned long long modexp(unsigned long long x, unsigned long long y, unsigned long long n)
{
    int c = 1;
 
    for (int i = 0; i < y; ++i)
        c = c * x % n;
 
    return c;
}

Verevkin · 14.07.2018, 01:52

Расшифруй мне, что означает эта надпись:

Сообщение от Mad_Programmer

4051753 ^ 6111579 = 111111 mod 9173503

@QuakerRUS · 14.07.2018, 01:53

Verevkin, первое, второе, четвертое число передается в аргументах, третее он хочет видеть в возвращаемом значении.

Verevkin · 14.07.2018, 01:56

Сообщение от QuakerRUS

первое, второе, четвертое число передается в аргументах, третее он хочет видеть в возвращаемом значении.

Меня больше интересуют назначения загадочных "^", "=", "mod".

@QuakerRUS · 14.07.2018, 01:59

Verevkin, степень, равно, остаток от деления.

Добавлено через 2 минуты
Verevkin, он правда неверно написал. Надо было 4051753 ^ 6111579 mod 9173503 = 111111

@Yetty · 14.07.2018, 02:07

4051753 ^ 6111579 значительно превышает максимальное значение типа unsigned long long
Поправьте если ошибаюсь - например взяли числа меньше 10^100000 - получили 1 с 100000 нулями

Verevkin · 14.07.2018, 02:07

Сообщение от QuakerRUS

он правда неверно написал. Надо было 4051753 ^ 6111579 mod 9173503 = 111111

Я всё равно не понимаю, как из этого

a ^ b % с = 111111

выразить это:

a ^ b = ?

@QuakerRUS · 14.07.2018, 02:08

Yetty, лишнее отсекается остатком от деления. Но у него переполнение при двойном произведении, как выше написали.

Добавлено через 29 секунд
Verevkin, надо просто посчитать a ^ b % c

Verevkin · 14.07.2018, 02:11

Сообщение от QuakerRUS

надо просто посчитать a ^ b % c

Зачем? Оно ж равно 111111 по условию.

@QuakerRUS · 14.07.2018, 02:12

Verevkin, 111111 - это возвращаемое значение, которое он ожидает. Он изначально число 111111 зашифровал, а теперь этой функцией расшифровывает.

@nonedark2008 · 14.07.2018, 02:16

Сообщение от QuakerRUS

он правда неверно написал

Нет, он использует вполне стандартную нотацию.

Verevkin · 14.07.2018, 02:17

Сообщение от QuakerRUS

111111 - это возвращаемое значение, которое он ожидает. Он изначально число 111111 зашифровал, а теперь этой функцией расшифровывает.

ааааааааа, ну ладно. Меня дезинформировало это:

Сообщение от Mad_Programmer

требуется возводить очень большое число в очень большую степень

@Yetty · 14.07.2018, 02:18

Сообщение от QuakerRUS

лишнее отсекается остатком от деления

можете растолковать чуть подробнее. или привести пример.

@QuakerRUS · 14.07.2018, 02:22

nonedark2008, странная какая то нотация. Есть пример? Потому как его пример, например, тут по другому написан.

https://ru.wikipedia.org/wiki/RSA

Добавлено через 2 минуты
Yetty, чтобы не вникать в его рекурсию я просто в начало его функции добавил эту строку и убедился, что числа не сильно растут.

C++
1
cout << x << endl << y << endl << n << endl << endl;

В нерекурсивном варианте, который я написал, там каждый проход цикла высчитывается остаток от деления и числа растут максимум до своего квадрата.

Сообщение от Verevkin

Меня дезинформировало это

Я тоже не понял, что он имел ввиду, пока не открыл в википедии статью с его примером, где уже человеческим языком написано.

@nonedark2008 · 14.07.2018, 10:20

Сообщение от QuakerRUS

странная какая то нотация

Например.
$https://www.cyberforum.ru/cgi-bin/latex.cgi?a \equiv b \text{ mod } m$ читается как a сравнимо c b по модулю числа m. Лучше в учебнике по дискретной математике почитать.

Добавлено через 2 минуты

Сообщение от QuakerRUS

Потому как его пример, например, тут по другому написан.

Там написано и так и сяк. Но я бы вообще не доверял википедии в правдивости всего там написанного.

@QuakerRUS · 14.07.2018, 11:02

Сообщение от nonedark2008

читается как a сравнимо c b по модулю числа m.

Если бы он написал 4051753^6111579 ≡ 111111 (mod 9173503), то вопросов бы не было.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .

@QuakerRUS 1469 / 1010 / 456 Регистрация: 30.10.2017 Сообщений: 2,799
	14.07.2018, 01:29
	Я в RSA не шарю, но имейте ввиду, что `unsigned long long` вмещает числа в диапазоне [0, 18 446 744 073 709 551 615]. 0

@Mad_Programmer 0 / 0 / 0 Регистрация: 22.02.2018 Сообщений: 25
	14.07.2018, 01:33 [ТС]
	Дело в том, что все числа, которые могут появится в возведении в степень, намного меньше предела unsigned long long. Проверено. Тут проблема в чём-то другом. А что до самого RSA - так тут его знания и не нужны, тут просто алгоритм возведения в степень по модулю. 0

@QuakerRUS 1469 / 1010 / 456 Регистрация: 30.10.2017 Сообщений: 2,799
	14.07.2018, 01:53
	Verevkin, первое, второе, четвертое число передается в аргументах, третее он хочет видеть в возвращаемом значении. 0

@QuakerRUS 1469 / 1010 / 456 Регистрация: 30.10.2017 Сообщений: 2,799
	14.07.2018, 01:59
	Verevkin, степень, равно, остаток от деления. Добавлено через 2 минуты Verevkin, он правда неверно написал. Надо было 4051753 ^ 6111579 mod 9173503 = 111111 0

@Yetty 7438 / 5030 / 2892 Регистрация: 18.12.2017 Сообщений: 15,692
	14.07.2018, 02:07
	4051753 ^ 6111579 значительно превышает максимальное значение типа unsigned long long Поправьте если ошибаюсь - например взяли числа меньше 10^100000 - получили 1 с 100000 нулями 0

@QuakerRUS 1469 / 1010 / 456 Регистрация: 30.10.2017 Сообщений: 2,799
	14.07.2018, 02:08
	Yetty, лишнее отсекается остатком от деления. Но у него переполнение при двойном произведении, как выше написали. Добавлено через 29 секунд Verevkin, надо просто посчитать a ^ b % c 0

@QuakerRUS 1469 / 1010 / 456 Регистрация: 30.10.2017 Сообщений: 2,799
	14.07.2018, 02:12
	Verevkin, 111111 - это возвращаемое значение, которое он ожидает. Он изначально число 111111 зашифровал, а теперь этой функцией расшифровывает. 0

Алгоритм возведения в степень по модулю

Решение