Teoria_chisel_i_kriptozashita

a = 390 и b = 170

Основная теорема арифметики. Всякое натуральное число N, кро-

ме 1, можно представить как произведение простых множителей

N = p1 · p2 · p3 · p4 · … · pn, n > 1,

(2.1)

причем единственным образом, с точностью до порядка следования сомножителей.

Среди простых сомножителей разложения (2.1) могут быть и равные. Если обозначить различные из них p1, p2,…, pk и допустить, что они встречаются в разложении соответственно α1,α2 ,...,αk раз, то разложение (2.1) преобразуется к виду

N= p1α1 pα2 2 ... pαk k

иназывается каноническим разложением.

Общий делитель нескольких целых чисел — это число, на которое делятся все данные числа без остатка. Наибольший из делителей называется наибольшим общим делителем (НОД). Форма записи НОД такая: (a,b) = c , где c — НОД чисел a и b.

Единица не является ни простым, ни составным числом, так как иначе не удастся доказать основную теорему арифметики.

Взаимно простые числа — это два или несколько целых чисел, наибольший общий делитель которых равен единице, т.е. (a,b) =1, при этом

для любых неотрицательных чисел m и n справедливо: (am ,bn ) =1.

Находят НОД обычно разложением чисел на простые множители с последующим нахождением произведения одинаковых сомножителей. Процесс разложения чисел на простые множители часто занимает слишком много времени. Однако для пары целых чисел можно использовать алгоритм Эвклида, который можно представить следующим образом.

Алгоритм Эвклида. Пусть a и b будут целыми числами и b > 0 (так как (a, b) = (–a, –b), это не умаляет общности). Мы используем повторно свойство делимости следующим образом (пример для приведён справа от главного изложения).

a = bq1 + r2,	0 ≤ r2	< b;	390 = 170 · 2 + 50;
b = r2q2 + r3,	0 ≤ r3	< r2;	170 = 50 · 3 + 2;
r2 = r3q3 + r4,	0 ≤ r4	< r3;	50 = 20 · 2 + 10;
. . .	. . .
rn-2 = br n-1q n-1 + rn, 0 ≤ rn< rn-1;
rn-1 = rnqn,			20 = 10 · 2,

где qi,— частное, а ri — остаток от деления (все ≥ 0).

Остатки r 2, r 3, . . . постоянно уменьшаются, так что в конце концов они должны стать равными нулю. Очевидно, что (a, b) = (a, b) = ( r2, b) =

11

= (r2, r3) = . . . = (rn-1, rn ) = rn, так как в действительности rn | rn-1. Отсюда НОД a и b является последним ненулевым остатком в вышеописанном процессе повторного деления.

Следовательно, наибольший общий делитель (390, 170) = 10. Заме-

тим, чтоэтобылополученобезразложениянамножителикаких-либочисел.

На сегодняшний день алгоритм Эвклида, несмотря на более чем 2000-летнюю историю, остается наиболее эффективным алгоритмом из известных.

Наименьшим общим кратным (НОК) отличных от нуля чисел N1,

N2, …, Nn называют наименьшее положительное число, кратное всем этим числам. НОК обозначают [N1, N2, …, Nn]. Очевидно [a,b] = (aa,bb) . НОК

взаимно простых чисел равно их произведению.

Фи-функция Эйлера ϕ(n) определяет число целых положительных чисел, не превосходящих n и взаимно простых с n .

1,

( p −1), ϕ(n) = ( pα − pα−1 ),

k

∏( piαi − pkαi−1 ),i=1

n =1; n = p; n = pα ;

k

n = ∏piαi .

i=1

Здесь p и pi — простые числа, α и αi — натуральные числа. Свойства фи-функции Эйлера:

1.Мультипликативность:

ϕ(a b) =ϕ(a) ϕ(b) при (a,b) =1.

2.Сумма значений фи-функции Эйлера от всех положительных делителей d числа n равна n :

