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

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

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

x1^B - x2*A = 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

NikSIk31,

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

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

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