Найти такое число b, что (a*b - 1) % p = 0

@a1paca · Регистрация: 06.07.2023

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

Есть число 2<=p<10^9 и число 0<a<p необходимо найти такое число b, что (a*b - 1) % p = 0
Есть идея использовать малую теорему Ферма (найти остаток от деления (a^(p - 2))%p), но т.к. p и a огромные, то такие числа хранить просто негде, нашел решение такой задачи на python (Обратное число ), но там используется встроенная функция pow(x, y, z) и туда можно передать в z число для получения остатка от деления (x^y%z).

@Volga_ · 08.07.2023, 07:23

a1paca, да.

@a1paca · 08.07.2023, 08:12 **[ТС]**

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

я предлагаю вам код, он может подойти по времени выполнения

при значениях p = 5 a = 1
код ничего не выводит, а должен вывести 1, в вашем решении не учтено, что 0 делится на p

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

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

ри значениях p = 5 a = 1
код ничего не выводит

объявил k = 0 заработало, сейчас отправлю решение

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

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

сейчас отправлю решение

не проходит по времени

@alexu_007 · 08.07.2023, 12:05

// быстрое возведение a в степень b по модулю m

C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
quint64 stmod(quint64 a, quint64 b, quint64 m)
{
    quint64 rez = 1;
 
    while (b)
    {
        if (b & 1)
        {
            rez *= a;
            rez %= m;
        }
 
        a *= a;
        a %= m;
        b >>=1;
 
    }
 
return rez;
}

@zss · 08.07.2023, 12:06

a1paca, в задаче, на которую Вы ссылаетесь,
есть такое

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

число p является простым

Может, всё-таки и в Вашей задаче есть такое условие?
Тогда решение из 14 сообщения
https://www.cyberforum.ru/post16966340.html
Вам подойдёт.

@a1paca · 08.07.2023, 16:42 **[ТС]**

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

Забыл написать, что p простое число

я позже писал о том, что p - простое число

Байт · 08.07.2023, 19:52

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

Байт, я несовсем вижу вида b=a[sub]p-2[//sb] при 0<b<p. Например: при p=7, a=3 получается решение b=5.

Что смущает?
3⁵ = 243 = 34*7 + 5 = 5 (mod 7)
5*3 = 15 = 1 (mod 7)

Новые блоги и статьи Все статьи Все блоги /
Транскрипция 55-минутного видео через Whisper: WhisperDesktop облажался, спас Google Colab[ anaschu 01.06.2026 Понадобилось получить текст из свежезагруженного видео на YouTube. Казалось бы, задача на пять минут. Заняла полтора часа. Делюсь опытом — может кому пригодится последовательность решений. . . .	21 мат мед. Планы на развитие модели здравоСохранения anaschu 01.06.2026 AnyLogic: план развития симуляционной модели рабочего коллектива — динамический абсентеизм, реальные данные, три сценария сравнения Продолжаю серию постов о дискретно-событийной модели рабочего. . .	20. Мат мед. Абсентеизм как отдельный тип простоя anaschu 29.05.2026 Апдейт модели: исправленные баги, абсентеизм и новые механизмы Продолжаю развивать ранее описанную модель рабочего коллектива на AnyLogic. За последние несколько дней был проведён серьёзный. . .	19. здоровье, усталость и психотип работника влияют на производительность предприятия, и наоборот, производительность на здоровье, усталось и психотип anaschu 28.05.2026 Дискретно-событийная модель рабочего коллектива на AnyLogic: здоровье, выгорание, психотипы и микростимуляция Привет, коллеги. Хочу поделиться итогами нескольких недель работы над симуляционной. . .
"Прокси" для последовательного порта Eddy_Em 28.05.2026 Эту штуку написал я достаточно давно. Но сейчас вот понадобилось настроить датчик грозы, но при этом не отключать его от "метеодемона". Соответственно, надо запустить этот "прокси": метеодемон будет. . .	Рефакторинг программы уравнивания. Massaraksh7 26.05.2026 Пример по предыдущей записи в блоге. Но, надо заметить, что, во-первых, там оптимизация не только математики, но и работы с базой данных, и с графами, а во-вторых, это ещё не всё.	Использование TThread в Lazarus для математических вычислений. Massaraksh7 25.05.2026 Производя рефакторинг своих программ на предмет ускорения их работы, обратил внимание на такой аспект, как сокращение времени матвычислений. Дело в том, что приходится работать с большими матрицами. . .	Модель здравосохранения 18. Чем здоровее работник, тем быстрее выгорает anaschu 24.05.2026 Имитационная модель корпоративного здравоохранения: что показывает математика Сегодня в модели рабочего коллектива на AnyLogic появились три новые механики — выгорание через накопленную усталость,. . .

@a1paca 1 / 1 / 0 Регистрация: 06.07.2023 Сообщений: 33

	Найти такое число b, что (ab - 1) % p = 0 06.07.2023, 14:27. Показов* 2972. Ответов 25 Метки algorithm, c++ (Все метки) Есть число 2<=p<10^9 и число 0<a<p необходимо найти такое число b, что (a*b - 1) % p = 0 Есть идея использовать малую теорему Ферма (найти остаток от деления (a^(p - 2))%p), но т.к. p и a огромные, то такие числа хранить просто негде, нашел решение такой задачи на python (Обратное число ), но там используется встроенная функция pow(x, y, z) и туда можно передать в z число для получения остатка от деления (x^y%z). 0

@Volga_ Модератор 5209 / 2927 / 1509 Регистрация: 14.12.2018 Сообщений: 5,267 Записей в блоге: 1
	08.07.2023, 07:23
	a1paca, да. 0