Скачать .docx Скачать .pdf

Дипломная работа: Теория остатков

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

Учреждение образования

«Гомельский государственный университет

имени Франциска Скорины »

Математический факультет

Кафедра алгебры и геометрии

Допущена к защите

Зав. кафедрой _________ Шеметков Л.А.

«_____» ____________ 2006 г.

ТЕОРИЯ ОСТАТКОВ

ДИПЛОМНАЯ РАБОТА

Исполнитель:

студентка группы М-52 ____________ Клименко Ю.

Научный руководитель:

к.ф-м.н., доцент кафедры

алгебры и геометрии ____________ Подгорная В.

Рецензент:

ст. преподаватель

кафедры высшей

математики ____________ Курносенко Н.

Гомель 2008

Содержание

Введение. 3

1 Алгоритм Евклида. 4

1.1 Определения алгоритма. 4

1.2 Алгоритм Евклида. 5

1.3 Применения алгоритма Евклида. 12

2 Делимость в кольцах. 17

2.1 Область целостности. 17

2.2 Кольцо частных. 19

2.3 Евклидовы кольца. 21

3 Сравнения и арифметика остатков. 27

4 Функция Эйлера. 41

5 Китайская теорема об остатках. 53

Заключение. 62

Список использованных источников. 63

Введение

История арифметики остатков начинается с исследований К.Ф. Гаусса, который впервые стал рассматривать сравнения. В дальнейшем была обнаружена связь теории сравнений с астрономическими задачами (китайская теорема об остатках). В результате многочисленных исследований теория остатков была распространена на кольца произвольной природы. В последнее время обнаружилось приложение этой теории в криптографии. В дипломной работе изложена теория остатков на современном алгебраическом языке.

Дипломная работа состоит из пяти разделов.

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

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

В третьем разделе изложены теории вычетов по модулю и теория сравнений. Приведено применении теории остатков в криптографии (алгоритм RSA).

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

В пятом разделе изложена китайская теорема об остатках для колец.

1 Алгоритм Евклида

1.1 Определения алгоритма

Единого «истинного» определения понятия «алгоритм» нет.

«Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.» (А. Колмогоров)

«Алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.» (А. Марков)

«Алгоритм есть формализованная последовательность действий (событий). Алгоритм может быть записан словами и изображен схематически. Практически любое неслучайное повторяемое действие поддается описанию через алгоритм.»

«Алгоритм — это система операторов, взятых из множества операторов некоторого исполнителя, которая полностью определяет некоторый класс алгоритмических процессов, то есть процессов, которые:

1. дискретны;

2. детерминированы;

3. потенциально конечны;

4. преобразовывают некоторые конструктивные объекты.

Между операторами алгоритма и операциями (элементарными действиями) алгоритмического процесса существует гомоморфное соответствие. Поэтому алгоритм следует также считать моделью алгоритмического процесса». (А. Копаев)

Формальные признаки алгоритмов

Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:

· детерминированность — определённость. В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа.

· понятность — алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд.

· завершаемость (конечность) — при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0.

· массовость — алгоритм должен быть применим к разным наборам исходных данных.

Современное формальное определение алгоритма было дано в 30-50-х гг. XX века в работах Тьюринга, Поста, Чёрча (тезис Чёрча — Тьюринга), Н. Винера, А. А. Маркова.

1.2 Алгоритм Евклида

Определение. Число d Z , делящее одновременно числа а , b , c , ... , k Z , называется общим делителем этих чисел. Наибольшее d с таким свойством называется наибольшим общим делителем. Обозначение: d = ( a , b , c , ..., k ) .

Теорема . Если ( a , b ) = d , то найдутся такие целые числа u и v , что d = au + bv .

Доказательство . Рассмотрим множество P = { au + bv u,v Z }. Очевидно, что P Z , а знатоки алгебры могут проверить, что P – идеал в Z . Очевидно, что a , b , 0 P . Пусть x , y P и y 0 . Тогда остаток от деления x на y принадлежит P . Действительно:

x = yq + r , 0 r < y ,

r = x – yq = ( au 1 + bv 1 ) – ( au 2 + bv 2 ) q = a ( u 1 u 2 q )+ b ( v 1 v 2 q ) P .

Пусть d P - наименьшее положительное число из P (призадумайтесь, почему такое имеется!). Тогда а делится на d . В самом деле, a = dq + r 1 , 0 r 1 < d , a P , d P , значит r 1 P , следовательно r 1 = 0. Аналогичными рассуждениями получается, что b делится на d , значит d - общий делитель a и b .

Далее, раз d P , то d = au 0 + bv 0 . Если теперь d 1 - общий делитель a и b , то d 1 | ( au 0 + bv 0 ), т.е. d 1 | d . Значит d d 1 и d - наибольший общий делитель.

Определение. Целые числа a и b называются взаимно простыми, если (a , b ) = 1.

Вспоминая свойство 1 из предыдущего пункта, легко заметить, что два числа a и b являются взаимно простыми тогда и только тогда, когда найдутся целые числа u и v такие, что au + bv = 1.

Пусть даны два числа a и b ; a 0, b 0, считаем, что a > b . Символом := в записи алгоритма обозначаем присваивание. Алгоритм:

1. Ввести a и b .

2. Если b = 0 , то Ответ: а . Конец .

a = bq 1 + r 1

b = r 1 q 2 + r 2

r 1 = r 2 q 3 + r 3

r 2 = r 3 q 4 + r 4

0 r 1 < b

0 r 2 < r 1

0 r 3 < r 2

0 r 4 < r 3

· · · · · · · · ·

r n -3 = r n -2 q n -1 + r n -1

r n -2 = r n -1 q n + r n

r n -1 = r n q n +1

0 r n -1 < r n -2

0 r n < r n -1

r n +1 = 0

3. Заменить r := "остаток от деления а на b ", а := b , b := r .

4. Идти на 2.

В современной буквенной записи, алгоритм Евклида выглядит так: a > b; a, b Z .

Имеем: b > r 1 > r 2 >... > r n > 0, следовательно процесс оборвется максимум через b шагов. Очень интересный и практически важный народохозяйственный вопрос о том, когда алгоритм Евклида работает особенно долго, а когда справляется с работой молниеносно, мы рассмотрим чуть позже. Давайте сейчас покажем, что r n = ( a , b ). Просмотрим последовательно равенства сверху вниз: всякий делитель а и b делит r 1 , r 2 ,..., r n . Если же просматривать эту цепочку равенств от последнего к первому, то видно, что r n | r n -1 , r n | r n -2 , и т.д., т.е. r n делит а и b . Поэтому r n - наибольший общий делитель чисел а и b .

Как и всякая добротно выполненная работа, алгоритм Евклида дает гораздо больше, чем от него первоначально ожидалось получить. Из его разглядывания ясно, например, что совокупность делителей а и b совпадает с совокупностью делителей ( a , b ). Еще он дает практический способ нахождения чисел u и v из Z (или, если угодно, из теоремы пункта 2) таких, что r n = au + bv = ( a, b ).

Действительно, из цепочки равенств имеем:

r n = r n -2 - r n -1 q n = r n -2 - ( r n -3 - r n -2 q n -1 ) q n = ...

(идем по цепочке равенств снизу вверх, выражая из каждого следующего равенства остаток и подставляя его в получившееся уже к этому моменту выражение)

... = au + bv = ( a , b ).

Пример. Пусть а = 525, b = 231. (ниже приводится запись деления уголком, и каждый раз то, что было в уголке, т.е. делитель, приписывается к остатку от деления с левой стороны, а остаток, как новый делитель, берется в уголок)

_

_42|

42 |

0

_

63|

42 |

21

2

_

231|

189 |

42

1

525|

462 |

63

3

231

2

Запись того же самого в виде цепочки равенств:

525 = 231 · 2 + 63

231 = 63 · 3 + 42

63 = 42 · 1 + 21

42 = 21 · 2

Таким образом, (525, 231) = 21. Линейное представление наибольшего общего делителя:

21 = 63 - 42 · 1 = 63 - (231 - 63 · 3) · 1 =

= 525 - 231 · 2 - (231 - (525 - 231 · 2) · 3) =

= 525 · 4 - 231 · 9,

и наши пресловутые u и v из Z равны, соответственно, 4 и - 9.

Приступим теперь к исполнению второй части названия этого пункта - анализу алгоритма Евклида. Нас будет интересовать наихудший случай - когда алгоритм работает особенно долго? Спросим точнее: какие два наименьших числа надо засунуть в алгоритм Евклида, чтобы он работал в точности заданное число шагов? Ответ на этот вопрос дает

Теорема (Ламэ, 1845 г.). Пусть n N , и пусть a > b > 0 такие, что алгоритму Евклида для обработки а и b необходимо выполнить точно n шагов (делений с остатком), причем а - наименьшее с таким свойством. Тогда а = n +2 , b = n +1 , где k - k- ое число Фибоначчи.

Следствие. Если натуральные числа a и b не превосходят N N , то число шагов (операций деления с остатком), необходимых алгоритму Евклида для обработки a и b не превышает log Ф ( 5 N ) - 2, где - верхнее целое , = (1 + 5)/2 - больший корень характеристического уравнения последовательности Фибоначчи.

Доказательство. Максимальное число шагов n достигается при а = n +2 , b = n +1 , где n - наибольший номер такой, что n +2 < N . Рассматривая формулу для n -ого члена последовательности Фибоначчи, легко понять, что n +2 - ближайшее целое к (1/ 5) n +2 . Значит (1/ 5) n +2 < N , следовательно, n +2 < log Ф ( 5 N ), откуда моментально даже n < log Ф ( 5 N ) - 3 (именно "минус три", ведь рассматривается верхнее целое).

log Ф ( 5 N ) 4,785 · lg N + 1,672, поэтому, например, с любой парой чисел, меньших миллиона, алгоритм Евклида разбирается не более, чем за 4,785 · 6 + 1,672 - 3 = 31 - 3 = 28 шагов.

Листинг алгоритма Евклида на языке С

// Обобщенный алгоритм Евклида для поиска наибольшего общего // делителя gcd = НОД(u,v) целых положительных чисел u и v // и коэффициентов a и b уравнения a*u + b*v = gcd// Все числа полагаются типа long // Подстановки упрощающие запись исходного текста#define isEven(x) ((x & 0x01L) == 0) // x - четное?#define isOdd(x) ((x & 0x01L)) // x - нечетное?#define swap(x,y) (x ^= y, y ^= x, x ^= y) // обмен значений x и y void GenEuclid(long *u, long *v, long *a, long *b, long *gcd){int k; // Параметр цикловlong a1, b1, g1; // Вспомогательные переменные // Алгоритм предполагает, что u > v, если u < v, то они переставляютсяif (*u < *v) swap(*u, *v);// Если u = n * 2^k1 или v = m * 2^k2, то перед поиском НОД// производим сокращение u = u/(2^k), v = v/(2^k),// где k - минимальное из k1, k2. Показатель k запоминаем.for (k = 0; isEven(*u) && isEven(*v); ++k){ *u >>= 1; *v >>= 1;}// Задание начальных значений*a = 1; *b = 0; *gcd = *u; a1 = *v; b1 = *u - 1; g1 = *v;do { do { if (isEven(*gcd)){ if (isOdd(*a) || isOdd(*b)){ *a += *v; *b += *u; } *a >>= 1; *b >>= 1; *gcd >>= 1; } if (isEven(g1) || *gcd < g1){ swap(*a, a1); swap(*b, b1); swap(*gcd, g1); } } while (isEven(*gcd)); while(*a < a1 || *b < b1){ *a += *v; *b += *u; } *a -= a1; *b -= b1; *gcd -= g1;} while (g1 > 0);while (*a >= *v && *b >= *u){ *a -= *v; *b -= *u;}// производим умножение коэффициентов уравнения // на сокращенный ранее множитель 2^k*a <<= k; *b <<= k; *gcd <<= k;}

Расширенный алгоритм Евклида и соотношение Безу

Формулы для ri могут быть переписаны следующим образом:

r 1 = a + b ( - q 0 )

r 2 = br 1 q 1 = a ( − q 1 ) + b (1 + q 1 q 0 )

(a ,b ) = rn = as + bt

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

1.3 Применения алгоритма Евклида

Пусть требуется решить линейное диофантово уравнение:

ax + by = c ,

где a , b , c Z ; a и b - не нули.

Попробуем порассуждать, глядя на это уравнение.

Пусть ( a , b ) = d . Тогда a = a 1 d ; b = b 1 d и уравнение выглядит так:

a 1 d· x + b 1 d· y = c , т.е. ( a 1 x + b 1 y ) = c .

Теперь ясно, что у такого уравнения имеется решение (пара целых чисел x и y ) только тогда, когда d | c . Пусть d | c . Поделим обе части уравнения на d , и всюду далее будем считать, что ( a , b ) = 1.

Рассмотрим несколько случаев.

Случай 1. Пусть c = 0, уравнение имеет вид ax + by = 0 - " однородное линейное диофантово уравнение".

x = -

b

a

y .

Так как x должен быть целым числом, то y = at , где t - произвольное целое число (параметр). Значит x = - bt и решениями однородного диофантова уравнения ax + by = 0 являются все пары вида {- bt , at }, где t = 0; ±1; ±2;... Множество всех таких пар называется общим решением линейного однородного диофантова уравнения, любая же конкретная пара из этого множества называется частным решением.

Случай 2. Пусть теперь c  0. Этот случай закрывается следующей теоремой.

Теорема. Пусть ( a , b ) = 1, { x 0 , y 0 } - частное решение диофантова уравнения ax + by = c . Тогда его общее решение задается формулами:







x = x 0 - bt

y = y 0 + at .

Таким образом, и в теории линейных диофантовых уравнений общее решение неоднородного уравнения есть сумма общего решения соответствующего однородного уравнения и некоторого (любого) частного решения неоднородного уравнения.

Доказательство. То, что правые части указанных в формулировке теоремы равенств действительно являются решениями, проверяется их непосредственной подстановкой в исходное уравнение. Покажем, что любое решение уравнения ax + by = c имеет именно такой вид, какой указан в формулировке теоремы. Пусть { x * , y *} - какое-нибудь решение уравнения ax + by = c . Тогда ax * + by * = c , но ведь и ax 0 + by 0 = c . Следуя многолетней традиции доказательства подобных теорем, вычтем из первого равенства второе и получим:

a ( x *- x 0 ) + b ( y *- y 0 ) = 0

- однородное уравнение. Далее, глядя на случай 1, рассмотрение которого завершилось несколькими строками выше, пишем сразу общее решение: x *- x 0 = - bt , y *- y 0 = at , откуда моментально, используя навыки третьего класса средней школы, получаем:







x * = x 0- bt ,

y * = y 0 + at.

Как же искать то самое частное решение { x 0 , y 0 }. Мы договорились, что ( a , b ) = 1. Это означает, что найдутся такие u и v из Z , что au + bv = 1, причем эти u и v мы легко умеем находить с помощью алгоритма Евклида. Умножим теперь равенство au + bv = 1 на c и получим: a ( uc ) + b ( vc ) = c , т.е. x 0 = uc , y 0 = vc .

Определение. Цепной (или, непрерывной) дробью называется выражение вида:


(Бедные наборщики в докомпьютерные времена буквально стрелялись, когда им приходилось набирать в книжках подобные многоэтажные выражения.) Договоримся называть числа q 1 , q 2 ,..., q n ,... - неполными частными и считаем, что q 1 Z , а q 2 ,..., q n ,... N . Числа называются подходящими дробями цепной дроби .

1 = q 1 , 2 , = q 1 +

1

q 2

, 3 = q 1 +

1

q 2 +

1

q 3

, и т. д.

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

Пусть Q , = a / b ; a , b Z , b > 0. Оказывается, что при этих условиях, указанный выше процесс разложения числа в цепную дробь всегда конечен и выполним с помощью достопочтенного и любимого нами алгоритма Евклида. Действительно, отдадим алгоритму числа a и b , и внимательно посмотрим, что получится.


a = bq 1 + r 1

т.е.

a

b

= q 1 +

1

b / r 1

b = r 1 q 2 + r 2

т.е.

b

r 1

= q 2 +

1

r 1 / r 2

r 1 = r 2 q 3 + r 3

т.е.

r 1

r 2

= q 3 +

1

r 2 / r 3

. . . . . . .

r n -2 = r n -1 q n + r n

т.е.

r n -2

r n -1

= q n +

1

r n -1 / r n

r n -1 = r n q n +1

т.е.

r n -1

r n

= q n +1 .

Значит:

где q 1 , q 2 ,..., q n +1 - как раз те самые неполные частные из алгоритма Евклида (вот откуда название этих чисел в цепных дробях). Таким образом, в случае рационального числа a / b , процесс разложения в цепную дробь конечен и дробь содержит не более b этажей. Наиболее одаренные читатели в этом месте уже поняли, что основная теорема о цепных дробях для рациональных чисел оказалась почти доказана (не доказали только единственность разложения, но она в случае конечных цепных дробей почти очевидна - приравняйте две цепных дроби и, рассуждая по индукции, получите, что у равных дробей совпадают все неполные частные).

Пример. П ример заимствован из книги И. М. Виноградова "Основы теории чисел". Итак: разложить 105/38 в цепную дробь.

Включаем алгоритм Евклида:

105 = 38 · 2 + 29

38 = 29 · 1 + 9

29 = 9 · 3 + 2

9 = 2 · 4 + 1

2 = 1 · 2

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

2 Делимость в кольцах

2.1 Область целостности

Область целостности (или целостное кольцо , или область цельности ) — понятие абстрактной алгебры: ассоциативное коммутативное кольцо с единицей, в котором 0≠1 и произведение двух ненулевых элементов не равно нулю. Условие 0≠1 исключает из рассмотрения тривиальное кольцо {0}.

Эквивалентное определение: область целостности — это ассоциативное коммутативное кольцо, в котором нулевой идеал {0} является простым. Любая область целостности является подкольцом своего поля частных.

Примеры

· Простейший пример области целостности — кольцо целых чисел .

· Любое поле является областью целостности. С другой стороны, любая артинова область целостности есть поле. В частности, все конечные области целостности суть конечные поля.

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

· Множество действительных чисел вида есть подкольцо поля , а значит, и область целостности. То же самое можно сказать про множество комплексных чисел вида a + bi , где a и b целые (множество Гауссовых целых).

· Пусть U — связное открытое подмножество комплексной плоскости . Тогда кольцо H (U ) всех голоморфных функций будет целостным. То же самое верно для любого кольца аналитических функций, определённых на связном подмножестве аналитического многообразия.

· Если K — коммутативное кольцо, а I — идеал в K , то факторкольцо K / I целостное тогда и только тогда, когда I — простой идеал.

Делимость, простые и неприводимые элементы

Пусть a и b — элементы целостного кольца K . Говорят, что «a делит b » или «a — делитель b » (и пишут ), если и только если существует элемент такой, что ax = b .

Делимость транзитивна: если a делит b и b делит c , то a делит c . Если a делит b и c , то a делит также их сумму b + c и разность b - c .

Для кольца K с единицей элементы , которые делят 1, называются делителями единицы , а иногда и просто единицами . Они и только они, обратимы в K . Единицы делят все остальные элементы кольца.

Элементы a и b называются ассоциированными , если a делит b и b делит a. a и b ассоциированны тогда и только тогда, когда a = b * e , где e — обратимый элемент.

Необратимый элемент q целостного кольца называется неприводимым , если его нельзя разложить в произведение двух необратимых элементов.

Ненулевой необратимый элемент p называется простым , если из того, что , следует или . Это определение обобщает понятие простого числа в кольце , однако учитывает и отрицательные простые числа. Если p — простой элемент кольца, то порождаемый им главный идеал (p ) будет простым. Любой простой элемент неприводим, но обратное верно не во всех областях целостности.

Свойства

· Любое поле, а также любое кольцо с единицей, содержащееся в некотором поле, является областью целостности.

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

· Если A ― область целостности, то кольцо многочленов и кольцо формальных степенных рядов над A также будут областями целостности.

· Если A ― коммутативное кольцо с единицей и I ― некоторый идеал в A , то кольцо A / I является областью целостности тогда и только тогда, когда идеал I прост.

· Кольцо будет областью целостности тогда и только тогда, когда его спектр есть неприводимое топологическое пространство.

· Прямое произведение колец никогда не бывает областью целостности, так как единица первого кольца, умноженная на единицу второго кольца, даст 0.

· Тензорное произведение целостных колец тоже будет целостным кольцом.

Вариации и обобщения

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

2.2 Кольцо частных

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

Мультипликативной системой в кольце R называется подмножество S в R , содержащее 1, не содержащее нуля и замкнутое по умножению (в кольце R ). Для мультипликативной системы S множество образует идеал в кольце R . В случае, когда множество S не содержит делителей нуля кольца R , идеал IS = (0) и система S называется регулярной. Если R - целостное кольцо, в ней всякая мультипликативная система регулярна.

Элементами кольца частных кольца R по мультипликативной системе S являются формальные дроби вида r/s , где r - произвольный элемент R , а s - элемент множества S . Две дроби r 1 / s 1 и r 2 / s 2 считаются эквивалентными (представляют один и тот же элемент кольца частных), если . Операции сложения и умножения определяются как обычно:

Проверяется, что если в сумме или произведении дроби заменить на эвивалентные, новый результат будет выражаться дробью, эквивалентной прежней. С такими операциями множество S − 1 R приобретает структуру коммутативного кольца с единицей. Нулём в нём служит дробь 0/1 , единицей - дробь 1/1 .

Свойства

· Кольцо частных имеет каноническую структуру алгебры над кольцом R, так как вместе с кольцом S-1 R сразу определён и канонический гомоморфизм кольца R в S-1 R (каждому элементу r из R соответствует дробь r/1 ). Ядром этого гомоморфизма является идеал IS . В случае, если система S регулярна (не содержит делителей нуля), этот гомоморфизм инъективен, и кольцо R , таким образом, вложено в своё кольцо частных по системе S . При этом дробь r/s является единственным решением уравнения sx = r .

· Если оба элемента r и s принадлежат S , тогда в кольце S-1 R содержатся дроби r/s и s/r . Их произведение равно 1, следовательно, они обратимы. Обратно: каждый обратимый элемент кольца S-1 R имеет вид er/s , где r и s принадлежат S, а e - обратимый элемент кольца R .

· Если кольцо R не имеет (собственных) делителей нуля (т.е. это целостное кольцо), множество всех ненулевых элементов образует мультипликативную систему S . Соответствующее кольцо частных будет полем, которое называется полем частных целостного кольца. Отсюда следует, что каждое целостное кольцо вложено в некоторое поле, а именно - в своё поле частных .

· Если R - евклидово кольцо, то всякое кольцо, промежуточное между R и его полем частных, является кольцом частных кольца R по некоторой мультипликативной системе S .

· Если система S состоит из одних только обратимых элементов кольца R , канонический гомоморфизм кольца R в S-1 R превращается в изоморфизм, так как каждая дробь r/s оказывается сократимой в кольце R .

· Если кольцо R ' является подкольцом кольца R , то множество всех элементов из R ', обратимых в кольце R , образует регулярную мультипликативную систему S в кольце R' . Тогда каждой дроби r/s однозначно соответствует некоторый элемент кольца R . Множество всех таких элементов кольца R образует кольцо частных кольца R' в кольце R .

Примеры

· Полем частных кольца целых чисел является поле рациональных чисел .

· Степени числа 10 в образуют мультипликативную систему. Кольцом частных по ней будет кольцо конечных десятичных дробей.

· Полем частных кольца многочленов k [X 1 ,X 2 ,...,Xn ] над полем k будет поле рациональных функций k (X 1 ,X 2 ,...,Xn ).

· Пусть — простой идеал в R . Тогда дополнение к нему - мультипликативная система. Кольцо частных по ней называется локализацией кольца R по простому идеалу .

· Чётные числа в образуют простой идеал. Локализацией кольца по нему будет кольцо рациональных дробей, у которых в несократимом виде знаменатель — нечётное число.

2.3 Евклидовы кольца

Неформально, евклидово кольцо — в абстрактной алгебре — кольцо, в котором «работает» алгоритм Евклида.

Евклидово кольцо — это область целостности R , для которой определена евклидова функция (евклидова норма ) , причём , и возможно деление с остатком, по норме меньшим делителя, то есть для любых имеется представление a = bq + r , для которого d (r ) < d (b ).

Замечание

Часто на евклидову норму накладывают дополнительное ограничение: для любых a и ненулевых b из кольца R . Если на R задана норма, не удовлетворяющая этому условию, её можно поправить, переопределив:

Такая норма нужному неравенству удовлетворяет, однако прежний алгоритм деления с остатком уже не годится — его тоже надо поправлять. Пусть таков, что d '(b ) = d (bx ). Разделим с остатком ax на bx : ax = bxq ' + r 'x , где r ' = abq ' и d (r 'x ) < d (bx ) = d '(b ). Так как из определения , мы получили представление a = bq ' + r ' с d '(r ') < d '(b ), что и требовалось.

Тем не менее бонусов от такой нормы не так много — все обратимые элементы имеют одно и то же значение нормы, причём минимальное из всех (конечных), собственные делители элемента a имеют меньшее значение нормы, а также упрощается непосредственное доказательство факториальности евклидовых колец (без ссылки на факториальность колец главных идеалов, доказательство чего требует применения трансфинитной индукции). Основные же свойства евклидовых колец остаются в силе и без этого дополнительного свойства.

Примеры

· Кольцо целых чисел Z . Пример евклидовой функции — абсолютное значение .

· Кольцо целых гауссовых чисел Z [i] (где i — мнимая единица, i 2 = − 1) с нормой d (a + ib ) = a 2 + b 2 — евклидово.

· Произвольное поле K является евклидовым кольцом с нормой, равной 1 для всех элементов, кроме 0.

· Кольцо многочленов в одной переменной K [x ] над полем K . Пример евклидовой функции — степень deg.

· Кольцо формальных степенных рядов K [[x ]] над полем K является евклидовым кольцом. Норма степенного ряда — номер первого ненулевого коэффициента в нём (для нулевого ряда норма равна минус бесконечности).

· Обобщая предыдущий пример, всякое локальное кольцо является евклидовым, если в нём максимальный идеал является главным и пересечение всех его степеней состоит только из нуля. Норма обратимого элемента — 0, необратимого ненулевого — равна максимальной степени максимального идеала, которая содержит данный элемент, а норма нуля — минус бесконечность.

· Кольцо функций H(K) , голоморфных на связном компакте K в C (каждая из них должна быть голоморфна в какой-нибудь окрестности этого компакта; две такие функции считаются равными в H(K) , если они совпадают в некоторой окрестности K ), тоже евклидово. За норму ненулевой функции принимается число нулей (с учётом кратности), которые она принимает на K .

· Счётное пересечение евклидовых колец (подколец в каком-нибудь кольце) не обязано быть евклидовым кольцом (и даже нётеровым или факториальным). Например, кольцо функций H(D) , голоморфных в открытом круге D , является пересечением евклидовых колец функций H(K) , голоморфных на замкнутых кругах K , содержащихся внутри D (см. предыдущий пример), однако оно ни нётерово, ни факториально, соответственно, и неевклидово.

· Кольцо частных S-1 R евклидова кольца R по мультипликативной системе S тоже является евклидовым. Нормой дроби x из S-1 R принимается

, где dR — евклидова норма в R , а dS — норма в S-1 R .

Деление с остатком определяется так. Пусть есть две ненулевые дроби x = r / t и y из S-1 R . По определению нормы в S-1 R существует элементы u в R и s в S , такие что y = u / s и dS (y ) = dR (u ). Произведём деление с остатком в кольце R элементов rs и u :

rs = uq + r' , так что dR (r ') < dR (u ). Тогда r / t = (u / s )(q / t ) + r ' / ts . Из построения следуют неравенства .

· Евклидовыми являются кольца конечных двоичных и конечных десятичных дробей, так как они являются кольцами частных кольца целых чисел Z .

· Евклидовыми являются кольца рациональных функций над полем C с фиксированными полюсами, так как такие кольца являются кольцами частных кольца многочленов C [x ].

Алгоритм Евклида

В евклидовом кольце осуществим алгоритм Евклида нахождения наибольшего общего делителя двух чисел (элементов). Пусть изначально даны два элемента a0 и a1 , причём и . Деление с остатком даёт элемент a 2 = a 0a 1 q 1 с d (a 2 ) < d (a 1 ). Если он не равен нулю, можно опять применить деление с остатком, и получить элемент a 3 = a 1a 2 q 2 , и т. д. Таким образом генерируется цепочка значений с . Однако эта цепочка прерывается, поскольку всякое число из может строго превосходить лишь конечное количество других таких чисел. Это означает, что при некотором n остаток an+1 равен нулю, а an не равен, он и есть НОД элементов a0 и a1 . Следовательно, в евклидовом кольце гарантировано завершение алгоритма Евклида. Строго говоря, именно в евклидовых кольцах и возможна реализация алгоритма Евклида.

Свойства евклидовых колец

· В евклидовом кольце каждый идеал — главный (в частности, все евклидовы кольца нётеровы).

o Пусть I — произвольный идеал в евклидовом кольце. Если он содержит лишь 0, — он главный. В противном случае среди его ненулевых элементов найдётся элемент f с минимальной нормой (принцип минимума для натуральных чисел). Он делит все остальные элементы идеала: Если g — произвольный элемент идеала I , представим его в виде g = fq + r с d(r)<d(f) . Тогда r - тоже элемент идеала I и он обязан быть нулём, так как его норма меньше, чем у f . Следовательно, идеал I содержится в идеале (f) . С другой стороны, всякий идеал, содержащий элемент f , содержит идеал (f) . Значит, I = (f) - главный идеал.

· Каждое евклидово кольцо факториально, то есть каждый элемент представим конечным произведением простых элементов, и притом однозначно (с точностью до их перестановки и умножения на обратимые элементы). Факториальность - общее свойство всех колец главных идеалов.

· Каждое евклидово кольцо R целозамкнуто, то есть если дробь , является корнем многочлена со старшим коэффициентом, равным 1, тогда a делится на b . Целозамкнутость - общее свойство всех факториальных колец.

Свойства модулей над евклидовым кольцом

Пусть R - евклидово кольцо. Тогда конечнопорождённые R -модули обладают следующими свойствами:

· Всякий подмодуль N конечнопорождённого R -модуля M конечно порождён. (следствие нётеровости кольца R )

· Ранг подмодуля N не превосходит ранга модуля M . (следствие главности идеалов в R )

· Подмодуль свободного R -модуля свободен. (то же)

· Гомоморфизм конечнопорождённых R -модулей всегда приводится к нормальной форме. То есть существуют образующие (базис, если модуль свободен) модуля N , образующие (базис) модуля M , номер и - элементы кольца R , такие что ai делит ai + 1 и при i>k Aui = 0, а при остальных — Aui = ai vi . При этом коэффициенты определены однозначно с точностью до умножения на обратимые элементы кольца R . (Тут прямо задействована евклидовость кольца R .)

3 Сравнения и арифметика остатков

Определение. Пусть а, b Z , m N . Говорят, что число а сравнимо с b по модулю m , если а и b при делении на m дают одинаковые остатки. Запись этого факта выглядит так:

a b(mod m) .

Очевидно, что бинарное отношение сравнимости m (неважно, по какому модулю) есть отношение эквивалентности на множестве целых чисел, а любители алгебры скажут, что это отношение является даже конгруэнцией кольца Z , фактор-кольцо по которой Z/ m называется кольцом вычетов и обозначается Z m .

Ясно, что число a сравнимо с b по модулю m тогда и только тогда, когда a-b делится на m нацело. Очевидно, это, в свою очередь, бывает тогда и только тогда, когда найдется такое целое число t , что a=b+mt . Знатоки алгебры добавят к этим эквивалентным утверждениям, что сравнимость a с b по модулю m означает, что a и b представляют один и тот же элемент в кольце Z m .

Свойство 1. Сравнения по одинаковому модулю можно почленно складывать.

Доказательство. Пусть a1 b1 (mod m) , a2 b2 (mod m) . Это означает, что a 1 =b 1 +mt 1 , a 2 =b 2 +mt 2 . После сложения последних двух равенств получим a 1 +a 2 =b 1 +b 2 +m(t 1 +t 2 ) , что означает a 1 +a 2 b 1 +b 2 (mod m) .

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

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


Свойство 3. К любой части сравнения можно прибавить любое число, кратное модулю.

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

Свойство 4. Сравнения по одинаковому модулю можно почленно перемножать и, следовательно,

Свойство 5. Обе части сравнения можно возвести в одну и ту же степень.

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

Как следствие из вышеперечисленных свойств, получаем

Свойство 6. Если

a 0  b 0 (mod m) , a 1  b 1 (mod m) ,..., a n  b n (mod m) , x  y(mod m) ,

то a 0 x n +a 1 x n-1 +...+a n  b 0 y n +b 1 y n-1 +...+b n (mod m)

Свойство 7. Обе части сравнения можно разделить на их общий делитель, взаимно простой с модулем.

Доказательство. Пусть a b(mod m) , a=a 1 d , b=b 1 d . Тогда (a 1 -b 1 ) d делится на m . Поскольку d и m взаимно просты, то на m делится именно (a 1 -b 1 ) , что означает a 1 b 1 (mod m) .

