Как в С/С++ сделать реализацию примера?

Question

[NikSIk31]

Есть числа A и B , нужно вычислить C из формулы C^B = 1 (mod A)
как это можно вычислить?

Answer 1

[Максим Мосейчук]

У этой задачи бесконечное множество решений.
И C++ тут не причем. Это алгебра.

Пример: A=2, B=3.
Тогда C может быть любым положительным нечётным числом.

Степень это перемножение одинаковых чисел. Перемножение любого количества нечётных даст нечётное. Нечётное число всегда имеет 1 в остатке от деления на 2.

Comments

[NikSIk31]

тогда мне надо самое первое, удовлетворяющее условию

[Максим Мосейчук]

NikSIk31, Тогда вам нужно просто решить диофантово уравнение с двумя неизвестными.

x1^B - x2*A = 1

Которое можно привести к линейному виду, заменив x1^B на y.

Найти все корни уравнения.

Затем нужно найти такой y из всех решений, корень степени B которого давал бы целое число. Это число и будет решением.

Возможно есть способ попроще.

[#]

Максим Мосейчук, если мне не изменяет память, это даже не алгебра, а арифметика ))
что, в прочем, не означает простоты решения многих ее задач ))

[Максим Мосейчук]

#, когда у нас в задаче появляются буквы вместо чисел, тогда арифметика превращается в алгебру.

[NikSIk31]

я конечно все понимаю, но может что-то подскажете?

[Владимир Т]

Если С = 1, то при любом В мы имеем С^B = 1. 1 mod A = 1 также при любом A. То есть при любых A, B наименьшим возможным решением будет С = 1.
Впрочем, я не математик, могу и ошибаться.

[Максим Мосейчук]

NikSIk31, тут нужно учесть, что я сделал допущение, что ^ это возведение в степень, а A, B и C целые числа. Из вопроса это не ясно.

Если условия другие, тогда и решение другое.

[Максим Мосейчук]

Владимир Т, при A = 1 не сработает

[Максим Мосейчук]

NikSIk31, ну что вам подсказать. Эта задача в общем виде не решается за разумное время.

Это из разряда факторизации числа и дискретного логарифма.

Может у вас есть полный текст задачи, где есть какие-то граничные условия?

Впрочем я тоже не математик и могу ошибаться.

Но я уже сказал, я пока только одно решение вижу: перебор корней диофантового уравнения.

[Владимир Т]

Максим Мосейчук, при А = 1 задача не имеет решения, т.к. x mod 1 = 0 при любом x.

[NikSIk31]

Максим Мосейчук, это из алгоритма Шнорра https://ru.wikipedia.org/wiki/Схема_Шнорра#Пример

[Максим Мосейчук]

Может в Википедии неточность, но там написано, что q не вычисляется, а выбирается. Т.е. опять же перебором.

[NikSIk31]

Максим Мосейчук, там p выбирается, а q ищется из делителей p-1 , а потом по формуле во втором пункте написано "вычисляется" . а вообще хз

[Максим Мосейчук]

NikSIk31, все верно. Я не туда посмотрел. И не q а g.

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

[Roman]

NikSIk31,

картинка

[Максим Мосейчук]

NikSIk31, ваша задача является задачей нахождения корня n степени из единицы в конечном поле. Таких корней много.
Решение сводится к генерации случайного числа и его проверке. Если число не подошло, то генерируется новое число.

https://crypto.stackexchange.com/questions/63614/f...

Вот в wolfram список решений со значениями из вики...