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

Алгоритм нахождения числа по модулю

Читайте также:
  1. Lst.push_back(i); // Заполняем список числами
  2. Алгоритм 1. Зупинка артеріальної кровотечі за допомогою закрутки
  3. Алгоритм 3.1. Транспортна іммобілізація
  4. Алгоритм 4.3. Діагностичний і лікувальний (перша медична допомога) пошук при струсі мозку.
  5. Алгоритм L.
  6. Алгоритм RLE
  7. Алгоритм автоматического формирования парных симметричных ключей шифрования-дешифрования открытых сообщений на рабочих станциях абонентов корпоративной системы.
  8. Алгоритм анализа реальности достижения поставленных профессиональных целей.
  9. Алгоритм виконання роботи
  10. АЛГОРИТМ ВИЯВЛЕННЯ ТА ДІАГНОСТИКИ ТУБЕРКУЛЬОЗУ
  11. Алгоритм выполнения работы
  12. Алгоритм геометрического расчета передачи

Операцию нахождения числа по модулю (операцию нахождения вычета числа «а» по модулю «Р») называют приведением числа «а» по модулю «Р»

y = a mod P

Эта запись в модулярной алгебре читается как «число y сравнимо с числом а по модулю Р». Это соотношение справедливо для целых значений чисел: y, a, P и Р ≠ 0. Число «а» определяют как «вычет» числа «y» по модулю «Р». Операцию нахождения вычета числа «а» по модулю «Р» можно интерпретировать численным примером следующим образом. Найти вычет выражения y = 23 mod 17 = 6 mod 17, т.е. число 23 делится на 17, находится остаток, который и будет являться вычетом числа 23 по модулю 17. Набор целых чисел от 0 до Р-1 называется полным набором вычетов по модулю Р. Для последующих вычислений необходимо определять вычеты и от отрицательных чисел, например:

-23 mod 7 = -16 mod 7 = -9 mod 7 = -2 mod 7 = 5 mod 7 и т.д.

Модулярная алгебра полностью отвечает требованиям коммутативности, ассоциативности и дистрибутивности:

(а + b) mod P = [ a (mod P) + b (mod P)] mod P

(а - b) mod P = [ a (mod P) - b (mod P)] mod P

(а * b) mod P = [ a (mod P) * b (mod P)] mod P

[а * (b + c)] mod P = {[ a * b (mod P)] + [a * c (mod P)]} mod P

Вычисление обратных величин в модулярной алгебре.

В теории криптографических преобразований достаточно часто приходится сталкиваться с трудоемкой задачей вычисления обратных величин по модулю. Во многих криптографических задачах для заданных чисел «а» и «Р» требуется нахождение числа «d» меньшего «Р» (d < P), чтобы выполнялось единичное сравнение a * d mod P ≡ 1.

Необходимо отметить, что такое число «d» существует, если числа «а» и «Р» взаимно простые, при этом число «d» называют инверсией числа «а» по модулю «Р» и обозначают как: а-1 mod P. Например, требуется определить инверсию 6-1 mod 17; необходимо найти такое число, которое при умножении на число 6 и делении этого произведения на число 17 в остатке образует число 1. В рассматриваемом примере таким числом будет являться число 3, т.к. 6 * 3 mod 17 ≡ 1, следовательно, число 3 является инверсией числа 6 по модулю 17.

Для вычисления обратных величин при условии, что если Р - простое число, что практически справедливо для всех криптографических задач асимметричной криптографии, можно воспользоваться малой теоремой Ферма.

Малая теорема Ферма интерпретируется следующим образом: если «Р» - простое число, «а» - целое число, то инверсию числа «а» по модулю «Р» можно определить как:

а-1 (mod Р) = аφ(P) – 1 mod P

где: φ (Р) – функция Эйлера;

для простых чисел φ (Р) = Р – 1.

Функция Эйлера указывает сколько во множестве чисел от 0 до Р, есть чисел взаимно простых с Р.

Например, если Р = 17, то φ (Р) = Р-1 = 17-1 = 16. Требуется вычислить инверсию числа 2 по модулю 17, т.е. вычислить 2-1 mod 17.

2-1mod 17 = 2φ(P) – 1mod Р = 215mod 17 = 32768 mod 17 = 9 mod 17 → 9.

Следовательно, число 9 является инверсией числа 2 по модулю 17, т.к. 2 * 9 mod 17 = 18 mod 17 = 1 mod 17 → 1.


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.003 сек.)