АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Алгоритм операции возведения числа в степень по модулю

Читайте также:
  1. C. Число элементов в операции
  2. D. опасная степень загрязнения
  3. II. Операции за февраль руб.
  4. II.Хозяйственные операции за июнь 200_ г. руб.
  5. Lst.push_back(i); // Заполняем список числами
  6. V. Операции в пользу мира в информационный век
  7. Алгоритм 1. Зупинка артеріальної кровотечі за допомогою закрутки
  8. Алгоритм 3.1. Транспортна іммобілізація
  9. Алгоритм 4.3. Діагностичний і лікувальний (перша медична допомога) пошук при струсі мозку.
  10. Алгоритм L.
  11. Алгоритм RLE
  12. Алгоритм автоматического формирования парных симметричных ключей шифрования-дешифрования открытых сообщений на рабочих станциях абонентов корпоративной системы.

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

Например, требуется вычислить y = ax mod P при числовом отображении y = 6181 mod 77.

Во всех вычислениях степенной функции по модулю на первом шаге вводится параметр t = ë log 2 X û – целая часть log 2 X. Символы ë…û означают, выбор целой части включенного выражения.

Если y = ax mod P, где: а = 6; х = 181; Р = 77, то y = 6181 mod 77.

1. На первом шаге алгоритма определяется значение целой части логарифма по модулю 2 показателя степени х (в примере х = 181) t = ë log 2 181û;

2t ≤ х = 2t ≤ 181, откуда t = 7, следовательно, 27 ≤ 181; 128 ≤ 181.

2. На втором шаге алгоритма вычисляются числа ряда Si = an, где n = 2t. В рассматриваемом числовом примере t = 7, следовательно, последний член ряда определится как S7 = a128. Таким образом, искомый числовой ряд может быть представлен следующим образом:

Si → а а2 а4 а8 а16 а32 а64 а128, т.к. а = 6; Р = 77, то степенные значения ряда вычисляются по модулю Р = 77

а а2 а4 а8 а16 а32 а64 а128

6 36 64 15 71 36 64 15 при а =6 по mod Р (Р = 77)

1. После вычисления значений степенного ряда необходимо показатель степени выражения y = ax mod P отобразить в двоичной форме

Х = 181 → (1 0 1 1 0 1 0 1)2; 1 0 1 1 0 1 0 1 → 27+25+24+22+20 = 128+32+16+4+1 = 181.

4. Составляется следующая таблица

а128 а64 а32 а16 а8 а4 а2 а0 Искомый ряд
                Двоичное представление показателя степени «Х»
                Численные значения ряда Si

В соответствии со значением отображения показателя степени «х» в двоичной форме вычисляется произведение:

П = (а128 * а32 * а16 * а4 * а0) mod P = (15 * 36 * 71 * 64 * 6) mod 77 =

= (14722560) mod 77 = 6 mod 77 ≡ 6.

Следовательно, 6181mod 77 = 6 mod 77 ≡ 6.

На рис.4 представлен фрагмент вычисления степенной функции по модули в рамках разработанной автором автоматизированной обучающей системы.

 

Рис.4. Пример решения задачи возведения числа по модулю.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.002 сек.)