Вопросы и задания к лабораторной работе № 1
Лабораторный практикум к курсу «Математические основы информационной безопасности»
Лабораторная работа № 1. Основы теории чисел.
Постановка задачи
Цель работы: изучить основные понятия, теоремы и алгоритмы теории чисел, используемые в криптографии.
Задание: Составить схему алгоритма и написать программу, реализующую следующие функции:
–нахождения наибольшего общего делителя двух чисел на основе алгоритма Евклида;
–нахождения наибольшего общего делителя системы чисел на основе канонического разложения числа;
–нахождения последовательности простых чисел, не превосходящих данного N, на основе алгоритма Эратосфена.
Полученные алгоритмы оформить в виде отдельного модуля (библиотеки).
Теоретические предпосылки
Основа любого криптографического алгоритма базируется на элементах теории чисел, изучению которых и посвящена данная лабораторная работа. Теория чисел занимается изучением свойств целых чисел. Сразу оговоримся, что при изложении теоретического материала мы будем обозначать буквами только целые числа. [4, 25]
1. Основные понятия.
Определение 1. Если a делится на b нацело, мы будем говорить, что b делит a. При этом а называется кратным числа b, b – делителем числа а. Число а можно представить как
,
где q – полное частное.
Теорема 1 Если в равенстве вида 
относительно всех членов, кроме какого-либо одного, известно, что они кратны b, то и этот один член кратен b.
|
|
|
Доказательство:
Пусть таким одним членом будет k. Имеем
Перенесем в правую часть равенства все члены, кроме k.
Таким образом, k представляется произведением b на целое число ( 
) и тем самым делится на b по определению 1. Что и требовалось доказать.
Теорема 2 (о делении с остатком).
Всякое целое а представляется единственным способом с помощью положительного целого b равенством вида
 ; 
| (7.1) |
Доказательство
Действительно, одно представление числа а равенством вида (7.1) получим, взяв 
равным наибольшему кратному числа b, не превосходящему а.
Допустим существование другого представления числа а еще одним равенством вида (7.1)
 ; 
| (7.2) |
Вычтем почленно равенство (7.2) из (7.1), получим
| (7.3) |
Согласно Теореме 1 разность 
кратна b. С другой стороны разность двух неотрицательных чисел меньших b сама будет численно меньше b. Числом кратным b и численно меньшим b является 0. Если 
, то из равенства (7.3) следует, что и 
. Таким образом, второе представление числа а тождественно первому. Теорема 2 доказана.
|
|
|
Число q называется неполным частным, а число r – остатком от деления а на b.
2. Наибольший общий делитель.
Определение 2.Число, которое делит каждое из чисел а и b, называется общим делителем чисел а и b.
Определение 3. Наибольший из делителей чисел а и b называется наибольшим общим делителем (НОД) этой пары чисел.
Обозначение. НОД (a,b) º (а,b).
Определение 4. Если НОД(а,b)=1, то числа а и b называются попарно простыми.
Теорема 3. Если а кратно b, то совокупность общих делителей чисел а и b совпадает с совокупностью делителей одного числа b; в частности (а,b)=b.
Доказательство:
Действительно, всякий общий делитель чисел а и b является делителем и одного b. Раз а кратно b, то, согласно Теореме 1, всякий делитель числа b является также делителем числа а, т.е. является общим делителем чисел а и b.
Таким образом, совокупность общих делителей чисел а и b совпадает с совокупностью делителей одного b. Поскольку наибольший делитель числа b есть само b, то (а,b)=b.
Теорема 4. Если , то совокупность общих делителей чисел а и b совпадает с совокупностью делителей чисел b и c; в частности (а,b)=(b,c).
Доказательство:
Действительно, всякий общий делитель чисел а и b согласно Теореме 3 является и общим делителем чисел b и c. Всякий общий делитель чисел b и c делит а и, следовательно, является общим делителем чисел а и b.
|
|
|
Таким образом, общие делители чисел а и b те же, что и общие делители чисел b и c. В частности, должны совпадать и наибольшие из этих делителей, (а,b)=(b,c).
Алгоритм Евклида. Применяется для отыскания НОД двух чисел.
Пусть а,b – положительные целые и a>b.
Согласно Теореме 3 находим ряд равенств:
| (7.4) |
заканчивающийся, когда получается некоторое rn+1=0. Последнее неизбежно, так как ряд b,r2,r3,… не может содержать более чем b положительных чисел.
Таким образом, НОД чисел a и b равен последнему не равному нулю остатку алгоритма Евклида. Поскольку, согласно Теореме 4
Пример. Отыскать НОД(25,9) - ?
Алгоритм Эратосфена
Определение 5. Всякое а>1 будем называть простым, если у него нет других делителей, кроме 1 и самого себя, иначе – составным.
Алгоритм Эратосфена построения последовательности простых чисел в ряду целых чисел, не превосходящих данного целого N.
Выписываем ряд чисел
| 1,2,…, N | (5) |
Первое простое число в ряду (5) – 2. Вычеркиваем из ряда (5) все числа кратные 2, кроме самого числа 2. Первое, оставшееся после 2, простое число – 3. Вычеркиваем из ряда (5) все числа кратные 3, кроме самого числа 3. Первое, следующее за 3, невычеркнутое простое число 5. Вычеркиваем из ряда (5) все числа кратные 5, кроме числа 5. И т.д.
|
|
|
Выводы: 1) приступая к вычеркиванию кратных простого p, это вычеркивание следует начать с p2
2) составление последовательности простых чисел, не превосходящих N, закончено, как только вычеркнуты все составные кратные простых, не превосходящих 
.
Например, для числа 38
38 = 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37
Теорема 5. Всякое целое, большее единицы, разлагается на произведение простых сомножителей и притом единственным способом:
 ,
| (7.6) |
где p1,…,pK – простые сомножители числа а,
a1,…,aK – кратности вхождения соответственно сомножителей p1,…,pK в число а.
Разложение (7.6) числа a на простые сомножители называется каноническим.
Пример. 
Теорема: НОД нескольких чисел является произведением степеней вида pa, где p – общий простой делитель всех этих чисел; a - наименьший из показателей, с которыми p входит в их канонические разложения.
Пример.НОД(50 , 160 , 1960 )
50=21*52 160=25 *51 1960=23*51*72
НОД(50 , 160 , 1960 )=21*51=10
Упражнения
1. Найти НОД(396,1452)
2. Найти каноническое разложение числа а)2156; б)1934; в)1132.
3. Являются ли числа попарно простыми
а) (678, 941); б) (243, 1485); в) (535, 321)?
Вопросы и задания к лабораторной работе № 1
1. Докажите теорему о делении с остатком.
2. Дайте понятие НОД двух чисел. Какой алгоритм используется для его нахождения?
3. Какие числа называются простыми, составными?
5. Какое разложение целого числа называется каноническим?
Дата добавления: 2018-06-01; просмотров: 498; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!