Сравнение, свойства сравнений.

 

Под операцией a mod m понимается операция взятия целочисленного остатка от деления числа a на число m, где a и m - целые числа.

Запись в модульной арифметике a ≡ b mod m или a = b + k·m, где a, b, m - целые числа, m ≠ 0, k - некоторое целое число. Отсюда следует, что m делит (a - b) нацело: m/(a-b) или (a-b)modm=0. Число b называют вычетом числа a по модулю m. Операция a mod m назыв-ся приведением числа a по модулю m

Ряд целых чисел от 0 до (m - 1) называется полным набором вычетов по модулю m. Для любого целого a (a>0) его вычет r по модулю m принадлежит интервалу r = . Число r можно найти перебором из системы:

{r=a-km, kÎz, r = 0,m 1.}, перебирая все значения k.

 

Свойства операций сравнения состоят из 3 групп:

I )Свойства, определяемые отношением эквивалентности

1) Рефлективность a ≡ a mod m

2) Симметричность a ≡ b mod m, b mod a ≡ m

a^j(m) mod m≡1 или    a^j(m)≡1mod m

3) Транзитивность. Если a ≡ b mod m и b mod c ≡ m, то a ≡ с mod m

II ) Свойства сравнимости по модулю 2 аналогичны свойствам равенства

1)Если a₁ ≡ b₁ modm и a₂ ≡ b₂ modm, то(a₁+a₂)mod m=(b₁+b₂)mod m

2)Если a₁ ≡ b₁ modm и a₂ ≡ b₂ modm, то(a₁*a₂)mod m=(b₁*b₂) modm

3) Если a ≡ b mod m, (k,m)=1, тогда a_k=b_mmod m

4) Если a ≡ b mod m, тогда a_k ≡b_k mod m, где k- натуральное.

 

III ) Свойства, отличающихся от свойств равенства

5) Имеем a, b – числа, m – модуль (a,b) ≡ d – НОД, (d,m)≡1, a ≡ b mod m, тогда a/d ≡ b/d mod m

6) b*a ≡ b mod m, d –такое что a/d, b/d, m/d, тогда a/d≡b/d mod (m/d)

7) (a+b) mod m ≡ [a mod m + b mod m] mod m

8) a*b mod m ≡ [(a mod m)*(b mod m)] mod m

 

Теорема Эйлера.

a^j(m)≡1 mod m

 

Классы вычетов. Полная и приведенная система вычетов

a ≡ b mod m

a ≡ c mod m

a ≡ d mod m

Сравнимость по mod n является отношением эквивалентности на множестве Z целых чисел. Классами вычетов по mod n, являются следующие множества - разбиения Z :

[О] = {..., -2n, -n, О, n, 2n, ...},

[1]= {..., -2n+l, -n+l, 1, n+l, 2n+l, ...},

...

[n-l]={..., -n-l, -1, n-l, 2n-l, 3n-l, ...}.

 

Пример. Определим классы вычетов по mod 7:

[0]= {..., -14, -7, 0, 7, 14, 21, ...},

[1]= {..., -13, -6, 1, 8, 15, 22, ...},

[2]= {..., -12, -5, 2, 9, 16, 23, ...},

[3]= {..., -11, -4, 3,10,17, 24, ...},

[4] ={..., -10, -3, 4, 11, 18, 25, ...},

[5] ={..., -9, -2, 5, 12, 19, 26, ...},

[6] ={..., -8, -1, 6, 13, 20, 27, ...}.

Число классов вычетов совпадает со значением модуля.

Число чисел в классе бесконечно.

В каждом классе свои числа – они больше нигде не встречаются – пересечений нет.

Полная система вычетов – когда из любого класса берется по одному представителю. Приведенная система вычетов – система, состоящая из взаимно простых вычетов.

 

Схема Горнера.

На вход: числа a, x, m.

На выходе: y или сообщение о неприменимости алгоритма.

1. Ввод a, x, m.

2. Если m = 0, то деление на ноль, выход.

3. Если a = 0, то результат равен y = 0, переход к пункту 9.

4. Если a = 1 или x = 0, то результат равен y = 1, переход к пункту 9.

5. Производим поиск для числа x верхней границы, являющейся степенью числа 2: число k такое, что x ≤ 2k.

  а) Пусть r = 2⁰ и k = 0; пока k < 32 (максимальное число разрядов в машинном слове) и r ≤ x, то возводим 2 в степень k: r = 2^k и увеличиваем k на единицу.

  б) Если k = 0 или k > 32, то задача не решается в установленных условиях, выход

6. Пусть r = a. Если степень x нечетна (остаток от деления на 2 равен единице), то y = a, иначе y = 1.

7. Для всех i=  выполняем следующие действия:

  а) r = [(r mod m)·(r mod m)] mod m = r² mod m;

  б) если i-ый бит числа x равен единице x_i =1, то y=(y*r)mod m.

8. Вывод результата y. Выход.

Вычислительная сложность схемы Горнера равна O(log³₂(x)).

Второй вариант схемы Горнера.

Первые 6 шагов совпадают с алгоритмом первого варианта схемы Горнера.

7. Пусть результат y=1, переменная циклa i=k−1 и r=a² mod m.

8. Если x_i = 1,    то y=(y² ·r)modm,

                         иначе y = y² mod m.

9. Вычислить i = i − 1. Если i > 1, то перейти к шагу 8.

10. Если x₀ = 1, то y = (y · a) mod m.

11. Вывод результата y. Выход.

 

Квадратичные вычеты

Продолжим исследовать вычеты.

Широкое применение в криптографии нашла формула:

xⁿ ≡ a mod m, n=2

xⁿ ≡ a mod p – квадратичный вычет

b сравнимо с a по модулю p, где b= x2 (числа х и а из интервала (1- (р-1))

p-простое число, р>2.

b ≡ a mod p

Пример

Пусть p=7 Все возможные остатки: 0,1,2,3,4,5,6

1² ≡1mod7      4² ≡ 2 mod 7

2² ≡ 4 mod7     5² ≡ 4 mod 7

3² ≡ 2 mod 7    6² ≡ 1 mod 7

Все остатки можно разделить на 2 класса:

1,2,4 – квадратичные вычеты

3,5,6 - квадратичные невычеты

Число квадратичных вычетов = числу квадр. невычетов и равно (p-1)/2

Пусть модуль составное число и раскладывается на 2 простых сомножителя:m=p*q=5*7=35

α=(p-1)(q-1)/4 – число квадратичных вычетов, которые являются взаимно простыми с m

4*6/4=6

12 ≡ 1 mod 35=1

22 ≡ 1 mod 35=4

32 ≡ 1 mod 35=9

42 ≡ 1 mod 35=16

52 ≡ 1 mod 35=25

62 ≡ 1 mod 35=1

72 ≡ 1 mod 35=14

82 ≡ 1 mod 35=29

92 ≡ 1 mod 35=11

…………………..

Число неповторяющихся вычетов – 11

Из них взаимнопростых чисел с 35 – 1, 4, 9, 11, 16, 29

Для нахождения квадратичных вычетов достаточно перебрать только половину.

Критерий Эйлера для определения является ли число а квадратичным вычетом.

– элемент принадлежит к классу квадратичных вычетов.

Если  , то элемент принадлежит к классу квадратичных

невычетов

 

⇐ Предыдущая12345Следующая ⇒

Поделиться: