Теоретические основы современной криптографии презентация

Содержание

I. Элементы теории чисел 1) Множества N и Z . 2) Делители и кратные d|a, a d 3) a d=>|d|< |a| 4) Простые и составные числа. 5) Деление с остатком.

Слайд 1Теоретические основы современной криптографии

Слайд 2I. Элементы теории чисел
1) Множества N и Z .
2) Делители и

кратные d|a, a d
3) a d=>|d|< |a|
4) Простые и составные числа.
5) Деление с остатком. Сравнения по модулю.



…

…

Слайд 3Теорема 1. (о делении с остатком).
Для любого целого числа

а и положительного целого числа n существует единственная пара целых числа q и r, для которых 0 < r < n и a = qn + r

Слайд 4Число q=[a/n] называется частным или неполным частным; число r,

обозначаемое a mod n, называется остатком.
Если r = 0, то пишут a mod n = 0
Если r = 1, то пишут a mod n = 1
в общем случае a mod n = r, т.е. a =[a/n]n +(a mod n) => a mod n = a -[a/n]n

Слайд 5Класс эквивалентности (класс вычетов):

Множество классов вычетов по модулю n:

Выбирая в

каждом классе по представителю, можно считать, что:









C = cl(a)={nk+a|k Z}

a


a


a

Zn = {C0 ,C1 ,… ,Cn-1 }

a


Zn = {0 ,1 ,… ,n-1}

Слайд 6 6) Общие делители. Наибольший общий делитель.

Среди всех общих делителей

данных чисел а и b можно выбрать наибольший общий делитель, который обозначают НОД(а, b).
Он определён, если хотя бы одно из чисел
а и b отлично от 0. Положим для удобства НОД(0,0) = 0.

Слайд 7Важные свойства общих делителей и наибольшего
общего делителя:
если d

| а и d | b, то d (а + b) и d | (а - b) (1)
если d| а и d | b, то d(ах + bу) при любых целых
х и у. (2)
Если а | b, то |а| ≤ |b| или b = 0, поэтому
если а | b и b | a, то а = ± b.
Кроме того,
НОД (а,b) = НОД (b,а),
НОД (а,b) = НОД(-а, b),
НОД (а,b) = НОД (|а|, |b|),
НОД (a,0) = |а|,
НОД (а, ka) = |а| при всяком k∈Z.

Слайд 8 Теорема 2.

Наибольший общий делитель целых чисел а и

b, не равных 0 одновременно, является наименьшим положительным элементом множества {ах + bу : x,у∈Z} целочисленных линейных комбинаций чисел а и b

Слайд 9 Доказательство.
Пусть наименьший положительный элемент этого множества равен s.

Тогда s = ах + bу для некоторых
x,у ∈Z. Положим q =[a/s].
Согласно (a mod n = a – [a/n]n)
a mod s = a – qs = a – q(ax + by) = a(1 – qx) + b(-qy)
и потому остаток от деления а на s тоже является линейной комбинацией а и b. Но s был наименьшей положительной комбинацией такого вида, =>
|s|< a mod s. Итак, a mod s - линейная комбинация, а s – наименьшая линейная комбинация => a mod s>s (если a mod s положительно) или a mod s=0.

Слайд 10 Но! Остаток строго меньше делителя => a mod s

s => a mod s не может быть положительным. Так что a mod s = 0 и s|a. По аналогичным причинам верно s|b. Таким образом, s =НОД (а,b) делит как а, так и b, а потому делит и s = ах + bу.
Поскольку s > 0, отсюда следует, что
НОД (а,b) ≤ s. Таким образом, НОД (а,b) ≥ s и НОД (а,b) ≤ s, так что НОД (а,b) = s , ч.т.д.

Слайд 11Следствие 2.1
Наибольший общий делитель двух целых чисел

кратен любому их общему делителю.

Слайд 12 Доказательство.
По теореме 2 НОД (а,b) является линейной комбинацией

а и b. Из свойства 2 вытекает, что
d|(ax + by), но НОД = min(ax + by), следовательно, делитель а и b является делителем любой комбинации (ax + by), в том числе и наименьшей, ч.т.д.

Слайд 13Следствие 2.2
Для любых целых чисел а и b

и неотрицательного целого числа n выполняется соотношение НОД (аn,bn) = n НОД (а,b).

Слайд 14 Доказательство.
Элементы вида (апх + bпу) получаются из

элементов вида (ах + bу) умножением на n, так что это относится и к наименьшему элементу такого вида, ч.т.д.

Слайд 15 Следствие 2.3
Для любых положительных целых чисел п,

а и b из того, что п|аb и НОД(а, п) = 1 следует п|b.

Слайд 16 Доказательство.
НОД(а, п) = 1 => a не кратно n

=>
b кратно n => n|b
ч.т.д.



Слайд 17 7) Взаимно простые числа.

  Целые числа а и b

взаимно просты, если НОД (а,b) = 1.

Слайд 18Теорема 3.
Если НОД (а,p) = 1 и НОД

(b,p) = 1, то НОД (аb,p) = 1 (для любых целых чисел а, b, p).

Слайд 19 Доказательство.

По теореме 2 найдутся целые числа х, у, x´

и y´ - для которых,
ах + ру = 1,
bx´ + py´= 1.
Перемножая эти равенства, мы видим, что
ab(xx´) + p(ybx´ + y´ax + pyy´ )= 1,
так что 1 является целочисленной линейной комбинацией ab и p; осталось сослаться на теорему 2, ч.т.д.

Слайд 208) Разложение на простые множители.

Слайд 21 Теорема 4.
Если простое число p делит произведение

двух целых чисел а и b, то p | а или p | b.

Слайд 22 Доказательство.
Если это не так и p не

делит ни а, ни b, то p взаимно просто с этими числами (других делителей у p нет) и потому взаимно просто с их произведением (теорема 3) => ab не кратно p => противоречие, ч.т.д.

Слайд 23Теорема 5.
(существование и единственность разложения),
(основная теорема арифметики).
Всякое

составное число а единственным образом представляется в виде
a = p1e1 p2e2· …· prer,
  где p1 Без доказательства. 

Слайд 249) Наибольший общий делитель.
Если
a = p1e1 p2e2· …· prer
и
b =

p1 f1 p2 f2· …· pr fr
то
НОД(a,b) = p1 min(e1, f1) · p2 min(e2, f2) …· pr min(er, fr)

Слайд 25 Теорема 6.
(рекуррентная формула для НОД).
Пусть а –

целое неотрицательное, а b – целое положительное число.
Тогда НОД (а,b) = НОД (b , а mod b).

Слайд 26 Доказательство.
Пара (а,b) имеет те же делители, что

и пара (b, а mod b):
а mod b = а – [а/ b] b = 1⋅а + (-q)⋅b
(a mod b является целочисленной линейной комбинацией а и b и наоборот). Поэтому и наибольший общий делитель у этих пар одинаковый, ч.т.д.

Слайд 2710) Алгоритм Евклида.
Euclid (а,b)
if b = 0

then return а
else return Euclid (b, а mod b)


Число рекурсивных вызовов составляет O(logb).

Слайд 2811) Расширенный алгоритм Евклида.
d = НОД (а,b) = ax +

by
НОД (а,b) = min (ax + by) при аb ≠ 0

Extended-Euclid(a,b)
if b=0
then return (a,1,0)
(d′,x′,y′):=Extended-Euclid(b, a mod b)
(d,x,y):=(d′,x′,y′-[a/b]⋅y′)
return (d,x,y)

Слайд 29II. Элементы общей алгебры.
1) Группа.
Алгебраической операцией (на множестве S)

называется отображение * : S×S→S, т.е. отображение, обладающее свойством замкнутости.

Слайд 30 Множество S с определённой на нём алгебраической операцией * называется группой,

если выполнены следующие свойства:
1. Ассоциативность: a * (b * c) = (a * b) * c
для любых a, b, c из S.
2. Существование нейтрального элемента: существует элемент е из S, для которого е*a = а*е = а для любого a из S (такой элемент может быть только один, так как е = e*е’= e’ для любых двух элементов e и e’ с таким свойством).
3. Существование обратного элемента: для всякого a из S найдется единственный элемент b из S, для которого a * b = b * a = e

Слайд 31Условия 1-3 называются аксиомами группы.
Группа с коммутативной операцией называется коммутативной

или абелевой.
а * b = b * а для любых а, b из S

Слайд 32 Обычно групповую операцию * обозначают специальными символами, чаще всего символами •

или +, называя a·b произведением, а (a + b ) – суммой элементов а, b из S. В первом случае нейтральный элемент называют единицей (обозначение: 1), симметричный элемент – обратным (обозначение: а-1), а саму группу S –мультипликативной.
Во втором случае нейтральный элемент называют нулем (обозначение: 0), симметричный – противоположным (обозначение: -а), а саму группу S – аддитивной.

Слайд 332) Кольцо. Определение, простейшие свойства.

Непустое множество К, наделенное двумя алгебраическими

операциями - сложением и умножением, называется кольцом, если эти операции удовлетворяют следующим аксиомам:

Слайд 34для любых а, b, с из К
1) (a + b) +

c = a + (b + c);
2) Существует 0 из К : a + 0 = 0 + a;
3) Для любого a из К существует -a из К :
a + (-a) = (-a) + a = 0;
4) a + b = b + a;
5) (ab)c = a(bc);
6) (a + b)c = ab + bc, a(b + c) = ab +ac.


Слайд 35Кольцо называется коммутативным, если умножение в нем коммутативно, кольцо называется кольцом

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

Слайд 36Простейшие свойства кольца:
1. Кольцо обладает всеми свойствами аддитивной абелевой группы:

а) существует, и притом единственный, нулевой элемент 0;
б) для каждого элемента a существует, и притом единственный, противоположный элемент - а;
в) для любых элементов а, b ∈ К существует, и притом единственное, решение уравнения x + а = b; это решение называется разностью элементов b и а и обозначается символом b - a. Итак, b – a = b + (-a).

Слайд 372. В кольце умножение дистрибутивно относительно вычитания:
a(b – c) = ab –

ac,
(a – b)c = ac – bc, для любых a,b,c ∈ K.
Это следует из того, что b = (b - с) + с и аb = а(b - с) + ас.

Слайд 383. В кольце для любого элемента а:
a⋅0 = 0⋅a =

0.
Это следует из дистрибутивности умножения относительно вычитания:
а⋅0 = а(b - b) = аb - аb = 0.

Слайд 394. В кольце для любых элементов а,b:
(-а)b = а(-b) =

-аb.
Это следует из того, что аb + (-а)b = (а + (-а))b = 0b = 0.

Следствие: (-а)(-b) = аb, ∀а,b ∈ К.

Слайд 405. В кольце с единицей для любого элемента а:
(-1)а = а(-1)=-а.
Это

следует из того, что
а + (-1)а = 1а + (-1)а = (1 + (-1))а = 0а = 0.

Слайд 416. В кольце с единицей, содержащем не менее двух элементов:
1≠0.

Действительно, если 0 = 1, то существует а ∈ К : а ≠ 0, а ≠ 1. Тогда из равенства 0=1 следует, что 0а = 1а, т.е. 0 = а, но а ≠ 0.

Слайд 42 7. В кольце с единицей множество обратимых (по умножению), элементов

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

Слайд 43Делители нуля.

Ненулевые элементы a и b кольца называются
делителями нуля, если

ab = 0. При этом элемент a называется левым делителем нуля, а элемент b – правым.






( )( ) ( )

1 0 0 0 0 0
0 0 1 1 0 0

=

Слайд 443) Кольцо вычетов.
1. Замкнутость: Ca+b ∈ Zn
2.

Ассоциативность: Ca+(Cb+Cd)=(Ca+Cb)+Cd
3. Существует нейтральный элемент C0:
Ca+C0=C0+Ca=Ca
4. Существует противоположный элемент:





-C =

a

{

C ,если а=0

0

C ,если а>0

n-a

Слайд 45Определим на Zn операцию умножения. Положим CaCb=Cr , где r ≡

ab(mod n). Эта операция обладает следующими свойствами:
1. CaCb=CbCa , так как CaCb-класс, в который входит ab, а ab=ba.
2. (CaCb)Cd=Ca(CbCd), так как оба произведения представляют собой один и тот же класс, в который входит число (ab)d=a(bd).
3. Существует единица C1, так как CaC1=C1Ca=Ca





Слайд 464. (Ca +Cb)Cd=CaCd +CbCd, так как оба произведения представляют собой класс,

в который входит число (a+b)d=ad+bd.
5. Если n – составное число, то в кольце Zn есть делители нуля, так как если n=ab, где 1





Слайд 47Таким образом, Zn- конечное коммутативное кольцо с единицей, которое имеет делители

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





Похожие презентации

Основы информационной безопасности. Политика безопасности, регламентирующие документы. (Тема 2.3) 248
Об’єкти, функції і події в JavaScript. (Лекція 7) 380
Общее введение в компьютерную графику 364
Моделирования бизнес-процесса 246
Сенсоры роботов 406
Программные средства информатизации 512

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

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

Для правообладателей

Яндекс.Метрика