Форум программистов, компьютерный форум, киберфорум
Алгебра, теория чисел
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.76/21: Рейтинг темы: голосов - 21, средняя оценка - 4.76
Заблокирован
1

Возведение в степень по составному модулю (теорема об остатках)

05.06.2014, 23:52. Показов 3911. Ответов 8
Метки нет (Все метки)

Помогите разобраться, как поступать, если модуль раскладывается не на два простых (и взаимно простых) числа, а представим неоднозначно и содержит квадраты. Вот пример.
Первый пример решается очевидно, вот он: https://www.cyberforum.ru/cgi-bin/latex.cgi?{2}^{97} mod 77
77 = 7*11
Обозначим https://www.cyberforum.ru/cgi-bin/latex.cgi?{2}^{97} mod 77 = x
Тогда можно записать систему сравнений:
https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix}x\equiv {2}^{97} mod 7 & \\ x\equiv {2}^{97} mod 11 & \end{matrix}\right.
По малой теореме Ферма https://www.cyberforum.ru/cgi-bin/latex.cgi?{2}^{6} \equiv 1 mod 7, а https://www.cyberforum.ru/cgi-bin/latex.cgi?{2}^{10} \equiv 1 mod 11.
https://www.cyberforum.ru/cgi-bin/latex.cgi?{2}^{97} = {({2}^{6})}^{16}*{2}^{1} = 2 mod 7
https://www.cyberforum.ru/cgi-bin/latex.cgi?{2}^{97} = {({2}^{10})}^{9}*{2}^{7} = {2}^{7} mod 11 = 7 mod 11
Пришли к новой системе:
https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix}x \equiv 2 mod 7 & \\ x \equiv 7 mod 11 & \end{matrix}\right.
Решая ее, получаем значение исходной степени: x = 51 mod 77

Но я не знаю, как поступить, когда модуль содержит квадраты или факторизуется неоднозначно. Вот пример, который я не могу решить: https://www.cyberforum.ru/cgi-bin/latex.cgi?{21}^{2012} mod 100 = x.
100 = 4*25 = https://www.cyberforum.ru/cgi-bin/latex.cgi?{2}^{2}*{5}^{2}

https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix}x\equiv {21}^{2012} mod 2& \\ x\equiv {21}^{2012} mod 5 & \end{matrix}\right.

https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix}x\equiv 1 mod 2& \\ x\equiv 1 mod 5 & \end{matrix}\right.

Решением этой системы будет 1 mod 10. Но очевидно, что https://www.cyberforum.ru/cgi-bin/latex.cgi?{21}^{2012} mod 100 не равно 1 (на самом деле это будет 41), к тому же, решая систему, я получил элемент кольца https://www.cyberforum.ru/cgi-bin/latex.cgi?{Z}_{10}, а моя степень лежит в https://www.cyberforum.ru/cgi-bin/latex.cgi?{Z}_{100}. Что я делаю не так?
Попытка составить систему сравнений по модулям 4 и 25 тоже ничего не дает:
https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix}x\equiv {21}^{2012} mod 4& \\ x\equiv {21}^{2012} mod 25 & \end{matrix}\right.
Хотя числа 4 и 25 взаимно просты, а значит для них должна работать теорема об остатках.
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
05.06.2014, 23:52
Ответы с готовыми решениями:

Возведение в степень по модулю
Необходимо, используя 1)"Метод, эффективно использующий память" 2)"Метод с использованием...

Возведение в степень по модулю
Доброго дня всем. Имеется код java, пытаюсь реализовать алгоритм быстрого возведения в степень...

Быстрое возведение в степень по модулю
Столкнулся с проблемой, из-за которой не могу реализовать шифр. Это метод быстрого возведения в...

Быстрое возведение в степень по модулю
Пытаюсь реализовать схему быстрого возведения в степень. Степень представляеться в двоичном виде,...

8
Эксперт по математике/физике
3814 / 2824 / 855
Регистрация: 19.11.2012
Сообщений: 5,896
06.06.2014, 07:25 2
Я заметил бы вначале, что
https://www.cyberforum.ru/cgi-bin/latex.cgi?<br />
21^1\equiv21 (mod 100),\\21^2\equiv41 (mod 100),\\21^3\equiv61 (mod 100),\\21^4\equiv81 (mod 100),\\21^5\equiv1 (mod 100).<br />
Дальше все стало бы очевидно.
0
Заблокирован
06.06.2014, 16:47  [ТС] 3
Вы предлагаете разложить исходную степень в произведение степени единицы и значительно меньшей степени числа 21? Это не подходит. Цель задания - вычислить степень по КТО, а не просто найти ее значение. Преподаватель даже смотреть не станет аналогичную контрольную работу, если она решена не по КТО.
Мб попробовать разложить мультипликативную группу Z100 в произведение подгрупп, и по модулям этих подгрупп составить систему сравнений? Хотя вряд ли, это я просто другими словами сформулировал суть КТО...
0
1128 / 787 / 232
Регистрация: 12.04.2010
Сообщений: 2,012
06.06.2014, 23:50 4
Цитата Сообщение от Eru Iluvatar Посмотреть сообщение
Цель задания - вычислить степень по КТО
Как раз следует рассмотреть сравнения по модулю 25 и 4. (Т.к. 25 и 4 взаимно просты, и их произведение 100.)

В этом случае если k = pn-1(p-1), и если a не делится на p, то ak = 1 ( mod pn ). (См. на эту тему: теорема Эйлера, функция Эйлера.) (Частный случай, когда n=1, малая теорема Ферма.)

Пример. Если (a,5) = 1, то a20=1 ( mod 25 ).

Теорема Эйлера. Для степени простого числа

https://www.cyberforum.ru/cgi-bin/latex.cgi?\varphi (p^n) \;=\; p^{\small n} - p^{\small n-1}

Добавлено через 12 минут
Цитата Сообщение от Eru Iluvatar Посмотреть сообщение
Мб попробовать разложить мультипликативную группу Z100 в произведение подгрупп, и по модулям этих подгрупп составить систему сравнений?
Правильно, именно так можно решить эту задачу. Если m, n взаимно просты, то Zmn изоморфно произведению Zm и Zn.
0
Заблокирован
07.06.2014, 00:32  [ТС] 5
Так тоже не получается.
https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix}x\equiv {21}^{2012} mod 4& \\ x\equiv {21}^{2012} mod 25 & \end{matrix}\right.

https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix}x\equiv {1}^{2012} mod 4& \\ x\equiv {21}^{2012} mod 25 & \end{matrix}\right.

https://www.cyberforum.ru/cgi-bin/latex.cgi?{21}^{24}\equiv 1 mod25

https://www.cyberforum.ru/cgi-bin/latex.cgi?x\equiv {(21)}^{24*84}*{21}^{20} mod 25

https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix}x\equiv 1 mod 4& \\ x\equiv 1 mod 25 & \end{matrix}\right.

x = 1 + 4k

https://www.cyberforum.ru/cgi-bin/latex.cgi?1 + 4k\equiv 1 mod 25

https://www.cyberforum.ru/cgi-bin/latex.cgi?4k\equiv 0 mod25

Последнее сравнение не имеет решения, потому что для 4 не существует обратного.

Добавлено через 24 минуты
А сейчас получается что-то похожее на правильных ход решения.
Я ошибся, когда искал степень числа 21, которая дает единицу, она равна 6. Далее получаю https://www.cyberforum.ru/cgi-bin/latex.cgi?{21}^{2} mod 25 = https://www.cyberforum.ru/cgi-bin/latex.cgi?16 mod 25
Составляю систему:
x = 16 mod 4
x = 1 mod 25,
откуда выражаю x = 16 + 4k = 4k (mod 4)
4k = 1 mod 25
И это сравнение я не могу решить. Элемент 4 не имеет обратного в кольце Z25, разделись обе части на число 2, взаимно простое с модулем, тоже не получается, потому что единица не делится нацело.
0
1128 / 787 / 232
Регистрация: 12.04.2010
Сообщений: 2,012
07.06.2014, 18:03 6
Eru Iluvatar, Если x не делится на n, то https://www.cyberforum.ru/cgi-bin/latex.cgi?x^{n-1} \equiv 1 ( mod n ) - это верно только для простых n.

Неверно, что https://www.cyberforum.ru/cgi-bin/latex.cgi?{21}^{24}\equiv 1 \; mod25

Пример.
Как правильно ? Чему должно быть равно k, чтобы было https://www.cyberforum.ru/cgi-bin/latex.cgi?{2}^{k}\equiv 1 \; mod9 ?
По модулю 9, например, 22 = ..., 23 = ..., 24 = ... (mod 9 )

Добавлено через 6 минут
Цитата Сообщение от Eru Iluvatar Посмотреть сообщение
Элемент 4 не имеет обратного в кольце Z25, разделись обе части на число 2, взаимно простое с модулем, тоже не получается, потому что единица не делится нацело.
https://www.cyberforum.ru/cgi-bin/latex.cgi?2k \equiv 1 ( mod 9 )

Eru Iluvatar, имеет ли решение это сравнение?

https://www.cyberforum.ru/cgi-bin/latex.cgi?4x \equiv 1 ( mod 7 )

Чему равно x ?
0
Заблокирован
07.06.2014, 19:17  [ТС] 7
2^6 = 1 mod 9

2k = 1 (mod 9)
Простым подбором 2k должно быть равно 10, k = 5, или аналитически:
2k = 1 + 9 (mod 9), 9 = 0 в кольце вычетов
2k = 10 (mod 9) делим на 2, (2, 9) = 1
k = 5 (mod 9)

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

Система:
x = 1 mod 4
x = 16 mod 25
Решение:
x = 1 + 4k
1 + 4k = 16 mod 25
4k = 15 mod 25
4k = 15+25 mod 25
k = 10 mod 25

x = 1 + 4k = 1 + 4(10 + 25t) = 1 + 40 + 100t = 41 mod 100
0
1128 / 787 / 232
Регистрация: 12.04.2010
Сообщений: 2,012
07.06.2014, 21:19 8
Цитата Сообщение от Eru Iluvatar Посмотреть сообщение
смог разобраться в этом задании
Поздравляю.

Кстати, может в будущем Вам пригодится такое утверждение:

Если p - простое число и x не делится на p, то

https://www.cyberforum.ru/cgi-bin/latex.cgi?{x}^{p(p-1)} \equiv 1 \: ( mod \: p^2 )  \\

Например,

https://www.cyberforum.ru/cgi-bin/latex.cgi?{x}^{6} \equiv 1 \: ( mod \: 9 )  \\ {x}^{20} \equiv 1 \: ( mod \: 25 )  \\
0
Эксперт по математике/физике
3814 / 2824 / 855
Регистрация: 19.11.2012
Сообщений: 5,896
09.06.2014, 06:26 9
Цитата Сообщение от Alex5 Посмотреть сообщение
это верно только для простых n.
Не только. Правильно так. Если это не верно, то n составное.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
09.06.2014, 06:26

Возведение числа в степень по модулю
Кто может поделиться функцией быстрого возведения в степень по модулю N^-1 MOD M

Возведение числа в степень по модулю в C#
пример: 2^11(mod5)=3(mod5). Вот, что я написала, но еще как-то нужно сделать проверку, что степень...

Возведение в степень по модулю. Большие числа
Всем привет. У меня есть пару способов возведения в степень по модулю, но с большими числами не...

Возведение в степень по модулю для большого числа
#include &lt;vcl.h&gt; #pragma hdrstop #include &lt;iostream&gt; #include &lt;math.h&gt; #include &lt;conio.h&gt;...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.