Редукція Барретта

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Редукція Барретта — алгоритм обчислення лишку за модулем, запропонований Барреттом 1986 року[1].
Наївний спосіб обчислення виразу полягає в застосуванні ділення з остачею, яке в довгій арифметиці є складною операцією (зазвичай, зводиться до кількох операцій множення та віднімання). Алгоритм Барретта розроблено для оптимізації цієї операції за умов та сталого . У ньому ділення замінено двома множеннями, зсувом та відніманням.

Алгоритм

[ред. | ред. код]

Попередні обчислення:

  1. Нехай і — не степінь 2 (обчислення лишку за модулем, який дорівнює степені 2, у двійковій системі є тривіальним).
  2. Обрати таке, що (найменше таке дорівнює ).
  3. Обчислимо (це й буде наперед обчислений множник).

Обчислення залишку за модулем:

  1. Маємо таке, що , залишок від ділення якого на потрібно знайти.
  2. Обчислюємо
  3. Якщо , тоді повернути ; інакше — повернути . Цей результат дорівнює .

Доведення правильності

[ред. | ред. код]
  1. Оскільки не є степенем 2, то число — не ціле. Отже,
  2. Множення на
  3. Ділення на .
  4. Із того, що випливає, що Тому: .
  5. Також: і . Разом маємо: .
  6. Множимо на
  7. Множимо на .
  8. Додаємо
  9. Очевидно, що , оскільки число кратне .

У результаті ми перейшли від у діапазоні до у діапазоні без зміни конгруентності за модулем .
Останній крок простий: необхідно отримати результат у діапазоні .

Застосування

[ред. | ред. код]

Редукція Барретта застосовується для обчислення залишку за модулем в операціях модульного множення й модульної експоненти, які широко застосовуються в системах криптографічного захисту інформації[2].

Примітки

[ред. | ред. код]
  1. Barrett, P. (2006). Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor. Advances in Cryptology — CRYPTO' 86. Lecture Notes in Computer Science. Т. 263. с. 311—323. doi:10.1007/3-540-47721-7_24. ISBN 978-3-540-18047-0.
  2. Кабір Лабіб Ахмед (11.06.2022). Метод прискореного модулярного множення для систем криптографічного захисту даних (PDF). Дипломний проєкт. Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського».