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

делителей кроме тривиальных (1,-1, p, -p).
pi - различные простые числа
ai

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

Пример:

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

меньших 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

- это такое целое число, которое удовлетворяет сравнению

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)

НОД(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

НОД=1
1=3-2*1
2=17-5*3
3=20-1*17
17=77-3*20
20=97-1*77
3-(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=
=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

Пример: 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.

в двоичном виде;
-         каждую единице заменим парой букв КУ (квадрат+умножение);
-        

каждый ноль заменим буквой К (квадрат);
-         в образовавшейся последовательности вычеркнем первую пару КУ;
-         над основанием 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).

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)

теорема Ферма, т. е. если 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
 
Тест не выполняется для так называемых псевдопростых чисел.

число составное.

Для любого b имеется бесконечно много псевдопростых чисел, однако

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

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

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

r — нечетное. Если n простое, то для любого a ≥ 2,

взаимно простого с n, выполняется условие. Разложим an-1-1 на множители

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