Найти такое число 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)

Новые блоги и статьи Все статьи Все блоги /
Установка MinGW GCC 16.2 и CMake 8Observer8 10.08.2026 VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия	Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо anaschu 10.08.2026 Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .	Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .
Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .	Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники). Hrethgir 04.08.2026 Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .	Термопринтер QR701 Argus19 03.08.2026 Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .

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

	Найти такое число b, что (ab - 1) % p = 0 06.07.2023, 14:27. Показов* 3022. Ответов 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

Опции темы