Элементы теории чисел.

Многие криптографические алгоритмы базируются на результатах классической теории чисел. Мы рассмотрим необходимый минимум из этой теории. Классические теоремы Ферма, Эйлера и ряд других результатов из теории чисел будут даны без доказательств, которые могут быть найдены практически в любом учебнике по теории чисел.

Определение 3.2. Целое положительное число р называется простым, если оно не делится ни на какое другое число, кроме самого себя и единицы.

Пример. Числа 11, 23 - простые; числа 27, 33 - составные (27 делится на 3 и на 9, 33 делится на 3 и на 11).

Теорема 3.3 (основная теорема арифметики).Любое целое положительное число может быть представлено в виде произведения простых чисел, причем единственным образом.

Пример. 27=3·3·3, 33 =3·11.

Определение 3.3. Два числа называются взаимно простыми, если они не имеют ни одного общего делителя кроме единицы.

Пример 3.5. Числа 27 и 28 взаимно просты (у них нет общих делителей кроме единицы), числа 27 и 33 - нет (у них есть общий делитель 3).

Определение 3.4 (функция Эйлера).Пусть дано целое число N>1. Значение функции Эйлера (N) равно количеству чисел в ряду 1,2,3,...,N-1, взаимно простых с N.

Пример 3.6.

(10)=? (12)=?

1, 2, 3, 4, 5, 6, 7, 8, 9 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11

(10)=4 (12)=4

(здесь подчеркнуты числа, не взаимнопростые с аргументом).

Утверждение 3.4. Если р - простое число, то (р)=р-1.

Доказательство. В ряду 1, 2, 3, ..., р-1 все числа взаимнопросты с р, так как р - простое число и по определению не делится ни на какое другое число.

Утверждение 3.5. Пусть р и q - два различных простых числа (рq). Тогда (p) =(p-1)·(g-1).

Доказательство. В ряду 1, 2, ..., pq-1 не взаимнопростыми с pq будут числа

р, 2р, 3р,…, (q- l)p

и

q, 2q, 3q, ..., (p-1)q.

Всего таких чисел будет (q—1)+(р-1) Следвательно, количество чисел, взаимнопростых с pq, будет pq-1-(р-1)-(q-1)=pq-q-p+1=(p-1)(q-1).

Теорема 3.6 (Ферма).Пусть р - простое число и 0<а<р. Тогда

а^р-1 mod p=1.

Пример 3.7. р=13, а=2;

2¹² mod l3=(2²)²·((2²)²)² mod 13=3·9 mod 13 = 1,

10¹⁰ mod 11 = 10²·((2²)²)² mod 11=1·1 = 1.

Теорема 3.7 (Эйлер).Пусть а и b — взаимно простые числа.Тогда,

mod b=1.

Теорема Ферма является частным случаем теоремы Эйлера, когда b - простое число.

Теорема 2.8. Если р и q — простые числа, рq и k- произвольное целое число, то

. (2.12)

Определение 3.5.Пусть а и b - два целых положительных числа. Наибольший общий делитель чисел а и b есть наибольшее число с, которое делит и а и b:

c=gcd(a,b).

Обозначение gcd для наибольшего общего делителя происходит от английских слов greatest common divisor