Элементы дискретной математики

Сентябрь 3, 2022

Главная
Алгебра
Элементы дискретной математики

Содержание

2. Модульная арифметика a=cn+res(a) Переместительный закон (коммутативный) (a+b)(modn)=(b+a)(modn) r=a(modn) Сочетальный закон (ассоциативный) (a+(b+c))(modn)=((a+b)+c)(modn) Распределительный закон a(b+c)(modn)=ab(modn)+ac(modn) (a+b)(modn)=[a(modn)+b(modn)](modn)
3. Разложение на множители Число p называется простым, если оно не имеет делителей кроме тривиальных (1,-1, p,
4. Наибольший общий делитель Наибольшим общим делителем (НОД) двух чисел v и u называется наибольшее целое число,
5. Теоремы Эйлера и Ферма Функция Эйлера ϕ(x). Определяет число натуральных чисел меньших x и взаимно простых
6. Обращение элемента по модулю n Обратный элемент x к числу a - это такое целое число,
7. Пример нахождения обратного элемента n=17, a=13, a-1=? 1. используя алгоритм Евклида, находим НОД(17,13), 17=1*13+4 13=3*4+1, НОД=1
8. Пример 2 1. используя алгоритм Евклида, находим НОД(97,77), 97=1*77+20 77=3*20+17 20=1*17+3 17=5*3+2 3=2*1+1, НОД=1 1=3-2*1 2=17-5*3
10. Возведение в степень y=ax(modn) Прямой способ: a·a·…a·a(modn) 1. Быстрый способ возведения: Пример: 337(mod7) Представим показатель степени
11. Возведение в степень 2. Быстрый способ возведения Д.Кнута. - представим показатель степени в двоичном виде; -
12. Вычисление дискретного логарифма logay=x(modn) y=ax(modn) Сложность вычислений для операции дискретного логарифмирования: N≅O((n)1/2). Нахождение дискретного логарифма методом
13. Проверка чисел на простоту Тест Ферма (вероятностный тест). В его основе лежит теорема Ферма, т. е.
14. Тест Ферма Пример. n=341, b=2. 2340=(210)34mod341=(1024(mod341))10(mod341)=1. Но с другой стороны 341=31⋅11, т.е. число составное. Для любого
15. Простые числа Простые числа Числа Кармайкла Псевдопростые числа по основанию а Сильно псевдопростые числа по основанию
16. Пусть число n нечетное и n − 1 = 2sr, где r — нечетное. a –
17. Тест Рабина- Миллера - Тест-Рабина-Миллера позволяет отсеять часть псевдопростых чисел Вероятность ошибки для Теста Рабина-Миллера P(n-составное)
18. Тест Миллера - Рабина Пусть число n нечетное и n − 1 = 2sr, где r
20. Скачать презентацию

Слайд 2

Модульная арифметика
a=cn+res(a)
Переместительный закон (коммутативный)
(a+b)(modn)=(b+a)(modn)
r=a(modn)
Сочетальный закон (ассоциативный)
(a+(b+c))(modn)=((a+b)+c)(modn)
Распределительный закон
a(b+c)(modn)=ab(modn)+ac(modn)
(a+b)(modn)=[a(modn)+b(modn)](modn)
ab(modn)=[a(modn)b(modn)](modn)

Слайд 3

Разложение на множители
Число p называется простым, если оно не имеет делителей

кроме тривиальных (1,-1, p, -p).

pi - различные простые числа

ai - положительные целые числа

Пример:

Слайд 4

Наибольший общий делитель
Наибольшим общим делителем (НОД) двух чисел v и u

называется наибольшее целое число, которое делит оба числа.
Нахождение НОД:
Прямой метод - разложение чисел на множители.
u=210 = 2•3•5•7, v=135=3•3•3•5. НОД(210,135)=15
Алгоритм Евклида.
u=a1v+b1
v=a2b1+b2
···
bk-3=ak-1bk-2+bk-1
bk-2=akbk-1+bk

Если bk=1, то НОД(u,v)=1,
если bk=0, то НОД(u,v)= bk-1

210=1*135+75
135=1*75+60
75=1*60+15
60=14*15+0

Числа u и v называются взаимопростыми, если НОД(u,v)=1

Слайд 5

Теоремы Эйлера и Ферма
Функция Эйлера ϕ(x). Определяет число натуральных чисел меньших

x и взаимно простых с x. ϕ(1)=1.
ϕ(6)=2. ϕ(xy)= ϕ(x)• ϕ(y). ϕ(p)=p-1, если p простое.
Теорема Эйлера:
Если a и m взаимно простые числа,то
aφ(m)=1(modm) a=5, m=6 52(mod6)=25(mod6)=1
Теорема Ферма:
Если р простое число и p не делит a, то
ap-1=1(modp) a=2, p=7 26(mod7)=64(mod7)=1

Слайд 6

Обращение элемента по модулю n
Обратный элемент x к числу a -

это такое целое число, которое удовлетворяет сравнению
xa≡1(modn).
Обозначение обратного элемента - a-1.
Обратный элемент существует только тогда, когда НОД(a,n)=1.
Пример. n=7,a=5. a-1=3. 5•3=15, 15(mod7)=1.
Нахождение обратного элемента:
Известно представление НОД в виде
НОД(a,n)=z1a+z2n,
где z1,z2 –целые не обязательно положительные числа.
Так как НОД(a,n)=1, то
1= (z1a+z2n)modn=z1a(modn). Следовательно,
a-1 =z1 (modn)

Слайд 7

Пример нахождения обратного элемента
n=17, a=13, a-1=?
1. используя алгоритм Евклида, находим НОД(17,13),

17=1*13+4
13=3*4+1, НОД=1

2. Найдем числа z1 и z2, удовлетворяющие условию:
1= (z1*13+z2*17)mod17=z1*13(mod17).

1=13-3*4
4=17-1*13
1=13-3*4=13-3*(17-1*13)=4*13-3*17
z1=4, z2=-3

3. a-1= z1=4

4. Проверка 4*13(mod17)=52(mod17)=1

Слайд 8

Пример 2
1. используя алгоритм Евклида, находим НОД(97,77),
97=177+20
77=320+17
20=117+3
17=53+2
3=21+1, НОД=1
1=3-21
2=17-53
3=20-117
17=77-320
20=97-177
3-(17-53)1=63-171=
=6(20-117)-171=620-717=
=620-7(77-320)=2720-777=

=27*(97-77)-7*77=27*97-34*77

Получили представление 1=(z1*97+z2*77)mod97=z2*77(mod97)

a-1= z2=-34(mod97)= 63

Проверка 63*77(mod97)=4851(mod97)=1

Слайд 9

Слайд 10

Возведение в степень
y=ax(modn)
Прямой способ: a·a·…a·a(modn)
1. Быстрый способ возведения: Пример: 337(mod7)
Представим

показатель степени в двоичном виде
x=2k-1xk-1+2kxk+…+22x2+21x1+20x0
37=32+4+1=100101
Найдем k степеней основания a путем последовательного
возведения в квадрат a. 31=3(mod7), 32=2(mod7), 34=4(mod7),
38=2(mod7), 316=4(mod7), 332=2(mod7).
Перемножим между собой только те степени, которым
соответствуют ненулевые коэффициенты в двоичном
представлении числа x.
31=3(mod7), 34=4(mod7), 332=2(mod7).
y=2·4 ·3(mod7)=3.

Слайд 11

Возведение в степень
2. Быстрый способ возведения Д.Кнута.
- представим показатель степени в

двоичном виде;
-         каждую единице заменим парой букв КУ (квадрат+умножение);
-         каждый ноль заменим буквой К (квадрат);
-         в образовавшейся последовательности вычеркнем первую пару КУ;
-         над основанием a проводим вычисления, согласно полученной последовательности.
Пример: 337(mod7)
37 = 100101 = КУКККУККУ= КККУККУ
3→32(mod7)=2→22(mod7)=4→42(mod7)=2→2⋅3(mod7)=6→62(mod7)= 1→12(mod7)= 1→1⋅3(mod7)=3
Сложность вычислений для операции возведения в степень: N≅O(2logx).

Слайд 12

Вычисление дискретного логарифма
logay=x(modn) y=ax(modn)
Сложность вычислений для операции дискретного логарифмирования: N≅O((n)1/2).
Нахождение дискретного

логарифма методом «встречи посредине»
Строим базу данных размера O((n)1/2) вида az(modn) для случайных чисел z∈[1,n] и сортируем ее.
Для случайных чисел b, таких что НОД(b,n-1)=1 вычисляем yb(modn) и сравниваем с числами базы данных.
С большой вероятностью после нескольких попыток получаем
az(modn)= yb(modn)
Возводим обе части в степень b-1, получим az· b-1 (modn)= y (modn). Откуда следует
zb-1=x.
Этот метод имеет сложость Nt≅O((n)1/2logn), Nv≅O((n)1/2)

Слайд 13

Проверка чисел на простоту
Тест Ферма (вероятностный тест).
В его основе лежит теорема

Ферма, т. е. если n- простое число и b взаимопростое с n, то bn-1=1(modn).
Для проверки нечетного числа n на простоту необходимо:
Прогенерировать k’ чисел bi , i=1,2,…,k’, biПроверить, что НОД(n, bi)=1. Невзаимопростые с n числа отбросить. Остается k взаимопростых с n чисел. (для выполнения проверки используется алгоритм Евклида).
Проверить выполнение сравнения bn-1=1(modn) для i= 1,2,…. Если оно не выполняется хотя бы один раз, то n составное. Если выполняется для всех i, то n возможно простое
Вероятность ошибки P(n-составное) =1/2k
Тест не выполняется для так называемых псевдопростых чисел.

Слайд 14

Тест Ферма
Пример. n=341, b=2. 2340=(210)34mod341=(1024(mod341))10(mod341)=1.
Но с другой стороны 341=31⋅11, т.е. число

составное.
Для любого b имеется бесконечно много псевдопростых чисел, однако их относительное количество не такое уж большое. Так для b=2 существует всего 21853 псевдопростых чисел среди чисел от 1 до 25⋅109.
Особый случай составляют составные числа, условия т. Ферма для которых выполняются при любом b. Это числа Кармайкла.
Всего имеется 2163 числа Кармайкла в диапазоне 1 до 25⋅109, а в диапазоне 1 до 1⋅105 всего 16 таких чисел: 561,1105,1729….75361. В тесте Ферма эти числа не различимы.

Слайд 15

Простые числа
Простые числа
Числа Кармайкла
Псевдопростые числа
по основанию а
Сильно
псевдопростые
числа
по основанию а

Слайд 16

Пусть число n нечетное и n − 1 = 2sr, где r — нечетное. a

– произвольное целое число.1≤а ≤n-1 взаимно простое с n.
Число n называется сильно псевдопростым по основанию а, если ar≡1(modn) или если существует такое целое j, 0≤j ≤s-1, что .

Пусть число n нечетное и n − 1 = 2sr, где r — нечетное. a – произвольное целое число.1≤а ≤n-1 взаимно простое с n.
Число n называется сильно псевдопростым по основанию а, если ar≡1(modn) или если существует такое целое j, 0≤j ≤s-1, что .

Слайд 17

Тест Рабина- Миллера -
Тест-Рабина-Миллера позволяет отсеять часть псевдопростых чисел
Вероятность ошибки для

Теста Рабина-Миллера
P(n-составное) < (1/4)k

Слайд 18

Тест Миллера - Рабина
Пусть число n нечетное и n − 1 = 2sr, где r

— нечетное. Если n простое, то для любого a ≥ 2, взаимно простого с n, выполняется условие. Разложим an-1-1 на множители

В последнем произведении хотя бы одна из скобок делится на n, то есть либо ar ≡ 1 (mod n), либо среди чисел ar, a2r, …, a2 s−1r найдется сравнимое с −1 по модулю n.

Элементы дискретной математики

Содержание

Разложение на множителиЧисло p называется простым, если оно не имеет делителей

Наибольший общий делительНаибольшим общим делителем (НОД) двух чисел v и u

Теоремы Эйлера и ФермаФункция Эйлера ϕ(x). Определяет число натуральных чисел меньших

Обращение элемента по модулю nОбратный элемент x к числу a -

Пример нахождения обратного элементаn=17, a=13, a-1=?1. используя алгоритм Евклида, находим НОД(17,13),

Пример 21. используя алгоритм Евклида, находим НОД(97,77), 97=1*77+2077=3*20+1720=1*17+317=5*3+23=2*1+1, НОД=11=3-2*12=17-5*33=20-1*1717=77-3*2020=97-1*773-(17-5*3)*1=6*3-17*1= =6*(20-1*17)-17*1=6*20-7*17= =6*20-7*(77-3*20)=27*20-7*77=

Возведение в степеньy=ax(modn) Прямой способ: a·a·…a·a(modn)1. Быстрый способ возведения: Пример: 337(mod7)Представим

Возведение в степень2. Быстрый способ возведения Д.Кнута.- представим показатель степени в

Вычисление дискретного логарифмаlogay=x(modn) y=ax(modn)Сложность вычислений для операции дискретного логарифмирования: N≅O((n)1/2). Нахождение дискретного

Проверка чисел на простотуТест Ферма (вероятностный тест).В его основе лежит теорема

Тест ФермаПример. n=341, b=2. 2340=(210)34mod341=(1024(mod341))10(mod341)=1.Но с другой стороны 341=31⋅11, т.е. число

Простые числаПростые числаЧисла КармайклаПсевдопростые числапо основанию аСильно псевдопростые числапо основанию а