∑ϕ(d) = n.

d n

Сравнения. Вычеты. Классы вычетов

Пусть n — натуральное число. Если два целых числа a и b при делении на n дают один и тот же остаток, то они называются сравнимыми по модулю n . Отношение сравнимости было введено Карлом Фридри-

хом Гауссом и записывается как

a ≡ b (mod n) .

Читается: a сравнимо с b по модулю n . Все четные (нечетные) числа сравнимы по модулю два. 30 ≡16 ≡ −5 ≡ 23(mod 7) , так как

12

(−5) ≡ 2(mod 7) ≡ 9 ≡16 ≡ 23 ≡ 30.

Из соотношения a ≡ b (mod n) следует отношение делимости n (a − b) , т.е. разность сравнимых по модулю n чисел кратна мо-

дулю n и, следовательно, сравнима с нулем по данному модулю. Из равенства a = b следует сравнение a ≡ b по любому модулю.

У равенств и сравнений имеется много общих свойств:

1)симметрия: a ≡ b b ≡ a;

2)транзитивность: a ≡ b, c ≡ d a ≡ c ;

3)обе части сравнения можно почленно складывать и вычитать:

a ≡ b, c ≡ d a ±c ≡ b ±d ;

4) обе части сравнения можно почленно умножать: a ≡ b, c ≡ d a c ≡ b d .

Замечание. Все сравнения в пунктах 1) — 4) осуществляются по одному и тому же модулю.

Специфические свойства сравнений:

5) обе части сравнения можно разделить на общий делитель, если он взаимно прост с модулем

a b ≡ (b d)(mod n) a ≡ d(mod n) при (b, n) =1;

12 = 6 2 ≡ (2 3)(mod3) 6 ≡ 3(mod3), но при a = 4, b = 3

4 не сравнимо с 2 по модулю 3, так как (3,3) = 3 ≠1;

6) обе части сравнения и модуль можно умножить на одно и то же натуральное число, а также разделить на любой их общий положительный делитель:

a ≡ b(mod n) a d ≡ (b d)(mod n d); 7 ≡ 4(mod3) 14 ≡8(mod 6) ;

a b ≡ (b d)(mod n) a ≡ d(mod (bn, n));

20≡ 32(mod 6) 10 ≡16(mod3);

7)если сравнение имеет место по нескольким модулям, то оно имеет место по модулю, равному общему наименьшему кратному этих модулей:

a ≡ b(mod n )	, n2	]);
1 a ≡ b(mod[n1
a ≡ b(mod n2 )

14 ≡ 2(mod6) 14 ≡ 2(mod12); 14 ≡ 2(mod 4)

8) если сравнение имеет место по mod n, то оно имеет место и по модулю d , равному любому делителю числа n :

13

a ≡ b(mod n); a ≡ b(mod d) , если d n ;

14 ≡ 2(mod3);

14 ≡ 2(mod 6) 14 ≡ 2 ≡ 0(mod 2);

9) общий делитель одной части сравнения и модуля является также делителем второй части сравнения :

a ≡ b(mod n), a = a1 d , n = n1 d b = b1 d ;

15 ≡ 9(mod 6), 3 15, 3 6 3 9 .

Для сравнений справедливы основные законы арифметики:

(a ± b)mod m ≡ [a mod m ± b mod m]mod m (ассоциативность);

(a b)modm ≡[a modm bmodm]modm (коммутативность); [с (a ±b)]mod m ≡[с a mod m ±с b mod m]mod m (дистрибу-

тивность).

Все целые числа, которые при делении на n дают один и тот же остаток r , объединяют в один класс, обозначая его Zi . Очевидно, что при

делении на n возможны n остатков:

0,1, 2, 3, ... , (n −1).

Следовательно, все целые числа можно разбить на n классов:

Z0 , Z1, Z2 , Z3, ... , Zn−1,

которые называются классами вычетов по модулю n . Каждый класс Zi