Свойство 8. Обе части сравнения и его модуль можно умножить на одно и то же целое число или разделить на их общий делитель.

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

a b(mod m) a=b+mt ak=bk+mkt ak bk(mod mk) .

Свойство 9. Если сравнение a b имеет место по нескольким разным модулям, то оно имеет место и по модулю, равному наименьшему общему кратному этих модулей.

Доказательство. Если a b(mod m 1 ) и a b(mod m 2 ) , то a-b делится на m 1 и на m 2 , значит a-b делится на наименьшее общее кратное m 1 и m 2 .

Свойство 10. Если сравнение имеет место по модулю m , то оно имеет место и по модулю d , равному любому делителю числа m .

Доказательство очевидно следует из транзитивности отношения делимости: если a b(mod m) , то a-b делится на m , значит a-b делится на d , где d|m .

Свойство 11. Если одна часть сравнения и модуль делятся на некоторое число, то и другая часть сравнения должна делиться на то же число.

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

a  b(mod m)  a=b+mt .

Отношение m сравнимости по произвольному модулю m есть отношение эквивалентности на множестве целых чисел. Это отношение эквивалентности индуцирует разбиение множества целых чисел на классы эквивалентных между собой элементов, т.е. в один класс объединяются числа, дающие при делении на m одинаковые остатки. Число классов эквивалентности m (знатоки скажут - "индекс эквивалентности m ") в точности равно m .

Определение. Любое число из класса эквивалентности m будем называть вычетом по модулю m . Совокупность вычетов, взятых по одному из каждого класса эквивалентности m , называется полной системой вычетов по модулю m (в полной системе вычетов, таким образом, всего m штук чисел). Непосредственно сами остатки при делении на m называются наименьшими неотрицательными вычетами и, конечно, образуют полную систему вычетов по модулю m . Вычет называется абсолютно наименьшим, если наименьший среди модулей вычетов данного класса.

Пример : Пусть m = 5 . Тогда:

0, 1, 2, 3, 4 - наименьшие неотрицательные вычеты;

-2, -1, 0, 1, 2 - абсолютно наименьшие вычеты.

Обе приведенные совокупности чисел образуют полные системы вычетов по модулю 5 .

Лемма 1. 1) Любые m штук попарно не сравнимых по модулю m чисел образуют полную систему вычетов по модулю m .

2) Если а и m взаимно просты, а x пробегает полную систему вычетов по модулю m , то значения линейной формы аx+b , где b - любое целое число, тоже пробегают полную систему вычетов по модулю m .

Доказательство. Утверждение 1) – очевидно. Докажем утверждение 2). Чисел аx+b ровно m штук. Покажем, что они между собой не сравнимы по модулю m . Ну пусть для некоторых различных x 1 и x 2 из полной системы вычетов оказалось, что ax 1 +b ax 2 +b(mod m) . Тогда, по свойствам сравнений из предыдущего пункта, получаем:


ax 1 ax 2 (mod m)

x 1 x 2 (mod m)

– противоречие с тем, что x 1 и x 2 различны и взяты из полной системы вычетов.

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

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

Приведенную систему обычно выбирают из наименьших неотрицательных вычетов. Ясно, что приведенная система вычетов по модулю m содержит ( m ) штук вычетов, где ( m )– функция Эйлера – число чисел, меньших m и взаимно простых с m . Если к этому моменту вы уже забыли функцию Эйлера, загляните в пункт 14 и убедитесь, что про нее там кое-что говорилось.

Пример. Пусть m = 42. Тогда приведенная система вычетов суть:

1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41.

Лемма 2. 1) Любые ( m ) чисел, попарно не сравнимые по модулю m и взаимно простые с модулем, образуют приведенную систему вычетов по модулю m .

2) Если ( a,m ) = 1 и x пробегает приведенную систему вычетов по модулю m , то аx так же пробегает приведенную систему вычетов по модулю m .

Доказательство. Утверждение 1) – очевидно. Докажем утверждение 2). Числа аx попарно несравнимы (это доказывается так же, как в лемме 1 этого пункта), их ровно ( m ) штук. Ясно также, что все они взаимно просты с модулем, ибо (a,m)=1, (x,m)=1 (ax.m)=1 . Значит, числа аx образуют приведенную систему вычетов.

Лемма 3. Пусть m 1 , m 2 , ..., m k – попарно взаимно просты и m 1 m 2 ...m k =M 1 m 1 =M 2 m 2 =...=M k m k , где M j =m 1 ...m j-1 m j+1 ...m k

1) Если x 1 , x 2 , ..., x k пробегают полные системы вычетов по модулям m 1 , m 2 , ..., m k соответственно, то значения линейной формы M 1 x 1 +M 2 x 2 + ...+M k x k пробегают полную систему вычетов по модулю m=m 1 m 2 ...m k .

2) Если 1 , 2 , ..., k пробегают приведенные системы вычетов по модулям m 1 , m 2 , ..., m k соответственно, то значения линейной формы M 1 1 +M 2 2 + ...+M k k пробегают приведенную систему вычетов по модулю m=m 1 m 2 ...m k .

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

1) Форма M 1 x 1 +M 2 x 2 + ...+M k x k принимает, очевидно, m 1 m 2 ...m k =m значений. Покажем, что эти значения попарно несравнимы. Ну пусть

M 1 x 1 +M 2 x 2 + ...+M k x k M 1 x 1  +M 2 x 2  + ...+M k x k  (mod m)

Всякое M j , отличное от M s , кратно m s . Убирая слева и справа в последнем сравнении слагаемые, кратные m s , получим:

M s x s  M s x s  (mod m s )  x s  x s  (mod m s )

– противоречие с тем, что x s пробегает полную систему вычетов по модулю m s .

2). Форма M 1 1 +M 2 2 + ...+M k k принимает, очевидно, ( m 1 ) ( m 2 ) ... ( m k ) = ( m 1 m 2 ... m k )= ( m ) (функция Эйлера мультипликативна!) различных значений, которые между собой по модулю m=m 1 m 2 ...m k попарно несравнимы. Последнее легко доказывается рассуждениями, аналогичными рассуждениям, проведенным при доказательстве утверждения 1) этой леммы. Так как ( M 1 1 +M 2 2 + ...+M k k ,m s )=(M s s ,m s )=1 для каждого 1 s k , то ( M 1 1 +M 2 2 + ...+M k k ,m s )=1 , следовательно множество значений формы M 1 1 +M 2 2 + ...+M k k образует приведенную систему вычетов по модулю m .

Лемма 4. Пусть x 1 , x 2 , ..., x k ,x пробегают полные, а 1 , 2 ,..., k ,  – пробегают приведенные системы вычетов по модулям m 1 , m 2 , ..., m k и m=m 1 m 2 ...m k соответственно, где (m i m j )=1 при i j . Тогда дроби {x 1 /m 1 +x 2 /m 2 +...+x k /m k } совпадают с дробями {x/m} , а дроби { 1 /m 1 + 2 /m 2 +...+ k /m k } совпадают с дробями { /m} .

Доказательство. Доказательство обоих утверждений леммы 4 легко получается применением предыдущей леммы 3 после того, как вы приведете каждую сумму {x 1 /m 1 +x 2 /m 2 +...+x k /m k } и { 1 /m 1 + 2 /m 2 +...+ k /m k } к общему знаменателю:

{x 1 /m 1 +x 2 /m 2 +...+x k /m k }={(M 1 x 1 +M 2 x 2 +...+M k x k )/m} ;

{ 1 /m 1 + 2 /m 2 +...+ k /m k }={(M 1 1 +M 2 2 +...+M k k )/m} ,

где M j = m 1 ... m j -1 m j +1 ... m k .

Если теперь принять во внимание, что дробные части чисел, получающихся при делении на модуль m любых двух чисел, сравнимых по модулю m , одинаковы (они равны r/m , где r – наименьший неотрицательный вычет из данного класса), то утверждения настоящей леммы становятся очевидными.

Теорема (Эйлер). Пусть m>1 , (a,m)=1 , ( m ) – функция Эйлера. Тогда:


a ( m ) 1(mod m) .

Доказательство. Пусть х пробегает приведенную систему вычетов по mod m :

x=r 1 ,r 2 ,...,r c

где c= (m) их число, r 1 ,r 2 ,..., r c - наименьшие неотрицательные вычеты по mod m . Следовательно, наименьшие неотрицательные вычеты, соответствующие числам ax суть соответственно:

1 , 2 ,..., c

– тоже пробегают приведенную систему вычетов, но в другом порядке (см. Лемму 2 из пункта 17). Значит:

a r 1  (mod m)

a r 2  (mod m)

...

a r c  (mod m)

Перемножим эти с штук сравнений. Получится:

a c r 1 r 2 ...r c j 1 j 2 ... j c (mod m)

Так как r 1 r 2 ...r c = 1 2 ... c 0 и взаимно просто с модулем m , то, поделив последнее сравнение на r 1 r 2 ...r c , получим a ( m ) 1(mod m) .

Вторая теорема этого пункта – теорема Ферма – является непосредственным следствием теоремы Эйлера (конечно, при схеме изложения материала, принятой в этой книжке).

Теорема (Ферма). Пусть р – простое число, р не делит a . Тогда:

a p-1  1(mod p) .

Доказательство 1. Положим в условии теоремы Эйлера m=p , тогда (m)=p-1 (см. пункт 14 ) . Получаем a p-1 1(mod p) .

Необходимо отметить важность условия взаимной простоты модуля и числа a в формулировках теорем Эйлера и Ферма. Простой пример: сравнение 6 2 1(mod 3) очевидно не выполняется. Однако можно легко подправить формулировку теоремы Ферма, чтобы снять ограничение взаимной простоты.

Следствие 1. Без всяких ограничений на a Z ,

a p a(mod p) .

Доказательство. Умножим обе части сравнения a p-1 1(mod p) на a . Ясно, что получится сравнение, справедливое и при a , кратном р .

Доказательство 2. Так как р - простое число, то все биномиальные коэффициенты:

(кроме C 0 p и C p p ) делятся на р , ибо числитель выписанного выражения содержит р , а знаменатель не содержит этого множителя. Если вспомнить бином Ньютона, то становится понятно, что разность (A+B) p -A p -B p =C p 1 A p-1 B 1 +C p 2 A p-2 B 2 +...+C p p-2 A 2 B p-2 +C p p-1 A 1 B p-1 , где А и В – какие угодно целые числа, всегда делится на р . Последовательным применением этого незатейливого наблюдения получаем, что (A+B+C) p -A p -B p -C p ={[(A+B)+C] p -(A+B) p -C p }+(A+B) p -A p -B p всегда делится на р ; (A+B+C+D) p -A p -B p -C p -D p всегда делится на р ; и вообще, (A+B+C+...+K) p -A p -B p -C p -...-K p всегда делится на р . Положим теперь в последнем выражении A=B=C=...=K=1 и возьмем количество этих чисел равным a . Получится, что a p -a делится на р , а это и есть теорема Ферма в более общей формулировке.

Следствие 2. (a+b) p a p +b p (mod p) .

Система шифрования RSA

Пусть и натуральные числа. Функция , реализующая схему RSA, устроена следующим образом

(1)

Для дешифрования сообщения достаточно решить сравнение

(2)

При некоторых условиях на и это сравнение имеет единственное решение .

Для того, чтобы описать эти условия и объяснить, как можно найти решение, нам потребуется одна теоретико-числовая функция, так называемая функция Эйлера. Эта функция натурального аргумента обозначается и равняется количеству целых чисел на отрезке от до , взаимно простых с . Так и для любого простого числа и натурального . Кроме того, для любых натуральных взаимно простых и . Эти свойства позволяют легко вычислить значение , если известно разложение числа на простые сомножители.

Если показатель степени в сравнении (2) взаимно прост с , то сравнение (2) имеет единственное решение. Для того, чтобы найти его, определим целое число , удовлетворяющее условиям

(3)


Такое число существует, поскольку , и притом единственно. Здесь и далее символом будет обозначаться наибольший общий делитель чисел и . Классическая теорема Эйлера, см. [3], утверждает, что для каждого числа , взаимно простого с , выполняется сравнение и, следовательно,

(4)

Таким образом, в предположении , единственное решение сравнения (2) может быть найдено в виде

(5)

Если дополнительно предположить, что число состоит из различных простых сомножителей, то сравнение (5) будет выполняться и без предположения . Действительно, обозначим и . Тогда делится на , а из (2) следует, что . Подобно (4), теперь легко находим . А кроме того, имеем . Получившиеся сравнения в силу дают нам (5).

Функция (1), принятая в системе RSA, может быть вычислена достаточно быстро. Как это сделать, мы обсудим чуть ниже. Пока отметим лишь, что обратная к функция вычисляется по тем же правилам, что и , лишь с заменой показателя степени на . Таким образом, для функции (1) будут выполнены указанные выше свойства а) и б).

Для вычисления функции (1) достаточно знать лишь числа и . Именно они составляют открытый ключ для шифрования. А вот для вычисления обратной функции требуется знать число , оно и является ``секретом'' , о котором речь идет в пункте в). Казалось бы, ничего не стоит, зная число , разложить его на простые сомножители, вычислить затем с помощью известных правил значение и, наконец, с помощью (3) определить нужное число . Все шаги этого вычисления могут быть реализованы достаточно быстро, за исключением первого. Именно разложение числа на простые множители и составляет наиболее трудоемкую часть вычислений. В теории чисел несмотря на многолетнюю ее историю и на очень интенсивные поиски в течение последних 20 лет, эффективный алгоритм разложения натуральных чисел на множители так и не найден. Конечно, можно, перебирая все простые числа до , и, деля на них , найти требуемое разложение. Но, учитывая, что количество простых в этом промежутке, асимптотически равно , находим, что при , записываемом 100 десятичными цифрами, найдется не менее простых чисел, на которые придется делить при разложении его на множители. Очень грубые прикидки показывают, что компьютеру, выполняющему миллион делений в секунду, для разложения числа таким способом на простые сомножители потребуется не менее, чем лет. Известны и более эффективные способы разложения целых чисел на множители, чем простой перебор простых делителей, но и они работают очень медленно. Таким образом, название статьи М. Гарднера вполне оправдано.

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

(6)

то единственное условие на выбор показателя степени в отображении (1) есть

(7)

Итак, лицо, заинтересованное в организации шифрованной переписки с помощью схемы RSA, выбирает два достаточно больших простых числа и . Перемножая их, оно находит число . Затем выбирается число , удовлетворяющее условиям (7), вычисляется с помощью (6) число и с помощью (3) - число . Числа и публикуются, число остается секретным. Теперь любой может отправлять зашифрованные с помощью (3) сообщения организатору этой системы, а организатор легко сможет дешифровывать их с помощью (5).

Для иллюстрации своего метода Ривест, Шамир и Адлеман зашифровали таким способом некоторую английскую фразу. Сначала она стандартным образом (a=01, b=02, ..., z=26, пробел=00) была записана в виде целого числа , а затем зашифрована с помощью отображения (1) при

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

была обещана награда в 100$.

Эта история завершилась спустя 17 лет в 1994 г., когда D. Atkins, M. Graff, A. K. Lenstra и P. C. Leyland сообщили о дешифровке фразы, предложенной в [1]. Она1) была вынесена в заголовок статьи, а соответствующие числа и оказались равными


4 Функция Эйлера

Определение. Функция : R R (или, более общо, : C C ) называется мультипликативной если:

1). Функция определена всюду на N и существует а N такой, что ( а ) 0.

2). Для любых взаимно простых натуральных чисел а 1 и а 2 выполняется ( а 1 · а 2 ) = ( а 1 ) · ( а 2 ).

Пример 1. ( а ) = а s , где s - любое (хоть действительное, хоть комплексное) число. Проверка аксиом 1) и 2) из определения мультипликативной функции не составляет труда, а сам пример показывает, что мультипликативных функций по меньшей мере континуум, т.е. много.

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

Свойство 1. (1) = 1.

Доказательство. Пусть а - то самое натуральное число, для которого

( а ) 0. Тогда ( а · 1) = ( а ) · (1) = ( а ).

Свойство 2.

,

где р 1 , р 2 ,..., р n - различные простые числа.

Доказательство очевидно.

Свойство 3. Обратно, мы всегда построим некоторую мультипликативную функцию ( a ), если зададим (1) = 1 и произвольно определим ( р  ) для всех простых р и всех натуральных , а для остальных натуральных чисел доопределим функцию ( a ) используя равенство


.

Доказательство сразу следует из основной теоремы арифметики.

Пример 2. Пусть (1) = 1 и ( р  ) = 2 для всех р и . Тогда, для произвольного числа,

.

Свойство 4. Произведение нескольких мультипликативных функций является мультипликативной функцией.

Доказательство. Сначала докажем для двух сомножителей: Пусть 1 и 2 - мультипликативные функции = 1 · 2 , тогда (проверяем аксиомы определения)

1) (1) = 1 (1) · 2 (1) = 1 и, кроме того, существует такое a (это a = 1), что ( a ) 0.

2) Пусть ( a , b ) = 1 - взаимно просты. Тогда

( a · b ) = 1 ( a · b ) · 2 ( a · b ) =

= 1 ( a ) 1 ( b ) 2 ( a ) 2 ( b ) =

= 1 ( a ) 2 ( a ) · 1 ( b ) 2 ( b ) = ( a ) ( b ).

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

Введем удобное обозначение. Всюду далее, символом

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

Лемма 1. Пусть

- каноническое разложение числа a N , - любая мультипликативная функция. Тогда:

Если a = 1, то считаем правую часть равной 1.

Доказательство. Раскроем скобки в правой части. Получим сумму всех (без пропусков и повторений) слагаемых вида

,

где 0 k k , для всех k n . Так как различные простые числа заведомо взаимно просты, то

,

а это как раз то, что стоит в доказываемом равенстве слева.

Лемма 2. Пусть ( a ) - любая мультипликативная функция. Тогда

,

- также мультипликативная функция.

Доказательство. Проверим для ( a ) аксиомы определения мультипликативной функции.

1).

2). Пусть

и все р и q различны. Тогда, по предыдущей лемме, имеем: (благо, делители у чисел a и b различны)

Пример 1. Число делителей данного числа.

Пусть ( а ) = а 0 1 - тождественная единица (заведомо мультипликативная функция). Тогда, если

,

то тождество леммы 1 пункта 13 принимает вид:

,


- это не что иное, как количество делителей числа a . По лемме 2 пункта 13, количество делителей ( a ) числа a есть мультипликативная функция.

Пример 2. Сумма делителей данного числа.

Пусть ( a ) = a 1 a - тождественная мультипликативная функция. Тогда, если

,

то тождество леммы 1 пункта 13 принимает вид:

сумма первых ( + 1) членов

геометрической прогрессии

- сумма всех делителей числа a . По лемме 2 пункта 13, сумма всех делителей есть мультипликативная функция.

Пример 3. Функция Мебиуса.

Функция Мебиуса ( a ) - это мультипликативная функция, определяемая следующим образом: если p - простое число, то ( p ) = -1; ( p  ) = 0, при > 1; на остальных натуральных числах функция доопределяется по мультипликативности.

Таким образом, если число a делится на квадрат натурального числа, отличный от единицы, то ( a ) = 0; если же a = p 1 p 2· · · p n (теоретик-числовик сказал бы на своем жаргоне: "если a свободно от квадратов"), то ( a ) = (-1) k , где k - число различных простых делителей a . Понятно, что (1) = (-1) 0 = 1, как и должно быть.

Лемма 1. Пусть ( a ) - произвольная мультипликативная функция,

.

Тогда:

(при a = 1 считаем правую часть равной 1).

Доказательство. Рассмотрим функцию 1 ( x ) = ( x ) · ( x ). Эта функция мультипликативна, как произведение мультипликативных функций. Для 1 ( x ) имеем ( p - простое): 1 ( p ) = - ( x ); 1 ( p  ) = 0, при > 1. Следовательно, для 1 ( x ) тождество леммы 1 пункта 13 выглядит так:

Следствие 1. Пусть ( d ) = d -1 = 1/ d (это, конечно, мультипликативная функция),


Тогда:

Пример 4. Функция Эйлера.

Функция Эйлера, пожалуй, самая знаменитая и "дары приносящая" функция из всех функций, рассматриваемых в этом пункте. Функция Эйлера ( a ) есть количество чисел из ряда 0, 1, 2,..., a - 1, взаимно простых с a . Полезность и практическое применение этой функции я продемонстрирую в следующих пунктах, а сейчас давайте поймем, как ее вычислять.

Лемма 2. Пусть

.

Тогда:

1) (формула Эйлера);

2)

в частности, ( p  ) = p  - p  -1 , ( p ) = p - 1.

Доказательство. Пусть x пробегает числа 0, 1, 2,..., a - 1. Положим x = ( x , a ) - наибольший общий делитель. Тогда ( a ) есть число значений x , равных 1. Придумаем такую функцию ( x ), чтобы она была единицей, когда x единица, и была нулем в остальных случаях. Вот подходящая кандидатура:


Последнее легко понять, если вспомнить лемму 1 из этого пункта и в ее формулировке взять ( d ) 1. Далее, сделав над собой некоторое усилие, можно усмотреть, что:

Поскольку справа сумма в скобках берется по всем делителям d числа x = ( x , a ), то d делит x и d делит a . Значит в первой сумме справа в суммировании участвуют только те x , которые кратны d . Таких x среди чисел 0, 1, 2,..., a - 1 ровно a / d штук. Получается, что:

что и требовалось.

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

Зафиксируем некоторое d 0 такое, что d 0 делит a , d 0 делит x , x < a . Значит в сумме справа в скобках слагаемых ( d 0 ) ровно a / d 0 штук и ( a ) есть просто сумма


После этого, равенство

получается применением следствия из леммы 1 этого пункта. Должен признать, что приведенное доказательство формулы Эйлера и, в особенности, его последний момент с изменением порядка суммирования, объективно тяжеловаты для понимания. Но мы не боимся трудностей!

Второе утверждение леммы следует из первого внесением впереди стоящего множителя a внутрь скобок.

Оказывается, только что доказанная формула

для вычисления функции Эйлера имеет ясный "физический смысл". Дело в том, что в ней отражено так называемое правило включений и исключений:

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

Проиллюстрирую это правило на примере подсчета функции Эйлера для чисел вида

Посмотрите на рисунок 1.

Рис. 1.

Прямоугольник изображает множество всех целых чисел от 0 до a ; овал N 1 - множество чисел, кратных p 1 ; кружок N 2 - числа, кратные p 2 ; пересечение N 1,2 - множество чисел, делящихся одновременно на p 1 и p 2 , т.е. на p 1 p 2 ; числа вне овала и кружочка взаимно просты с a . Для подсчета числа чисел, взаимно простых с a , нужно из a вычесть количество чисел в N 1 и количество чисел в N 2 (их, соответственно, a / p 1 и a / p 2 штук), при этом общая часть N 1,2 (там a /( p 1 p 2 ) штук чисел) вычтется дважды, значит ее надо один раз прибавить (вот оно, "включение - исключение"!). В результате получим:

что я вам и утверждал. Мне кажется, что таким способом можно объяснить формулу Эйлера любому смышленому школьнику.

Кстати, любому смышленому школьнику вполне возможно объяснить и то, что при a > 2, ( a ) всегда число четное. Действительно, если k взаимно просто с a и k < a , то число a - k тоже меньше a , взаимно просто с a и не равно k . (Если бы a и a - k имели общий делитель, то их разность a - ( a - k ) = k тоже делилась бы на этот делитель, что противоречит взаимной простоте a и k .) Значит числа, взаимно простые с a разбиваются на пары k и a - k , следовательно, их четное число.

Из леммы 2 вытекают приятные следствия.

Следствие 2. Функция Эйлера мультипликативна.

Доказательство. Имеем:

- произведение двух мультипликативных функций, первая из которых мультипликативна по лемме 2 пункта 13. Значит, ( a ) - мультипликативна.

Следствие 3. .

Доказательство. Пусть

.

Тогда, по лемме 1 пункта 13 имеем:


.

5 Китайская теорема об остатках

В этом пункте детально рассмотрим только сравнения первой степени вида

ax b(mod m),

оставив более высокие степени на съедение следующим пунктам. Как решать такое сравнение? Рассмотрим два случая.

Случай 1. Пусть а и m взаимно просты. Тогда несократимая дробь m/a сама просится разложиться в цепную дробь:

Эта цепная дробь, разумеется, конечна, так как m/a - рациональное число. Рассмотрим две ее последние подходящие дроби:

.

Вспоминаем (пункт 9) важное свойство числителей и знаменателей подходящих дробей: mQ n-1 -aP n-1 =(-1) n . Далее (слагаемое mQ n-1 , кратное m , можно выкинуть из левой части сравнения):

-aP n-1  (-1) n (mod m) т.е.

aP n-1  (-1) n-1 (mod m) т.е.

a[(-1) n-1 P n-1 b]  b(mod m)

и единственное решение исходного сравнения есть:

x (-1) n-1 P n-1 b(mod m)

Пример. Решить сравнение 111x 75(mod 322).

Решение. (111, 322)=1. Включаем алгоритм Евклида:

322=11 · 2+100

111=100 · 1+11

100=11 · 9+1

11=1 · 11

(В равенствах подчеркнуты неполные частные.) Значит, n=4 , а соответствующая цепная дробь такова:

Посчитаем числители подходящих дробей, составив для этого стандартную таблицу:

0

2

1

9

11

P n

1

2

3

29

322

Числитель предпоследней подходящей дроби равен 29, следовательно, готовая формула дает ответ: x (-1) 3 29 75 -2175 79(mod 322)

Ох уж эти мне теоретико-числовые рассуждения из разных учебников, продиктованные традицией изложения и необходимостью обязательно использовать ранее изложенную теорию! О чем идет речь в нескольких строках выше? Дано сравнение ax b(mod m) , где a и m взаимно просты. Ну возьмите вы алгоритм Евклида, найдите те самые пресловутые u , v Z такие, что au+vm=1 , умножьте это равенство на b : aub+vmb=b , откуда немедленно следует: aub b(mod m) . Значит решением исходного сравнения является x ub(mod m) . Собственно, и все. Поворчал.

Случай 2. Пусть (a,m)=d . В этом случае, для разрешимости сравнения ax b(mod m) необходимо, чтобы d делило b , иначе сравнение вообще выполняться не может. Действительно, ax b(mod m) бывает тогда, и только тогда, когда ax- b делится на m нацело, т.е. ax- b=t · m ,

t  Z , откуда b=ax- t m , а правая часть последнего равенства кратна d .

Пусть b=db 1 , a=da 1 , m=dm 1 . Тогда обе части сравнения xa 1 d b 1 d(mod m 1 d) и его модуль поделим на d :

xa 1 b 1 (mod m 1 ) ,

где уже а 1 и m 1 взаимно просты. Согласно случаю 1 этого пункта, такое сравнение имеет единственное решение x 0 :

x x 0 (mod m 1 ) (*)

По исходному модулю m , числа (*) образуют столько решений исходного сравнения, сколько чисел вида (*) содержится в полной системе вычетов: 0,1,2,..., m-2, m-1 . Очевидно, что из чисел x=x 0 +t m в полную систему наименьших неотрицательных вычетов попадают только x 0 , x 0 +m 1 , x 0 +2m 1 , ..., x 0 +(d-1)m 1 , т.е. всего d чисел. Значит у исходного сравнения имеется d решений.

Подведем итог рассмотренных случаев в виде следующей теоремы

Теорема 1. Пусть (a,m)=d . Если b не делится на d , сравнение ax b(mod m) не имеет решений. Если b кратно d , сравнение ax b(mod m) имеет d штук решений.

Пример. Решить сравнение 111x 75(mod 321) .

Решение. (111,321)=3 , поэтому поделим сравнение и его модуль на 3:

37x 25(mod 107) и уже (37,107)=1 .

Включаем алгоритм Евклида (как обычно, подчеркнуты неполные частные):

107=37 2+33

37=33 1+4

33=4 8+1

4=1 4

Имеем n=4 и цепная дробь такова:

Таблица для нахождения числителей подходящих дробей:

q n

0

2

1

8

4

P n

1

2

3

26

107

Значит, x  (-1) 3  26  25  -650( mod 107)  -8( mod 107)  99( mod 107) .

Три решения исходного сравнения:

x 99(mod 321), x 206(mod 321), x 313(mod 321) ,

и других решений нет.

Теорема 2. Пусть m>1, (a,m)=1 Тогда сравнение ax b(mod m) имеет решение: x ba (m)-1 (mod m) .

Доказательство. По теореме Эйлера, имеем: a (m) 1(mod m) , следовательно, a ba (m)-1 b(mod m) .

Пример. Решить сравнение 7x 3(mod 10) . Вычисляем:

(10)=4; x 3 7 4-1 (mod 10) 1029(mod 10) 9(mod 10) .

Видно, что этот способ решения сравнений хорош (в смысле минимума интеллектуальных затрат на его осуществление), но может потребовать возведения числа а в довольно большую степень, что довольно трудоемко. Для того, чтобы как следует это прочувствовать, возведите самостоятельно число 24789 в степень 46728.

Теорема 3. Пусть р – простое число, 0<a<p . Тогда сравнение ax b(mod p) имеет решение:

где C a p – биномиальный коэффициент.

Доказательство непосредственно следует из очевидного сравнения

которое нужно почленно поделить на взаимно простое с модулем число 1 2 3 ... a-1 .

Пример. Решить сравнение 7x 2(mod 11) . Вычисляем:


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

Лемма 1 (Китайская теорема об остатках). Пусть дана простейшая система сравнений первой степени:

где m 1 ,m 2 ,...,m k попарно взаимно просты. Пусть, далее, m 1 m 2 ...m k =M s m s ; M s M s  1(mod m s ) (Очевидно, что такое число M s  всегда можно подобрать хотя бы с помощью алгоритма Евклида, т.к. (m s ,M s )=1 ); x 0 =M 1 M 1  b 1 +M 2 M 2  b 2 +...+M k M k  b k . Тогда система (*) равносильна одному сравнению

x x 0 (mod m 1 m 2 ...m k ) ,

т.е. набор решений (*) совпадает с набором решений сравнения x x 0 (mod m 1 m 2 ...m k ) .

Доказательство. Имеем: m s делит M j , при s j. Следовательно, x 0 M s M s  b s (mod m s ) , откуда x 0 b s (mod m s ) . Это означает, что система (*) равносильна системе

которая, очевидно, в свою очередь, равносильна одному сравнению x x 0 (mod m 1 m 2 ...m k ) .

В следующей лемме, для краткости формулировки, сохранены обозначения леммы 1.

Лемма 2. Если b 1 ,b 2 ,...,b k пробегают полные системы вычетов по модулям m 1 ,m 2 ,...,m k соответственно, то x 0 пробегает полную систему вычетов по модулю m 1 m 2 ...m k .

Доказательство. Действительно, x 0 =A 1 b 1 +A 2 b 2 +...+A k b k пробегает m 1 m 2 ...m k различных значений. Покажем, что все они попарно не сравнимы по модулю m 1 m 2 ...m k .

Ну пусть оказалось, что

A 1 b 1 +A 2 b 2 +...+A k b k  A 1 b' 1 +A 2 b' 2 +...+A k b' k (mod m 1 m 2 ...m k )

Значит,

A 1 b 1 +A 2 b 2 +...+A k b k  A 1 b' 1 +A 2 b' 2 +...+A k b' k (mod m s )

для каждого s , откуда

M s M s  b s  M s M s  b' s

Вспомним теперь, что M s M s   1(mod m s ) , значит M s M s   1+m s  t , откуда (M s M s  ,m s )=1 . Разделив теперь обе части сравнения

M s M s  b s M s M s  b' s

на число M s M s  , взаимно простое с модулем, получим, что b s b' s (mod m s ) , т.е. b s =b' s для каждого s .

Итак, x 0 пробегает m 1 m 2 ...m k различных значений, попарно не сравнимых по модулю m 1 m 2 ...m k , т.е. полную систему вычетов.

Формулировка для колец

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

является сюрьективным. Более того, Φ опеределяет изоморфизм

.

Если положить , и определить гомоморфизмы следующим образом


то мы получим арифметическую версию теоремы.

Также часто встречается следующая эквивалентная формулировка для колец, где Bi имеют форму A / Ii , φi являются естественными проекциями на A / Ii и требуется, чтобы Ii + Ij = A для любых .

Заключение

История арифметики остатков начинается с исследований К.Ф. Гаусса, который впервые стал рассматривать сравнения. В дальнейшем была обнаружена связь теории сравнений с астрономическими задачами (китайская теорема об остатках). В результате многочисленных исследований теория остатков была распространена на кольца произвольной природы. В последнее время обнаружилось приложение этой теории в криптографии. В дипломной работе изложена теория остатков на современном алгебраическом языке.


Список использованных источников

1. С. Ленг, Алгебра, М., 1968

2. С. Коунтинхо, Введение в теорию чисел. Алгоритм RSA, М. 2001

3. А.И. Кострикин, Введение в алгебру, М., 2000

4. О. Зарисский, Коммутативная алгебра, т.1., М., 1963