§4. Сравнения с одним неизвестным
Будем рассматривать сравнения вида a0xn + a1xn-1 + … + an≡ 0 (mod m) (*).
Если a0 не делится на m, то n называется степенью сравнения.
Решить сравнение – значит найти все x, ему удовлетворяющие. Два сравнения, которые удовлетворяют одни и те же значения x, называются равносильными.
Если сравнению (*) удовлетворяет какое-то x=x1, то ему же будут удовлетворять все числа, сравнимые с x1 по модулю m: x ≡ x1(mod m). Весь класс чисел, сравнимых с x1 по модулю m считается за одно решение. Таким образом, (*) будет иметь столько решений, сколько вычетов из полной системы ему удовлетворяет.
Пример:
x5+x+1=0 (mod 7) удовлетворяют x ≡ 2 (mod 7) и x ≡ 4 (mod 7) – 2 решения.
4.1. Сравнения первой степени.
Любое сравнение первой степени можно привести к виду ax ≡ b (mod m). Рассмотрим случай, когда (a, m)=1. Согласно утверждению 2 пункта 3 §3, когда x пробегает полную систему вычетов по модулю m, ax тоже пробегает полную систему вычетов по по модулю m. Следовательно, при одном и только одном значении x из полной системы вычетов, ax будет сравнимо с b, т.е. при (a, m)=1 сравнение имеет ровно 1 решение.
Нахождение решения: Так как (a, m) = 1, то по теореме обратимости a-1 , и тогда исходному сравнению равносильно x ≡ a-1b (mod m).
Пусть теперь (a,m)=d>1. Для того, чтобы сравнение имело решение, необходимо, чтобы d\b, иначе сравнение невозможно (свойство сравнений №14).
Если же a=a1d, b=b1d, m=m1d , то исходному сравнению равносильно a1x≡b1(mod m1), причем (a1,m1)=1 сравнение имеет 1 решение по mod m1: x≡x1(mod m1), или d решений по модулю m:
x≡ x1 (mod m),
x≡ x1+m1(mod m),
x≡x1+2m1(mod m),
…
x≡x1+(d–1)m1(mod m).
Пример 1.
Решить сравнение 6x = 5 (mod 35).
Вычислим НОД(6, 35), пользуясь алгоритмом Евклида:
35 = 65+5,
6 = 15 +1
5 = 51+0 НОД(6, 35)=1.
Вычислим обратный элемент к 6 по модулю 35, пользуясь расширенным алгоритмом Евклида:
1 = 6–5=6–(35–65)=6–35+65= 66–35
6-1 = 6 (mod 35).
Домножим правую и левую части исходного сравнения на 6:
6-16x≡6-15(mod 35)
1x≡65(mod 35)
Ответ: x ≡ 30 (mod 35)
Пример 2.
Решить сравнение 18x = 6 (mod 24).
Вычислим НОД(18, 24), пользуясь алгоритмом Евклида:
24 = 18 + 6;
18 = 26+0 НОД(18, 24)=6.
Правая и левая части сравнения, а также модуль, делятся на 6. Разделим исходное сравнение на 6 и получим равносильное сравнение:
3x ≡ 1 (mod 4) *.
Вычислим НОД(3, 4), пользуясь алгоритмом Евклида:
4 = 13 + 1;
3 = 31 + 0 НОД(3, 4)=1.
Вычислим обратный элемент к 3 по модулю 4, пользуясь расширенным алгоритмом Евклида:
1=4–3 3-1 = –1(mod 4).
Домножим правую и левую части сравнения (*) на –1:
3-1 3x=–11 (mod 4) x≡ –1 (mod 4).
Или, переводя решение в систему наименьших неотрицательных вычетов, x≡ 3 (mod 4).
Ответ: получили 6 решений по модулю 24:
x≡ 3 (mod 24);
x≡ 7 (mod 24);
x≡ 11 (mod 24);
x≡ 15 (mod 24);
x≡ 19 (mod 24);
x≡ 23 (mod 24).
4.2. Система сравнений первой степени. Китайская теорема об остатках.
Рассмотрим систему сравнений
*
От системы сравнений вида aix ≡ bi (mod mi) можно перейти к данной способом, указанным в п.1.
Китайская теорема об остатках (I век до н.э. Сунь-Цзе)
Пусть m1,…, mk – попарно простые числа система сравнений (*) имеет единственное решение x0 ≡ **,
где M= , Mi= , .
Доказательство:
Т.к. ms\Mj
система (*) равносильна системе
***
т.е. системам (*) и (***) удовлетворяют одни и те же значения x. Системе (***) (в силу свойств 12 и 13 сравнений) удовлетворяют те и только те значения, которые заданы теоремой (т.е. x0).
Следствие.
Если в системе ** независимо друг от друга пробегают полные системы вычетов по модулям соответственно, то пробегает полную систему вычетов по модулю M.
Доказательство: в силу свойства 13 сравнений, x0 пробегает ровно M не сравнимых по модулю M значений.
Пример
Решить систему сравнений:
mi345
Mi201512
233
Вычислим параметры, необходимые для нахождения решения. Составим таблицу
Согласно китайской теореме об остатках, решением будет являться
x0≡1202+2153+4123(mod 60)≡40+90+144(mod 60)≡34(mod 60).
Ответ: x≡34(mod 60).
Проверка:
Решение верно.
4.3. Применения китайской теоремы об остатках.
Китайская теорема об остатках находит широкое применение в теории чисел и криптографии.
Применение Китайской теоремы об остатках в криптосистеме RSA.
В криптосистеме RSA при расшифровании требуется вычислить ydmod n, причем известно, что n=pq, где p, q – большие простые числа. Как было показано ранее, степень d, в которую требуется возвести шифрованный текст, можно понизить за счет использования теоремы Эйлера. Зная разложение числа n на простые сомножители и используя китайскую теорему об остатках, возможно еще более ускорить вычисления.
Сначала вычисляют:
r1=yd mod p=(y mod p)d mod (p–1)mod p,
r2=yd mod q=(y mod q)d mod (q–1)mod q.
Как читатель мог заметить, при вычислениях для ускорения возведения в степень используется теорема Ферма.
Получим систему сравнений
.
Решая ее по китайской теореме об остатках, получим решение .
Сложность возведения в степень с использованием китайской теоремы об остатках и теоремы Ферма составляет около 6k3 против 24k3 при использовании только теоремы Ферма (где k есть размерность числа n).
Пример.
Пусть в RSA
Требуется вычислить x=10029 mod 187.
Вычисляем:
r1=(100 mod 11)29 mod 10 mod 11=19 mod 11 = 1,
r2=(100 mod 17)29 mod 16 mod 17=1513 mod 17=2.
Cоставляем систему
Пользуясь Китайской теоремой об остатках, решаем эту систему.
mi1117Mi1711M’i214
Получаем
Ответ: 10029 mod 187=155.
Схема разделения секрета на основе Китайской теоремы об остатках.
На основе китайской теоремы об остатках можно построить (n,k)–пороговую схему разделения секрета. Напомним основные принципы схем разделения секрета.
Пусть существует некая информация, которую следует сохранить в секрете, и имеется n участников, не доверяющих друг другу. Эти участники хотят, чтобы секретную информацию можно было получить только при условии того, что как минимум k участников из n собрались вместе.
(n,k)-пороговая схема разделения секрета – это схема разделения секретной информации между n участниками таким образом, чтобы только k из них (или более), собравшись вместе, могли получить этот секрет. Причем вероятность угадать верное значение секрета при наличии k–m долей секрета m>0 равна вероятности угадать верное значение секрета без обладания долей секрета. При этом все участники протокола равноправны.
Как правило, схемы разделения секрета состоят из 2-х фаз: фазы разделения, когда каждому участнику протокола выдается его доля секрета, и фаза восстановления, когда k или более любых участников, собрав свои доли, восстанавливают общий секрет.
Схема разделения секрета на основе китайской теоремы об остатках выглядит следующим образом:
Пусть N – общий секрет.
Разделение секрета:
Берем p1, p2,…, pn – различные простые числа.
Часть секрета, выдаваемая i-му участнику схемы, есть число xi, вычисляемое как xi≡N(mod pi).
Заметим, что числа p1, p2,…, pn должны быть такими, чтобы произведение любых k из них было больше, чем N. А это достигается, когда для всех i выполняется pi> .
Для того, чтобы k–1 участников не смогли восстановить секрет без k-го участника, необходимо, чтобы pi << .
Итак, относительно чисел p1, p2,…, pn должны выполняться условия:
< pi << .
Восстановление секрета:
Собравшись вместе, k участников составляют и решают систему сравнений .
Решив систему, участники получают общий секрет N.
4.4. Сравнения любой степени по простому модулю.
Пусть р – простое число, и пусть задано сравнение вида f(x)≡0(mod p), где f(x)=axn+a1xn—1+…+an *. Тогда справедлива
Теорема 1:
Сравнение вида * равносильно сравнению степени, не выше р—1.
Доказательство:
Деля f(x) на (xp—x) с остатком, имеем f(x) =(xp—x)Q(x)+R(x).
Так как xp—x≡0(mod p), то f(x)≡R(x)(mod p), а степень многочлена R(x) не выше, чем р–1. Что и требовалось доказать.
Теорема 2
Если сравнение * имеет более n решений, то все коэффициенты многочлена f(x) кратны р.
Доказательство:
Пусть * имеет хотя бы n+1 решение, и вычеты этих решений суть x1, x2, … , xn, xn+1.
Тогда многочлен f(x) можно представить в виде
f(x)=a(x—x1)(x—x2)(x—x3)…(x—xn)+ **
+b(x—x1)(x—x2)…(x—xn—1)+
+c(x—x1)(x—x2)…(x—xn—2)+
……...
+l(x—x1)+m.
Справедливость этого равенства проверяется раскрытием скобок в правой части.
Полагая в этом равенстве x=x1, убеждаемся, что p\m, полагая x=x2 и учитывая, что p\m, убеждаемся, что р\l. Полагаем, что x=x3, x=x4, …, x=xn+1 и последовательно убеждаемся, что p\c, p\b, p\a, то есть все коэффициенты из ** делятся на p.
Учтем, что a=a, , , … , , то есть коэффициенты из * являются линейными комбинациями коэффициентов из **, а значит a, a1, a2, …, an кратны р как линейные комбинации чисел, кратных р.
4.5. Сравнения любой степени по составному модулю.
Теорема
Если m1, m2, … , mk – попарно простые числа, то сравнение
f(x)≡0(mod m1·m2·…·mk) *
равносильно системе
** ,
причем, если первое сравнение имеет T1 решений по модулю m1, второе – T2 решений модулю m2, …, k-е сравнение имеет Tk решений по модулю mk, то исходное сравнение будет иметь T=T1·T2·…·Tk решений по модулю m1·m2·…·mk.
Доказательство:
Равносильность сравнения и системы очевидна и следует из свойств 12 и 13 сравнений.
Утверждение о количестве решений следует из того, что каждое сравнение
f(x)≡0(mod ms) ***
выполняется тогда и только тогда, когда выполняется одно из Ts сравнений вида x≡bs(mod ms) (где bs пробегает вычеты решений сравнения ***). Причем возможно всего T=T1·T2·…·Tk различных комбинаций вида x≡b1(mod m1), x≡b2(mod m2),…, x≡bk(mod mk), которые приводят (по китайской теореме об остатках) к различным классам вычетов по модулю m1·m2·…·mk.
Из доказанной теоремы следует, что решение сравнения вида сводится к решению сравнений вида .
А решение сравнение вида f(x)≡0(mod pα) может быть найдено, если известно решение сравнения f(x)≡0(mod p). Покажем это.
Пусть x≡x1(mod p) – решение сравнения f(x)≡0(mod p). Тогда x можно представить в виде
x=x1+pt1, где .
Подставляя такое x в сравнение f(x)≡0(mod p2) и применяя формулу Тейлора (учитывая, что f(x) – многочлен, x1 – целое число, поэтому ), получаем
f(x1)+pt1f '(x1)≡0(mod p2).
Поскольку f(x1)≡0(mod p), то p\f(x1), а значит можно сократить в получившемся выражении на p правую, левую части и модуль. Получим:
Если f '(x1) не делится на р, то данное сравнение имеет одно решение:
(т.е. )
Подставляя полученное x в сравнение f(x)≡0(mod p3), имеем
f(x2)+p2t2f '(x2)≡0(mod p3),
откуда, сократив правую, левую части и модуль на p2 , получим
[Здесь f '(x2) не может быть кратно р, если f '(x1) не кратно p, т.к. x2≡x1(mod p), а значит, f '(x2) ≡ f '(x1) (mod p)]
Тогда сравнение имеет одно решение , или, что то же самое, , откуда получаем решение по модулю p3 : x=x3+p3t3.
Продолжим этот процесс до тех пор, пока не будет решено сравнение по модулю pα. Итак, по данному решению сравнения f(x)≡0(mod p) можно найти решение сравнения f(x)≡0(mod pα).
Пример:
Требуется решить сравнение x3+9x—1≡0 (mod 125).
Известно, что сравнение x3+9x—1≡0 (mod 5) имеет одно решение:
x≡2(mod 5), или x=2+5t1.
Поскольку модуль «5» небольшой, а общих подходов к сравнениям высоких степеней мы пока не знаем, то этот корень нашли простым перебором, попутно убедившись в его единственности.
Подставим получившееся x в сравнение по модулю 25:
(2+5t1)3+9(2+5t1)—1≡0 (mod 25).
Решим это сравнение.
8+4·5t1+2·(5t1)2+(5t1)3+18+9·5t1—1≡0 (mod 25)
25+13·5t1+25·(5t13+2 t12) ≡0 (mod 25)
13·5t1≡0 (mod 25)
13t1≡0 (mod 5)
t1≡0 (mod 5)
Или, что то же самое, t1=0+5t2, откуда решение по модулю 25 есть x=2+25t2. Подставим полученное x в сравнение по модулю 125:
(2+25t2)3+9(2+25t2)—1≡0 (mod 125)
Решим это сравнение.
8+4·25t2+2·(25t2)2+(25t1)3+18+9·25t1—1≡0 (mod 125)
25+13·25t2+625·(25t23+2t22) ≡0 (mod 125)
25+13·25t2≡0 (mod 125)
1+13t2≡0 (mod 5)
13t2≡—1 (mod 5)
3t2≡4 (mod 5)
Получили сравнение первой степени. Решим его. Отыщем 3-1(mod 5), для чего, как всегда, воспользуемся расширенным алгоритмом Евклида:
5=3+2
3=2+1
2=1+0
1=3—2=3—(5—3)=2·3—1·5.
2≡3-1(mod 5).
Тогда решением сравнения относительно t2 будет
t2≡2·4 (mod 5)
t2≡3 (mod 5)
Или, что то же самое, t2=3+5t3, откуда решение по модулю 125 есть x=2+25(3+5t3)=2+75+125t3=77+125t3, или, что то же самое,
x≡77 (mod 125).
|