содержит бесконечное количество сравнимых между собой целых чисел,

объединенных одним соотношением

N = nq +r ; r < n; q = −∞,..., −2, −1,0,1, 2,...,∞.

Замечание. Различные классы вычетов по модулю n не содержат общих элементов и, таким образом, являются непересекающимися классами. Например, при n = 2 все целые числа разбиваются на два непересекающихся класса: четные и нечетные числа. Числа одного и того же класса называются вычетами этого класса.

Полной системой вычетов по модулю n называют набор чисел, со-

держащий по одному вычету из каждого класса. В качестве «представителя» класса можно взять любой вычет класса. Однако чаще всего пользуются наименьшими неотрицательными вычетами, когда в формуле N = nq +r число q = 0 . В этом случае полная система вычетов по моду-

лю n составляется из остатков r : 0,1, 2, 3, ... , (n −1).

Приведенной системой вычетов по модулю n называют набор чи-

сел из полной системы вычетов, которые являются взаимно простыми с модулем n .

14

Так как фи-функция Эйлера ϕ(n) определяет число целых положи-

тельных чисел, не превосходящих n и взаимно простых с n , то можно сказать, что количество чисел в приведенном наборе вычетов по модулю n равняется фи-функции Эйлера ϕ(n) ;

10)слагаемое, стоящее в какой-либо части сравнения, можно переносить в другую часть, переменив его знак на обратный;

11)к каждой части сравнения можно прибавить любое число, кратное модулю;

12)обе части сравнения можно возвести в одну и ту же степень. Если модуль класса вычетов представляет собой простое число, то

множество вычетов по этому модулю образует конечное поле (поле Галуа). Полем называется коммутативное кольцо, в котором у каждого ненулевого элемента есть обратный. Поскольку произведение двух ненулевых элементов поля снова является ненулевым элементом (вследствие отсутствия в поле делителей нуля), операция умножения ассоциативна, имеется нейтральный для операции умножения элемент 1 и каждый ненулевой

элемент а имеет обратный элемент a−1 , то множество отличных от нуля элементов поля образует абелеву группу по умножению. Эта группа называется мультипликативной группой поля.

Ненулевые элементы кольца вычетов Zm тогда и только тогда образуют группу относительно операции умножения по модулю m, когда m — простое число. Следовательно, для простого числа р кольцо Zp является полем. Это конечное поле принято обозначать GF( p) . Его элементы {0, 1,…, (p – 1)} — это всевозможные остатки от деления целых чисел на р, а алгебраические действия с ними — сложение и умножение по модулю р.

Характеристикой поля называется такое наименьшее положительное число k, для которого k a ≡ 0(mod p) , а GP( p). Если такого

элемента не существует, то считается, что характеристика поля равна нулю. Каждое поле Галуа содержит единственное наименьшее подполе, число элементов которого равно простому числу. Следовательно, характе-

ристика каждого поля Галуа является простым числом.

Для конечного поля справедлива малая теорема П. Ферма.

2.1. Малая теорема Ферма. Теорема Эйлера

Малая теорема Ферма. Пусть р — простое число, а — некоторое целое число. Тогда ap ≡ a (mod p). Если p не делит a, тогда ap-1 ≡ 1 (mod p).

Доказательство. Предположим сначала, что p не делит a , так что (а, р) = 1, и рассмотрим р – 1 чисел а, 2а, 3а, . . . , (р – 1)а. Ни одно из них не кратно p ( p | ja означает, что p | j, так как р — простое число и p не де-

15

лит a). Также не найдётся двух чисел, которые конгруэнтны (сравнимы)

по модулю р, так как ja ≡ ka (mod p) означает j ≡ k (mod p). Следовательно, по модулю р эти р – 1 чисел различны и не равны нулю. Итак, числа 1, 2, 3,

. . . , р – 1 должны располагаться в соответствующем порядке. Перемножая их, мы получим

a p−1 1 2 3...( p −1) = a 2a 3a...( p −1)a ≡ (1 2 3...( p −1))(mod p).

Числа 2, 3, . . . , р – 1 все являются взаимно простыми с р и могут быть последовательно сокращены один за другим из этого сравнения. Отсюда следует, что ap–1 ≡ 1 (mod p). Умножение на а даёт ap ≡ a (mod p).

Если, с другой стороны, р | a, тогда р и а оба ≡ 0 (mod p), а из этого следует, что ap ≡ a (mod p).

Обобщением малой теоремы Ферма является теорема Эйлера для составного модуля.

Теорема Эйлера. Пусть n > 0 и предположим, что (a, n) = 1. Тогда aϕ(n) ≡ 1 (mod n), где ϕ(n) — фи-функция Эйлера.

Доказательство. Пусть r1, r2, . . . , rk (k = ϕ(n) ) будут целыми числами Z 1, n и взаимно простыми с n. Рассмотрим a r1, a r2, . . . , a rk . Из представленных членов не найдётся двух, которые сравнимы по mod n

(a ri ≡ a rj, что означает ri ≡ rj (mod n), так как (a, n) = 1) и все они взаимно простые ((a, n) = ( ri , n) = 1, что означает (a ri , n) = 1). Следова-

тельно, среди них существуют ϕ(n) таких, что их наименьшие положи-

тельные вычеты по модулю n должны быть точно числами r1, r2, . . . , rk в соответствующем порядке. Отсюда

r1 r2 . . . rk ≡ ( ar1 a r2 . . . a rk )(mod n),

так что, сокращая ri, так как они взаимно простые с n, мы получим искомое сравнение 1 ≡ a k (mod n).

Функция ϕ(n) является мультипликативной, т.е. если (m, n) = 1, тогда ϕ(mn) =ϕ(m)ϕ(n). Принято, что ϕ(1) =1 и ϕ(2) =1.

Полезной для практического применения модулярной арифметики является китайская теорема об остатках, утверждающая, что можно восстановить целое число из определенного диапазона чисел по множеству его остатков от деления на числа из некоторого набора попарно взаимно простых чисел.

Для нахождения делителей составных чисел используется вероятностный алгоритм Полларда, который рассмотрим для двух случаев.

16

ρ-метод факторизации Полларда. Пусть f(x) = x2 + 1 и запишем f2(x) = f(f(x)), f3(x) = f(f2(x)) и т. д. Пусть ak =f k(1). (Следовательно, а1

= 2, а2 = 5, аk+1 = ak 2 + 1). Конечно, вместо этого f можно использовать другие полиномы. Предположим, что мы хотим представить N в виде сомножителей, т.е. найти простое число р (возможно наименьшее простое число), для которого p | N. Конечно, последовательность {ak}, взятая по модулю р или по модулю N в конце концов будет повторяться, и ожидается, что это повторение будет происходить быстрее по модулю p, чем по модулю N. (Действительно, повторение будет реальной возможностью, если количество членов превзойдёт p ). Следовательно, мы надеемся, что

ai ≡ aj (mod p) для j > i и j не достаточно большое. Заметим, что тогда at ≡ aj-i+t (mod p) для всех t ≥ i. Конечно, мы не можем решить задачу нахождения ai mod p, пока мы не знаем, что собой представляет р, но мы можем решить задачу нахождения ai по модулю N , мы просто запишем

p | ((aj – ai) mod N, N).

(Чтобы не связываться с aj – ai , требуется, чтобы эта разность быстро становилась очень большой).

Проделаем простое усовершенствование: так как i < j, то существует целое число t, для которого i < t ≤ j и (j - i) | t. (Это становится понятным, если задать вопрос, почему должно существовать целое число k, для которого i /(j – i) < k ≤ j /(j – i), и тогда используйте t = k(j – i)). Более того,

at = ak(i-i ) ≡ a(k+1)(j-1) ≡ a(k+2)(j-1) ≡ . . . ≡ a2k(j-1) ≡ a2t (mod p), т.е. вместо

контроля i и j мы должны рассмотреть at и a2t для t = 1, 2, 3, . . . Таким образом, метод заключается в следующем:

Зададим x = a1 = 2, y = a2 = 5.

Заменим х на f (x), y на f (f (y)); таким образом, теперь x = a2 , y =

a4. Найдём (x – y, N).

Повторим: теперь х = a3, у = a6. Найдём (x – y, N).

Продолжаем до тех пор, пока (x – y, N) не станет равным 1 или N. Конечно, х и у сокращаются по модулю N на каждой стадии, используя x:= (x – N) · INT(x / N), и т. д. Заметим, что вышеприведённый метод значительно лучше, чем сохранение ai в массиве, даже учитывая, что ai вычисляется дважды. При этом удаётся избежать проблемы, связанной с большими массивами чисел повышенной точности.

(р – 1) метод факторизации Полларда. Одной из версий этого ме-

тода будет следующая. Предположим, что р — простое число, а k такое,

17

что (р – 1) | k! Это означает, что все простые сомножители числа (р – 1)

будут меньше k . Теорема Ферма утверждает, что 2k! ≡ 1 (mod p). Предположим, что мы хотим разложить на множители данное целое

число N. Возьмём малое целое число, скажем, 2 и вычислим последовательно

21, 22, 26, 224, . . . , 2k! (все по модулю N),

где k является разумно большим (но не слишком большим!). Если р — простой множитель N, тогда, естественно, р является множителем числа

( 2 k! – 1 N, N) и НОД будет скорее р, чем N. (Обозначение х N принято для наименьшего положительного вычета x по модулю N). Этот метод можно проверить на числах, которые являются произведением двух простых чисел. Заметим, что для успеха вычислений мы должны потребовать,

чтобы все простые множители искомого фактора р были бы ≤ k.

Китайская теорема об остатках. Пусть m1, m2, . . . , mr — поло-

жительные числа, причем, каждая пара взаимно простая: (mi, mj) = 1 для i ≠ j. Тогда система сравнений

x ≡ a1 (mod m1), x ≡ a2 (mod m2), . . . , x ≡ aк (mod mк)

имеет единственное решение — сравнение по модулю произведения m1 m2

. . . mr.

Доказательство. Существование решения может быть доказано индукцией или следующим образом. Пусть ki для i = 1, . . . , r будет произведением всех положительных чисел m за исключением mi. Конечно, (ki, mi) = 1, так что ki имеет обратное число ni по модулю mi. Тогда

x = a1 k1 n1 + a2 k2 n2 + . . . + ar kr nr

есть искомое решение. Например, m1 является сомножителем n2, . . . , nr и k1 n1 ≡ 1 (mod m1), Отсюда x ≡ a1 (mod m1). Таким же образом доказываются другие сравнения.

Порядком числа а по модулю n, если (a, n) = 1, называется наименьшее целое k > 0 такое, что ak ≡ 1 (mod n). Это записывается как k = ordn a и произносится, что а имеет порядок k по модулю n. Естественно, что ordn a ≤ ϕ(n) . Заметим, что если (a, n) > 1 и k > 0, то невозможно

для ak быть сравнимым с 1 (mod n). Если а имеет порядок k mod n, тогда в некоторых книгах используют выражение “а является показателем k по модулю n”.

Предположим (a, n) = 1. Тогда ak ≡ 1 (mod n), если ordn a | k. Отсюда получим, что степень а, которая сравнима с 1, не только ≥ ordn a , но

18

ordn a | ϕ(n)

точно кратна этому порядку. В особенности это нужно помнить, когда и если р — простое число, то ordn a | (p – 1).

Доказательство. Предположим, что аk ≡ 1, где k > 0 и пусть

k = q ordn a + r, где 0 ≤ r ≤ ordn a . Тогда, по модулю n,

1 ≡ ak = (aordna )q ar ≡ ar .

Отсюда и из определения порядка следует, что r = 0 как число наименьшей положительной степени а, которое сравнимо с единицей.

Число а, для которого (a, n) = 1 и ordn a = ϕ(n) называется при-

митивным корнем по модулю n. Таким образом, если модуль n делится на два различных простых нечётных числа, то для него не существует примитивного корня.

Определим основные свойства примитивных корней. Если предположить, что g является примитивным корнем по модулю n, то выполняются следующие свойства:

а) для любых целых чисел r и s,

g r ≡ g s (mod n) r ≡ s (mod ϕ(n) );

б) ϕ(n) , числа 1, g, g2, . . . , g ϕ(n) - 1 — все являются различными по модулю n. Они, следовательно, по модулю n точно являются числами, взаимно простыми с n; положительные вычеты являются точно положи-

тельными целыми числами ≤ (n – 1) и взаимно простыми с n.

Доказательство

а) предположим, что r ≥ s. Тогда g r-s g s ≡ gs (mod n), и так как

(g, n) = 1, то можно сократить g s из обеих частей, чтобы получить g r–s ≡ 1 (mod n). Таким образом, ϕ(n) = ord n g | (r – s), что даёт искомый ре-

зультат. Обратное утверждение также действительно; б) это действительно применение пункта (а); так как нет двух степе-

ней 0, 1, 2, . . . , ϕ(n) – 1, которые могли быть сравнимыми по модулю

ϕ(n) .

В теоретико-групповом смысле пункт (б) прямо утверждает, что примитивный корень является генератором циклической группы, состоя-

щей из вычетов по модулю n, которые взаимно просты с n.

Теорема. Предположим, что а является примитивным корнем по модулю 2k для некоторого k ≥ 3. Тогда а является также примитивным корнем по модулю 2k–1. Следовательно, не существуют примитивные корни по модулю 2k для k ≥ 3.

19

Доказательство. Очевидно, что а является нечётным числом. Мы имеем а2k −2 ≡1(mod 2k−1), согласно теореме Эйлера, так как ϕ(2k −1) = 2k −2 . Предположим, что в действительности порядок а по мо-

дулю 2k-1 меньше, чем 2k-2. Следовательно, степень числа 2 будет меньше,

чем (k – 2) :

а2r ≡1(mod 2k −1) для некоторого r			(0 ≤ r ≤ k – 3). Последовательное
возведение в квадрат показывает, что а2k −3				≡1(mod2k −1) .
Запишем выражение		а2k −3 = 2k−1b		для целого числа b. Тогда
а2k −3	= 2k −1b + 2 и,	перемножая	их	между собой, получим
а2k −2	−1 ≡ 0(mod2k ) . Однако это противоречит предположению, что а

является примитивным корнем по модулю 2k. Это показывает, что порядок а равняется ϕ(2k −1) = 2k −2 , что и требовалось доказать.

Дискретный логарифм — это функция, обратная возведению в степень в арифметике классов вычетов.

Известно [5], что для простого числа р степени числа а с показателями от 1 до (р – 1) порождают все целые числа в ряду от 1 до (р – 1) в точности по одному разу. Любое целое число b можно представитьвформе

b≡ r(mod p), где 1 ≤ r ≤ ( p −1)

вклассах вычетов. Отсюда вытекает, что для любого целого числа и любого первообразного корня а простого числа р можно найти ровно один показатель степени i, для которого

b ≡ аi (mod p) , где 1 ≤ i ≤ ( p −1) .

Значение показателя степени i, называют индексом числа b по моду-

лю р при основании а, или дискретным логарифмом.

Для дискретного логарифма принята форма записи indа, р(b) и справедливы следующие выражения:

indа, р(1) = 0 , поскольку а0 mod p =1mod p =1; indа, р(а) =1, поскольку а1 mod p = аmod p .

20