Алгоритм Евклида. Получение РАЕ. Решето Эратосфена.

Алгоритм Евклида. Получение РАЕ. Решето Эратосфена.

Алгоритм Евклида дает правило вычисления наибольшего общего делителя (НОД) 2-х натуральных чисел.

(a,b)= d, где d – НОД (Наибольший общий делитель)

НОК – наименьшее общее кратное

[a,b] = k, где k – НОК (Наименьшим общим кратным)

Если НОД(а, b)= 1, то числа а и b взаимно простые. НОК двух чисел a и b можно вычислить на знании НОД(a, b) по формуле: a*b=d*k, т.е. нок(а,b)= a*b/нод(a,b).

Существует рекуррентная запись запись алгоритма Евклида, которая заканчивается за определенное число шагов. Разложим большее через меньшее b< a

a=b*q₁+r₁

b=r₁*q₂+r₂

r₁=r₂*q₃+r₃

_{……………………………}

r_n_-₃=R_n_-₂*q_n-1 + r_n-1

r_n_-2=R_n_-1*q_n и r_n=0

Существует теорема что Rn-1– НОД. На основание теоремы сделаем вывод, что

a=b*q+S

НОД(a,b)= НОД(b,s)

Расширенный алгоритм Евклида (РАЕ)

(a,b)=d, d можно разложить по формуле: ax+by=d

Дополнительно вычисляются коэффициенты x,y

R₁=ax₁+by₁ R_n-1=ax_n-1+by_n-1

R2=ax₂+by₂R_n-2=ax_n-2+by_n-2

_{…………………………………}X_n_-1=x; y_n_-1=y

Общий вид формул для вычисления x_j и y_j:

x_j=x_j-2-q_jx_j-1; y_j=y_j-2-q_jy_j-1

Решето Эратосфена

Цель алгоритма - определить все положительные простые числа, меньшие некоторой верхней границы п, где n N. Вначале выписываются все нечетные целые между 3 и n.

Далее ряд просеивается. Первое число в нем 3. Вычеркиваются из списка все числа, кратные трем и большие трех. Теперь выбирается наименьшее число из списка, превосходящее 3, которое еще не было вычеркнуто - число 5. Вычеркивается каждое число из списка, кратное пяти и большее пяти. Эта процедура продолжается до тех пор, пока не будут рассмотрены все числа до п.

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

Можно отметить следующие замечания к алгоритму "решето Эратосфена".

1. Некоторые числа вычеркиваются больше, чем один раз.

2. Хотя процесс вычеркивания повторяется вплоть до граничного числа п, но все составные числа вычеркиваются раньше достижения этой границы.

Вычисление НОД и НОК на основе канонического разложения числа.

Любое составное число m можно однозначно представить в виде произведения простых сомножителей p, m = p₁*p₂*.....*p_k, где m – составное число, p – простое. Составное число может раскладываться на простые, при этом могут быть две формы:

1)когда все сомножители разные 2) когда есть кратные сомножители

Пример: 720 = 2⁴*3²*5 - такая форма носит название – каноническое разложение на простые сомножители. M=p₁^α1* p₂^α2* p_k^αk. Это позволяет при большем числе кратных

сомножителей достаточно компактно записать разложение.

Найдем НОД по след формуле: НОД=П_ip_i^min⁽^ai^*^bi⁾, где П_i-произведение.

Min(a_i*b_i) - из каждой пары сомножителей выбирается сомножитель с минимальным показателем.

Пример 90= 2*3²*5, 720= 2⁴*3²*5.

Берем минимальные показатели: НОД=П_ip_i^min⁽^ai^*^bi⁾=2*3²*5=90 - т.е. число 90 является НОД(d) чисел 90 и 720. Аналогично НОК :

НОK= П_ip_i^max⁽^ai^*^bi⁾= 2⁴*3²*5=720 - т.е. число 720 является НОК(k) чисел 90 и 720.

Тестирование чисел Мерена

Числами Мерсенна называются числа вида М(p) = 2 ^p - 1, pÎN.

Задача для чисел Мерсенна - поиск в ряду этих чисел простых.

Мерсенн рассматривал значения функции 2^p - 1 только при простых p .

Действительно, если p - составное, то такое же и М(p). Предположим, что

p = r * s , 1 < r и s < p , тогда

М(p)=2^p-1=2^rs -1=(2^r -l)(2^r^(s-1) +2^r^(s-2) +...+2^r +1).

Следовательно, если r делит p, то и М(r) делит М(p).

В то же время, если p - простое, то М(p) не обязательно является простым.

Например, для простого числа p = 11 число Мерсенна М(p)=211−1=2047=23×89 получается составным.

При доказательстве простоты чисел Мерсена Ферма использовал метод разложения на множители. Более эффективен тест Люка-Лемера.

Тест Люка - Лемера

Тест создает последовательность натуральных чисел: S₀, S₁, S₂, ..., S_p-2, определяемую рекуррентной формулой S_k+1 = S_k² - 2, где S₀ = 4. Пусть р – простое число. Число Мерсена является простым тогда и только тогда, когда S_p-2 mod M(p) ≡ 0, т.е. остаток равен 0.

Поясним, каким образом задается ряд S_k. Члены последовательности можно записать в виде сумм степеней некоторых иррациональных чисел. Пусть = 2 +√3 и =2 +√3 . Докажем индукцией по n, что ^{2^n} + ^{2^n}=S_n.

Очевидно, + =S₀. Предположим, что ^{2^(n-1)} + ^{2^(n-1)}=S_n-1.

Возводя в квадрат обе части равенства, получаем ^{2^n} +2( )^{2^(n-1)}+ ^{2^} ⁿ =S² _n _-1. Поскольку =1,то следует соотношение ^{2^n} + ^{2^n}=S² _n _-1 -2, что, по определению, дает S_n.

Описание алгоритма.

1. Ввод p. Если p < 3, то выход (не удовлетворяет условиям алгоритма).

2.Вычисление M(p) = 2^p-1

3. Установить S = 4.

4. Для "i = 1…p-2 вычислить S = (S² mod M(p)) - 2

5. Если S mod (M(p)-1)º0, то M(p) является простым, иначе составным.

4. Функция Эйлера

Эйлер установил такую закономерность, что существует определенная формула, по которой можно вычислить число взаимно простых чисел. Эта формула определяется на основе разложения числа m=p₁^a¹*…*p_k^ak. Функция Эйлера устанавливает число взаимно простых чисел с заданным числом m.

Формулы для вычисления:

1) j(m)=m(1-1/p₁)(1-1/p₂)(1-1/p_i)

2) j(m)=(p₁^a¹-p₁^a^1-1)(p₂^a²-p₂^a^2-1)…(p_k^a^k-p_k^a^k-1)

где p_i-числа, на которые мы делим, a_i-их степени

Классическое приложение этой функции такое: Заданно некоторое натуральное число a и заданно некоторое число m, пусть m-составное, натуральное, положительное. Если эти два числа взаимно просты, тогда для этой пары чисел справедлива следующая теорема (теорема Эйлера):

a^j⁽^m⁾mod m = 1.

Берем число a,возводим в j(m) , берем модуль от a^j⁽^m⁾: т.е. остаток будет равен всегда единице.

Частный случай: m- простое(p), то: a^p^-1modp 1

Мультипликативная функция

Имеем два натуральных числа a и b, если они взаимно просты, то мультипликативная функция устанавливает число взаимно простых чисел, для произведение двух взаимно простых чисел по формуле:j(a*b)=j(a)*j (b) т.е. при больших a и b, эта формула позволяет уменьшить выч. сложность. Но если числа a и b не взаимно простые, то вычисления проводятся по обычной формуле.

Функция Мебиуса

Функция Мебиуса μ(n) служит характеристикой канонического разложения. Характеристики канонического разложения: кратность, четность, нечетность. μ(n) определена для всех положительных натуральных чисел n и принимает значения {-1, 0, 1} в зависимости от характера разложения числа n на простые сомножители:

· μ(n) = 1 если n не делится на квадрат простого числа и разложение n на простые множители состоит из чётного числа сомножителей;

· μ(n) = −1 если n не делится на квадрат простого числа и разложение n на простые множители состоит из нечётного числа сомножителей;

· μ(n) = 0 если n делится на квадрат простого числа.

Принято считать что μ(1) = 1.

На основе Функции Мебиуса можно найти Функцию Эйлера: j(m)=(å(m/d_i)μ(d))

Задано число m. 1) находим все делители d_i/m 2) находим числа m/d_i

3) μ(d_i) - находим функцию Мебиуса для каждого значения

делителя. В конце мы и получаем значение функции Эйлера.

Числовая функция [ a ]

Это функция устанавливающая целую часть от нек. рационального числа. Может быть как положительное, так и отрицательное число. [3,5]=3. Пример приложения этой функции в криптографии: разложение факториалов на простые сомножители чисел.

Пример: 1000!= p₁*p₂*...*p_l. Мы не раскладывая факториал, можем проверить все сомножители. Допустим сколько раз сомножитель 3 входит в 1000! 1000/3+1000/9=498 раз

Пример.

Пусть дано:

a=2,

х=5432675,

m=p=13 Теорема Эйлера (a^j^(m))mod m 1.

m – целое, а – взаимное простое с m.

Теорема Эйлера утверждает, что остаток будет равен 1

Если m простое, то (р)=p-1

a^p-1= 1modp

1) Находим функцию Эйлера для числа m=p=13, т.е. исходя из малой т.Ферма j(р)=p-1=12.

2) Число х представляем черех функцию Эйлера

х=5432675=q j(р)+r = 452722*12+11=4352722+11

1) Вычисляем

(2^{4352722*12+11})mod13=(2^4352722*12*2¹¹)mod13=[(2^4352722*12mod13)(2¹¹mod13)]mod13=

=(2^{4352722*12+11})mod13=7

Здесь сомножитель (2^435272*12)mod13 по теореме Эйлера равен 1.

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

На вход: числа 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

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

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

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

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

невычетов

Шаги алгоритма.

1. Если НОД(a, m) ≠1, то обратный элемент не существует.

2. Для любого t Î[0, ¥) вычисляются следующие действия.

а. Если значение выражения не является натуральным числом,

то переход к пункту 2.

б. Иначе это выражение задает обратный элемент: a^-1=( )mod m, выход.

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

условие существования обратного элемента.

II Можно вычислить для элемента a обратный элемент a^-1 и при знании функции Эйлера φ(m), где (a,m) = 1. Так как a^j^(m)modm 1 и (a·a⁻¹)modm≡1, то a^j^(m)modm=(a*a^-1)modm=>
a⁽^j^(m)-1)modm=a^-1modm => a^-1=a⁽^j^(m)-1)modm. Данную формулу можно вычислить с меньшими вычислительными затратами, используя схему Горнера для быстрого возведения числа a в степень (φ(m) - 1).

Первообразные корни

Число a, где (a, m) = 1, называется первообразным корнем по модулю m, если показатель a по этому модулю равен φ(m), то есть P(a) = φ(m).

Таким образом, первообразным элементом является число a, для которого выполняется сравнение: a^φ⁽^m⁾ =1 mod m, где φ(m) = P_m(a).

Существует следующий переборный вариант поиска первообразных элементов. В качестве кандидатов в первообразные элементы

рассматриваются все числа a = , которые удовлетворяют следующим условиям:

1) взаимной простоты чисел a и m: (a, m) = 1;

2) a^φ⁽^m⁾ 1 mod m или a^φ⁽^m⁾ mod m=1;

3) для "r = , являющегося делителем числа φ(m): a^r 1 mod m.

Число 1 в качестве варианта первообразного элемента не рассматривается, так как при " 1ⁿи " модуле φ(m) будет выполняться условие 1^φ⁽^m⁾=1 mod m.

Теорема 1. Число a, a= , будет первообразным элементом по простому модулю p, если выполняется условие: A⁽^p^-1/^pi⁾≠1 mod p для "i= , где число p–1 представлено в виде канонического разложения p–1=Çp_i^αi, на k простых сомножителей, α_i - натуральные числа.

Теорема 2. Число первообразных корней, принадлежащих диапазону

a= , равно:

- φ(p-1), если модуль p - простое число;

- φ(φ(m)), если модуль m - составное число.

Теорема 3 . Если a - первообразный элемент по (простому и составному) модулю m, то остальные первообразные элементы могут быть найдены как числа a^k: (a^k mod m, φ(m)) = 1 и k≥2, k-целое.

Теорема 4 . Пусть p - простое число. Если a является первообразным элементом по составному модулю p^α (α ≥ 1), то число a будет первообразным элементом и по модулю p.

Теорема 5 . Пусть p - простое число. Если a - первообразный элемент по модулю p, то первообразным элементом также являются:

- число a по составному модулю p^k, если выполняются условия
k≥2 и a⁽^p^-1)^p^{^(}^k^-2) ≠1 mod p^k;

-одно из amodp² или (a+p)mod p².

Теорема 6 . Пусть p - простое число. Если a - первообразный элемент по модулю p², то a является первообразным элементом по модулю p^k, k ≥ 2.

Теорема 7 . Любой нечетный первообразный элемент по модулю p^k является первообразным корнем и по модулю 2p^k, где p - простое число и k ≥ 1-целое.

Теорема 8 . Первообразные элементы по составному модулю m

существуют тогда и только тогда, когда:

1) m = p^k,

2) m = 2p^k, где p - простое число и k ≥ 1 - целое.

Теорема 9 . Первообразный элемент существует тогда и только тогда, когда модуль mÎ{2, 4, p^k, 2p^k}, где p - простое число и k ≥ 1 - целое.

14. Вычисление в поле GFC(2^n) обратных элементов

Обратный элемент в конечном поле GF(2ⁿ) используется как вспомогательный элемент при делении некоторого многочлена A(x) на многочлен B(x) в поле GF(2ⁿ) по полиному-модулю P(x). Результирующий полином C(x) будет получен как C(x)=A(x)*B^-1(x) mod P(x), где B^-1(x) - обратный элемент для многочлена A(x).

Одним из способов получения обратного элемента в поле полиномов является использование функции Эйлера. Понятие функции Эйлера по аналогии переносится из теории чисел в поле GF(2ⁿ)

Пусть задан неприводимый модуль-полином P(x). Функция Эйлера в поле GF(2ⁿ) будет задавать число взаимно простых с P(x) полиномов. Так как P(x) является неприводимым, то функция Эйлера φ(P(x)) = 2ⁿ-1. Тогда, применяя функцию Эйлера, обратный элемент будет вычисляться как

A^-1(x) = A^j^(P(x))-1(x) mod P(x) = A⁽^{2^n-2)}(x) mod P(x).

Обратный элемент в поле GF(qⁿ), где q - простое число, также можно вычислить и по модификации алгоритма Евклида, находящей переменные выражения α·a+β·b=НОД(a, b), только вместо чисел в формулу будут подставляться полиномы. Для нахождения обратного элемента g⁻¹(x) для полинома g(x) по полиному-модулю f(x) в качестве решаемого уравнения используется g⁻¹(x)g(x)+t(x)f(x) = 1, где g⁻¹(x), g(x), t(x), f(x)ÎGF(qⁿ).

М-последовательности

Последовательность U_p над полем GF(2), получаемая по соотношению X(t+1)=A_T*X(t) и имеющая максимальный период 2ⁿ -1, называется максимальной линейной рекуррентной последовательностью или
M - последовательностью.

При a₀=1 состояние регистра X(0) не является запрещенным. В этом случае начальное состояние регистра, состоящее из всех единиц, является запрещенным, поскольку порождает последовательность U, состоящую также из одних единиц. При других начальных состояниях последовательность U над полем GF(2) также имеет максимальный период 2ⁿ -1, но является инверсной по сравнению с M - последовательностью. Период ЛРП определяется характеристическим многочленом над полем GF(2) матрицы A_T:

f(x)=xⁿ +a₁x^(n-¹⁾ +a₂x^(n-²⁾ +...+a_n_-1x+a_n, (1)

которым является определитель матрицы ( A_T + XE ), где Е–единичная матрица размера n. Коэффициенты a_i многочлена f (x) определяют первую строку матрицы A. Если характеристический многочлен f (x) над полем GF(2) является неприводимым и примитивным, то период ЛРП равен 2ⁿ -1.

Наименьший из всех возможных периодов ЛРП называется минимальным ее периодом. Если характеристический многочлен f (x) является только неприводимым, то максимальный период ЛРП, в этом случае,

L=ord f<2ⁿ-1.

Начальной информацией для построения ГПСЧ, порождающего ЛПР с заданным периодом L, является характерист. многочлен (1) с ord f =L.

М-последовательности имеют статистическую равномерность на периоде L= 2ⁿ-1, то есть число единиц N1 и нулей N2 определяется величинами N1 = 2⁽ⁿ^-1) и N2 = 2⁽ⁿ^-1) -1.

М-1 последовательности

1. Пусть характеристический многочлен f (x) для схемы ГПСП представлен в виде произведения

f (x)= P(x) * q(x)

примитивного многочлена P(x) и линейного многочлена g(x)=x+1, тогда максимальный период многочлена f(x) степени n равен L = 2ⁿ - 2. Последовательности такого типа (с периодом 2ⁿ-2 ) принято называть (M-1) последоват. Минимальный период последовательности, порождаемой ГПСП с рассмотренным характеристическим многочленом, равен

2. В (M-1) последовательности отсутствуют два (запрещенных)
n- разрядных двоичных набора, состоящих из чередующихся символов 0 и 1.

3. Число единичных символов в (M 1) последовательности совпадает с числом нулевых символов в периоде L = 2ⁿ - 2 .