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

Презентация на тему Презентация на тему Теоретические основы современной криптографии, предмет презентации: Информатика. Этот материал содержит 47 слайдов. Красочные слайды и илюстрации помогут Вам заинтересовать свою аудиторию. Для просмотра воспользуйтесь проигрывателем, если материал оказался полезным для Вас - поделитесь им с друзьями с помощью социальных кнопок и добавьте наш сайт презентаций ThePresentation.ru в закладки!

Слайды и текст этой презентации

Слайд 1
Текст слайда:

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


Слайд 2
Текст слайда:

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

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, ч.т.д.


Слайд 20
Текст слайда:

8) Разложение на простые множители.


Слайд 21
Текст слайда:

Теорема 4.

Если простое число p делит произведение двух целых чисел а и b, то p | а или p | b.


Слайд 22
Текст слайда:

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

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


Слайд 23
Текст слайда:

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

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


Слайд 24
Текст слайда:

9) Наибольший общий делитель.
Если
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 и наоборот). Поэтому и наибольший общий делитель у этих пар одинаковый, ч.т.д.


Слайд 27
Текст слайда:

10) Алгоритм Евклида.
Euclid (а,b)
if b = 0
then return а
else return Euclid (b, а mod b)


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


Слайд 28
Текст слайда:

11) Расширенный алгоритм Евклида.
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)


Слайд 29
Текст слайда:

II. Элементы общей алгебры.

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 – аддитивной.


Слайд 33
Текст слайда:

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

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


Слайд 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).


Слайд 37
Текст слайда:

2. В кольце умножение дистрибутивно относительно вычитания:
a(b – c) = ab – ac,
(a – b)c = ac – bc, для любых a,b,c ∈ K.
Это следует из того, что b = (b - с) + с и аb = а(b - с) + ас.


Слайд 38
Текст слайда:

3. В кольце для любого элемента а:
a⋅0 = 0⋅a = 0.
Это следует из дистрибутивности умножения относительно вычитания:
а⋅0 = а(b - b) = аb - аb = 0.


Слайд 39
Текст слайда:

4. В кольце для любых элементов а,b:
(-а)b = а(-b) = -аb.
Это следует из того, что аb + (-а)b = (а + (-а))b = 0b = 0.

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


Слайд 40
Текст слайда:

5. В кольце с единицей для любого элемента а:
(-1)а = а(-1)=-а.
Это следует из того, что
а + (-1)а = 1а + (-1)а = (1 + (-1))а = 0а = 0.


Слайд 41
Текст слайда:

6. В кольце с единицей, содержащем не менее двух элементов:
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

=


Слайд 44
Текст слайда:

3) Кольцо вычетов.
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






Слайд 46
Текст слайда:

4. (Ca +Cb)Cd=CaCd +CbCd, так как оба произведения представляют собой класс, в который входит число (a+b)d=ad+bd.
5. Если n – составное число, то в кольце Zn есть делители нуля, так как если n=ab, где 1






Слайд 47
Текст слайда:

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






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

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

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

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

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


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

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