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

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

Определение 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, 2 q, 3 q,..., (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

Дата добавления: 2014-01-11