Рабочая программа по дисциплине «Теоретико-числовые методы в криптографии» для студентов специальности «Компьютерная безопасность» ТюмГУ, и задания для самостоятельного выполнения с ответами к ним

Скачать 3.85 Mb.

Название	Рабочая программа по дисциплине «Теоретико-числовые методы в криптографии» для студентов специальности «Компьютерная безопасность» ТюмГУ, и задания для самостоятельного выполнения с ответами к ним
страница	3/16
Дата публикации	18.08.2013
Размер	3.85 Mb.
Тип	Учебное пособие

100-bal.ru > Математика > Учебное пособие

1 2 3 4 5 6 7 8 9 ... 16

§2. Функция Эйлера.

2.1. Мультипликативные функции.

Введем функции – целая часть от x , – дробная часть от x.

Функция Θ(a) называется мультипликативной, если:

Определена для , и при этом a₁:Θ(a₁)≠0;
: (a₁,a₂)=1 Θ(a₁a₂)=Θ(a₁)Θ(a₂).

Пример:

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

Свойства мультипликативных функций:

1. Если Θ(a) – мультипликативная функция, то Θ(1)=1.

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

По определению мультипликативной функции, найдется a₁: Θ(a₁)≠0.

Тогда Θ(a₁)=Θ(a₁1)=Θ(a₁) Θ(1). Отсюда Θ(1)=1.

2. Если Θ – мультипликативная функция, то для попарно простых чисел a₁,a₂,…,a_k выполняется Θ(a₁a₂…a_k)= Θ(a₁)Θ(a₂)…Θ(a_k).

В частности,

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

Если функции Θ₁, Θ₂, … ,Θ_k – мультипликативные, то их произведение Θ=Θ₁Θ₂…Θ_k – также мультипликативная функция.
Если Θ(a) – мультипликативная функция, – каноническое разложение а, то, обозначив знакомсумму по всем делителям числа а, имеем

(Доказываем, раскрывая скобки в правой части).

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

Функция Эйлера φ(a) есть количество чисел ряда 0, 1, …, а–1, взаимно простых с а ().

φ(1)=1, φ(2)=1, φ(3)=2, φ(4)=2, φ(5)=4, φ(6)=2 и т. д.

Свойства функции Эйлера:

1) φ(1)=1;

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

2) φ(p)=p–1, где р – простое;

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

Действительно если р – простое, в ряду чисел 0, 1, …, p–1 не является взаимно простым с p только «0». Остальные p–1 чисел являются взаимно простыми с p в силу его простоты. Воспользовавшись определением функции Эйлера, получим искомое.

3)φ(p^α)=p^α^–¹(p–1) , где р – простое;

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

Рассмотрим ряд чисел 0, 1, … , p, … , 2p, … , 3p, … , p², … ,(p+1)p, … ,p^α--1.

В этом ряду не взаимно простыми с p^α являются только те числа, которые кратны p, то есть числа 0, p, 2p, …, (p^α^–¹–1)p. Таких чисел будет p^α^–¹. Всего же чисел в этом ряду будет p^α.

Таким образом, количество чисел в рассматриваемом ряду, взаимно простых с p^α будет p^α–p^α^–¹= p^α^–¹(p–1). Итак, φ(p^α)=p^α^–¹(p–1).

4)φ(a) – мультипликативная функция.

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

Действительно, по определению функции Эйлера, она задана для всех положительных чисел, и согласно свойству №1 функции Эйлера, φ(1)=1.

Покажем, что φ(p₁p₂)=φ(p₁)φ(p₂), если p₁, p₂ – простые числа.

Действительно, в ряду чисел 0, 1, … , p₁p₂—1 ровно p₂ чисел являются кратными p₁ и ровно p₁ чисел будут кратны p₂. Причем, в силу взаимной простоты p₁ и p₂, это будут разные числа, и только число «0» кратно и p₁, и p₂. Таким образом, чисел, кратных p₁ или p₂ будет p₁+p₂—1. Тогда чисел, взаимно простых и с p₁, и с p₂ будет ровно p₁p₂—p₁—p₂+1=p₁(p₂—1)—(p₂—1) =(p₁—1)(p₂—1)= φ(p₁)φ(p₂).

Покажем теперь, что для взаимно простых чисел a₁ и a₂справедливо φ(a₁a₂)=φ(a₁)φ(a₂).

Действительно, в ряду чисел 0, 1, … , a₁a₂—1 ровно a₁a₂—φ(a₁)a₂ чисел будут не взаимно простыми с a₁ и a₁a₂—φ(a₂)a₁ чисел – не взаимно простыми с a₂.

В то же время в ряду чисел 0, 1, … , a₁—1 ровно a₁— φ(a₁) чисел не будут являться взаимно простыми с a₁, в ряду чисел 0, 1, … , a₂—1 ровно a₂— φ(a₂) чисел не будут являться взаимно простыми с a₂. То есть среди чисел 0, 1, … , a₁a₂—1 не взаимно простыми одновременно и с a₁, и с a₂ будут являться (a₁—φ(a₁))(a₂—φ(a₂)) чисел.

Таким образом, общее количество взаимно простых с a₁a₂ среди натуральных чисел, меньших a₁a₂, есть

a₁a₂—( a₁a₂—φ(a₁)a₂+ a₁a₂—φ(a₂)a₁—(a₁—φ(a₁))(a₂—φ(a₂)))=

= a₁a₂— (a₁a₂—φ(a₁)a₂— φ(a₂)a₁+ φ(a₁)a₂+ φ(a₂)a₁— φ(a₁)φ(a₂))= φ(a₁)φ(a₂).

Итак, доказали, что функция Эйлера – мультипликативная.

j

Пример

Вычислим φ(28350322).

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

28350322=2·14175161=2·7·2025023=2·7²·289289=2·7³·41327=

=2·7³·11·3757=2·7³·11·13·289=2·7³·11·13·17².

φ(28350322)= φ(2·7³·11·13·17²)= φ(2) · φ(7³)· φ(11)· φ(13)· φ(17²)=

=1·7²·6·10·12·17·16=9596160.

Ответ: φ(28 350 322)=9 596 160.

1 2 3 4 5 6 7 8 9 ... 16

Похожие:

	Программа дисциплины «Численные методы» для специальности 090102. 65 «Компьютерная безопасность» Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов специальности 090102 «Компьютерная...		Рабочая программа для студентов очной формы обучения специальности... Иванов Д. И. Алгебра. Учебно-методический комплекс. Рабочая программа для студентов очной формы обучения, специальности 090301. 65...
	Учебно-методический комплекс рабочая программа для студентов специальности... Учебно-методический комплекс. Рабочая программа для студентов специальности 090102. 65 – «Компьютерная безопасность», очной формы...		Рабочая программа для студентов направления 090301. 65 Компьютерная... Хохлов А. Г. Математический анализ. Учебно-методический комплекс. Рабочая программа для студентов направления 090301. 65 Компьютерная...
	Программа дисциплины Операционные системы для специальности 090102.... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов специальности «090102 Компьютерная...		Рабочая программа для студентов направлений: 090301. 65 «Компьютерная безопасность» ...
	Задания для самостоятельного выполнения Для успешной подготовки к сдаче итогового теста попробуйте выполнить задания по основным темам курса		6454 Задания к контрольной работе по дисциплине Задания к контрольной работе по дисциплине «Педагогические коммуникации» (гос 2000) и методические указания для их выполнения для...
	Учебно-методический комплекс содержит учебно-методический план, темы... В. И. Гренц. Безопасность жизнедеятельности. Учебно-методический комплекс, рабочая учебная программа для студентов специальности...		Учебно-методический комплекс содержит учебно-методический план, темы... В. И. Гренц. Безопасность жизнедеятельности. Учебно-методический комплекс, рабочая учебная программа для студентов очного и заочного...
	Методические указания для ее выполнения по дисциплине Конфликтология... Задания к контрольной работе и методические указания для ее выполнения по дисциплине «Конфликтология в профессиональной деятельности»...		Рабочая программа составлена в соответствии с требованиями фгос впо... Платонов М. Л. Дополнительные главы теории чисел. Учебно-методический комплекс. Рабочая программа для студентов специальности 090900....
	Информационное письмо Уважаемые коллеги! Приглашаем Вас принять участие... Задания к контрольной работе и методические указания для ее выполнения по дисциплине «Конфликтология в профессиональной деятельности»...		Методические указания для выполнения самостоятельных работ По учебной дисциплине Методические указания и задания для студентов по выполнению самостоятельных работ по дисциплине «Бурение нефтяных и газовых скважин»для...
	«Компьютерная графика» Рабочая программа по дисциплине «Компьютерная графика» предназначена для реализации Государственного образовательного стандарта спо...		Рабочая программа По дисциплине: сд. 05 П ожарная техника для специальности... Рабочая программа составлена на основании гос спо №13-3203Б от 08. 02. 2002г и учебного плана для очной формы обучения стф 13-3203Б...

Школьные материалы

§2. Функция Эйлера.

2.1. Мультипликативные функции.

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

Похожие: