рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Возведение натуральных чисел по модулю в большие степени по схеме Горнера

Возведение натуральных чисел по модулю в большие степени по схеме Горнера - Лекция, раздел Математика, Материалы лекций Математические основы криптологии Пусть Задано Выражение Вида   Y = A X Mo...

Пусть задано выражение вида

 

y = a x mod m , (1.1)

 

где a ÎN - основание степени,

 

x ÎN - степень выражения,

 

m ÎN - числовой модуль, число, нормирующее выражение в диапазоне

 

[0..m−1],


 

mod - знак операции взятия остатка от деления делимого ax на делитель

 

m,

 

y ÎN - результат вычисленного выражения, лежащий в диапазоне

 

[0..m−1],

 

N - множество натуральных чисел.

 

Пусть все операции производятся над натуральными числами, целочисленно, без округлений.

При непосредственном вычислении значение выражения ax может

 

выйти за размеры машинного слова (значения которого могут лежать в диапазоне [0..232−1]) уже при малых значениях a и x, например при a = 3 и x = 21. Поэтому необходимы другие механизмы получения результата, полагая, что будет использоваться модульная арифметика.

Схема Горнера обладает следующими особенностями:

 

- выражение (1.1) вычисляется при ограничениях на диапазон натуральных чисел для ПЭВМ (промежуточные результаты берутся по модулю);

- каждая операция разбивается на подмножество эквивалентных;

 

- используется, в отличие от последовательного возведения числа a в степень x, меньше операций умножения из-за разложения степени выражения (1.1) на сумму степеней числа 2.

Десятичное число x можно представить в виде суммы единиц, десятков, сотен, тысяч и т.д., то есть в виде десятичного полинома:

x= x0?100 + x1?101 + x2?102 + . . .+ xk-1?10k-1,

 


где xi= [0..9] - является десятичным числом,


i = 0, k - 1 , k ÎN - число, такое,


 

что x ≤ 10k. Например, десятичное число 50921 можно записать в виде полинома:

5092110 = 5? 104 + 0? 103 + 9? 102 + 2? 101 + 1? 100 (слева направо: 5 в разряде

 

десятков тысяч, 0 - в разряде тысяч, 9 - в разряде сотен, 2 - в разряде десятков, а 1 - в разряде единиц).

Аналогично, можно представить число x в виде двоичного числа


 

(двоичного полинома):

 


 

x= x0? 20 + x1? 21 + x2? 22 + . . .+ xk-1? 2k-1 или


k -1

x

i=0


 

i
x 2i , (1.2)


 


где xi = {0, 1} - двоичное число,


i = 0, k - 1 , k ÎN - число двоичных разрядов,


 

необходимое для представления числа x (x ≤ 2k). Например, двоичное число

 

10111 можно записать в виде полинома:

 

101112 = 1*104 + 0*103 + 1*102 + 1*101 + 1*100 (слева направо: 1 в разряде десятков тысяч, 0 - в разряде тысяч, 1 - в разряде сотен, 1 - в разряде десятков, а 1 - в разряде единиц).

Тогда из формул (1.1) и (1.2), при использовании модульной

 

арифметики, следует, что:

 


k -1
i
y =a x mod m =aåi =0 X i 2


 

mod m =


 

ç
=éæa20


 

X 0 mod m ö÷æça21


 

X1 mod m ÷öçæa2


 

X 2 mod m ö÷...çæa2


 

k -1


 

X k -1 mod m ÷öùmod m.


(1.3)


êëè


øè øè ø è


øúû


 

Здесь xi задают i-ые двоичные разряды степени x.

 

В схеме Горнера выражение y вычисляется с меньших номеров

 

двоичных разрядов в сторону возрастания степени i. Член r = çæ a2i X i mod m ÷ö

è ø

 

( i = 0, k - 1 ) из (1.3) при xi = 1 не требуется вычислять заново, с самого

 

начала, так как его можно получить следующим образом:

 


 

i
çæ a2


 

mod m ÷ö =çæ a


 

2i -1


 

2 mod m ÷ö


 

mod m , по значению предыдущего шага.


è ø è ø

 

 

Алгоритм работы схемы Горнера.

 

Опишем алгоритм схемы Горнера по шагам. На вход: числа a, x, m ÎN.

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

 

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 ÎN такое, что x ≤ 2k, то есть k ≥ log2 x.

5.а) Пусть r = 20 и k = 0; пока k < 32 (максимальное число разрядов

 

в машинном слове) и r x, то возводим 2 в степень k: r = 2k и увеличиваем k

 

на единицу.

 

5.б) Если k = 0 или k > 32, то задача не решается в установленных условиях, выход (число 32 обозначает максимальную степень двойки для машинного слова, то есть число 232 задает максимальное число различных значений, которые можно сохранить в машинном слове). Иначе пункт 6.

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

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

 

7.а) r = [(r mod m)·(r mod m)] mod m = r2 mod m;

 

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

 

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

 

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

 

Пример 1.13. Необходимо число a = 2 возвести в степень x = 25 и привести результат по модулю m = 29.

Тогда k, удовлетворяющее неравенству k > log2 x, равно 5.

 

Число x представимо в двоичной форме как x = 2510 = 11 0012. Это число является нечетным.

На шаге 6 получаем, что r = a = y = 2.


 

Далее представим шаг в виде трассировочной табл. 1.10:

 

Таблица 1.10. Трассировочная таблица

 

 

Шаги в цикле   Условие i < k   Значение xi   r   y
до цикла -
шаг i=1 да
шаг i=2 да
шаг i=3 да 256 mod 29=24 48 mod 29=19
шаг i=4 да 576 mod 29=25 475 mod 29=11
шаг i=5 нет - Выход из цикла  

 

Ответ: y = ax mod m = 11.

 

 

Дополнительные примеры для решения:

 


1) a = 7, x = 5, m = 31. Найти

 

2) a = 3, x = 7, m = 29. Найти


y = a x mod m

 

y =ax mod m


 


3) a = 5, x = 11, m = 14. Найти


y =ax mod m


 

 

Существует другой вариант схемы Горнера возведения целых чисел в

 

большие степени. Степень x также представляется в двоичном виде:

 


i
k -1

x xi 2


 

, x Î{0, 1}. В отличие от первого варианта схемы Горнера


i=0

 

последовательно рассматриваются двоичные разряды числа x в направлении понижения номера разряда. Тогда возведение в степень можно выполнить по

следующей схеме:

 

k -1 i

y =a x mod m =aåi =0 xi 2 mod m =

=[(...((((aX k -1)2 mod m ×aX k -2 )2 mod m ×aX k -3 )2 ... ×aX1)2 mod m ×aX 0 ]mod m.

Пример 1.14. Вычислим y = ax mod m при a = 9, x = 5, m = 31. Число x в двоичном виде можно представить как x = 510 = 1012. Тогда y = ax mod m =

= ((( a X 2 )2 mod m · a X1 )2 mod m · a X 0 ) mod m =

 

= (((a1)2 mod m ·a0)2mod m ·a1) mod m =

 

= ((a2 mod m)2 mod m · a) mod m = (92 mod 31)2 mod 31 · 9) mod 31 =

 

= (192 mod 31 · 9) mod 31 = 180 mod 31 = 25.

 

Ответ: y = ax mod m = 25.


 

 

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

 

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

 

8. Если xi = 1 (i-ый разряд числа x равен 1), то y = (y2 · r) mod m,

иначе y = y2 mod m.

 

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

 

10. Если x0 = 1 (учесть последний бит числа x), то y = (y · a) mod m.

 

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

 

Пример 1.15. Вычислим y = ax mod m при a = 5, x = 13, m = 11. Число x в двоичном виде можно представить как x = 1310 = 11012.

Пусть y = 1. Представим вычисления шагов 8-9 в виде трассировочной

 

табл. 1.11.

 

Таблица 1.11. Трассировочная таблица

 

Шаг, i xi y
x3 = 1 (1 · 11) mod 14 = 11
x2 = 1 (112 · 11) mod 14 = (9 · 11) mod 14 = 1
x1 = 0 1 mod 14 = 1

 

 


На шаге 10 будет учтен последний бит числа x: y = (y ·

 

= (1 · 5) mod 14 = 5.

 

Ответ: y = ax mod m = 5.


a x0 ) mod m =


 

 

Вычислите по второму варианту дополнительные примеры, представленные выше.

Примечания.

 

Для программной реализации алгоритма схемы Горнера требуется осуществлять перевод степени x из десятичной формы представления в двоичную. При вводе числа x и его сохранении в машинной переменной оно


 

уже будет представлено в двоичной форме. Поэтому можно не переводить числа, а для работы с отдельными разрядами (битами) двоичного числа использовать программные методики, описанные в приложении.

 

Вопросы для самопроверки.

 

1. Для чего нужна схема Горнера?

 

2. Как работает схема Горнера?

 

3. Какими особенностями обладает схема Горнера?

 

4. Как можно представить число в виде степеней основания счисления?

 

5. Что дает разложение степени в схеме Горнера в двоичное представление?

 

6. Какие ограничения накладываются на входные значения схемы Горнера?

 

7. Как можно выполнить перевод числа с длиной в машинное слово из десятичной в двоичную систему счисления?

8. Как можно выполнить возведение двойки в степень с помощью команд ЭВМ?

 

9. Какие математические операции используются в схеме Горнера?

 

10. Поясните второй вариант метода возведения числа в степень.

 

– Конец работы –

Эта тема принадлежит разделу:

Материалы лекций Математические основы криптологии

В М Захаров.. Материалы лекций.. Математические основы криптологии..

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Возведение натуральных чисел по модулю в большие степени по схеме Горнера

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Лекция№1
    Криптология состоит из двух направлений: криптографии и криптоанализа.   Криптография – наука о способах преобразования (шифрования)

Асимметричное шифрование.
    Алгоритм RSA (Revest, Shamir, Adelman) 1978г. e, n А, М В    

Алгоритм передачи секретного ключа по открытому каналу
В середине 70-х годов произошел настоящий прорыв в современной криптографии – появление асимметричных криптосистем, которые не требовали передачи секретного ключа между сторонами. Здесь от

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

Алгоритм РАЕ Кнута
   

Свойства делимости целых чисел
  Два числа a и b называются взаимно простыми если их НОД = 1   (a1,a2,….,an)= НОД   (a1,a2) = d1   (a3,d1) = d2

Свойства делимости целых чисел
  Свойства приведены без доказательства.   1)Свойство дистрибутивности   Пусть заданны три натуральных числа a,b,

Простые числа
  1)- каноническое разложение &nb

Получение простых чисел.
  По мере того как мы будем изучать курс «Математические основы криптологии» мы будем возвращаться к этой теме. Задача получение простых чисел во многом зависит от того как с

Проверка простоты чисел Мерсенна
  Числами Мерсенна называются числа вида М(p) = 2p - 1, pÎN.   Задача для чисел Мерсенна - поиск в ряду э

Sp-2 mod M(p) ≡ 0, т.е. остаток равен 0.
  Поясним, каким образом задается ряд Sk. Члены последовательности  

Алгоритм Бухштаба
  Данный алгоритм приведен из книги Бухштаба А.А. "Теория чисел" [4]. Пусть задано натуральное нечетное число n, n ≥ 9, которое необходимо разложить на 2

Алгоритм Ферма
  Алгоритм Ферма похож на алгоритм Бухштаба и является эффективным, если у раскладываемого числа n есть делитель (который

Функция Эйлера
  Имеется целое, положительное число m. Оно может быть как составным, так и простым. Функцию Эйлера принято обозначать, практически во всех учебниках как:  

Мультипликативная функция
  Имеем два натуральных числа a и b, если они взаимно просты, то мультипликативная функция устанавливает число взаимно простых чисел, для произведение двух взаимно простых чисел по фо

Числовая функция
  Это функция устанавливающая целую часть от некоторого рационального числа [a] – обозначение   может быть как положительное, так и отрицательное число

Для возведение натуральных чисел по модулю в большие степени
    Функция Эйлера может быть использована для возведение больших чисел в большую степень по модулю.     Имеется целое число

Сравнимость по модулю. Модулярная арифметика
    Понятие «модулярная арифметика» ввел немецкий ученый Гаусс.   Модульная арифметика аналогична обычной арифметике: она коммутативна, ассоциатив

Свойства операций сравнения
    В криптографии существуют шифры и по простому модулю и по составному модулю.   Нужно знать когда применять простой модуль, а когда состав

Доказательство теоремы Эйлера
  Пусть даны m и φ(m)=k   Имеем число a, причем (a,m)=1     Берем ряд натуральных чисел: a1

Модулярная арифметика (продолжение) Квадратичные вычеты Степенные вычеты
  Продолжим исследовать вычеты. Широкое применение в криптографии нашла формула: xn ≡ a mod m, n=2 xn ≡ a mod p – квадратичный выч

ЭЛЕМЕНТЫ ТЕОРИИ КОНЕЧНОГО ПОЛЯ Простейшие алгебраические структуры
  Под алгебраической структурой будем понимать некоторое множество   S с одной или несколькими операциями на нем.   Пусть S х S обозначае

Кольца и поля
  Алгебраические структуры с двумя бинарными операциями - сложение и умножение.     Определение 1.7. Множество S называется кольцом, е

Характеристика поля
  Определение 1.12. Если в поле Fq все ненулевые элементы имеют аддитивный порядок k, то говорят, что поле Fq имеет характеристику k. Обозначение. р - простое число.

Вычисление обратных элементов
  В арифметике действительных чисел просто вычислить обратную величину a−1 для ненулевого a: a-1 = 1/a или a? a-1 = 1.

Многочлены над конечным полем
  Onределенuе 1.13. Многочленом (относительно х) над полем GF(p)   m

Для любого простого р и nÎN существует хотя бы один неприводимый над полем GF(p) многочлен степени n [9].
Любой неприводимый над полем GF(p) многочлен степени п делит     многочлен x pm - x   (также и мног

Алrебраические структуры над множеством многочленов
  Кольцо многочленов над полем GF(p)   Определение 1.17. Кольцо, образованное многочленами над полем GF(p), называется кольцом многочлен

Расширение полей
  Рассмотрим, какова связь полей GF(p) и GF( p n ).   Пусть F - поле. Подмножество К поля Р, которое само является полем относительно операций поля Р, на

Системы уравнений сравнений
  Общий вид:   x ≡ c1 mod m1   x ≡ c2 mod m2

Pound; b£ n-1
  Если для каждого простого делителя p числа n-1 справедливы следующие утверждения:     (1) bn-1≡ 1(mod n),  

Числа Кармайкла
  Может ли составное нечетное число n быть псевдопростым по всем взаимно-простым с ним основаниям b? Забегая вперед, скачем, что «да».     Заметим

Процедура получения устойчивых простых чисел
  1. Генерируются простые числа s,t   2. Получаем простое число r такое что, (r-1) делит t без остатка: r-1|t На основе этих двух операций получаем про

М-последовательности. ГПСЧ типа ЛРС1
  Опр ед ел ени е. Последовательностью над полем   GF ( p)   будем   назы

M - последовательности на основе произведения многочленов
Рассмотрим способ построения схемы линейного регистра сдвига на основе характеристического многочлена, задаваемого как произведение   многочленов, при &nbs

Произведения многочленов
  Рассмотрим следующие свойства ЛРП, порождаемой схемой ГПСП,   изображенной на рис. 2.1, при a0 =1.  

ЛЕКЦИЧ 16
  Способы представления элементов поля GF(2n)   Для представления элементов в полях Галуа вида GF(2n) существуют ра

Алгоритм получения элементов поля GF(2n) в стандартном базисе
  Для построения элементов поля GF(2n) в стандартном базисе существует следующий алгоритм, использующий сдвиговыерегистры. На входе: поле GF(2n

Заданными в стандартном базисе
   

Алгоритм асимметричного шифрования RSA
  Алгоритм RSA предложили в 1978 г. 3 автора: Райвест (Rivest), Шамир (Shamir) и Адлеман (Adleman). RSA является алгоритмом с открытым ключом, работающим в режимах шифрования данных и

Математическая модель алгоритма RIJNDAEL
  Байты можно рассматривать как элементы конечного поля GF(28) -   многочлены степени не более 7   а7х7 + а6х

Раунд преобразования алгоритма RIJNDAEL
  RIJNDAEL выполняет серию однотипных раундов преобразования шифруемого блока. Шифруемый блок и его промежуточные состояния в ходе преобразования представляются в виде квадратной матр

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги