Редукція Барретта — алгоритм обчислення лишку за модулем, запропонований Барреттом 1986 року. Наївний спосіб обчислення виразу
полягає в застосуванні ділення з остачею, яке в довгій арифметиці є складною операцією (зазвичай, зводиться до кількох операцій множення та віднімання). Алгоритм Барретта розроблено для оптимізації цієї операції за умов та сталого . У ньому ділення замінено двома множеннями, зсувом та відніманням.
Алгоритм
Попередні обчислення:
Нехай і — не степінь 2 (обчислення лишку за модулем, який дорівнює степені 2, у двійковій системі є тривіальним). Обрати таке, що (найменше таке дорівнює ). Обчислимо (це й буде наперед обчислений множник).
Обчислення залишку за модулем:
Маємо таке, що , залишок від ділення якого на потрібно знайти. Обчислюємо Якщо , тоді повернути ; інакше — повернути . Цей результат дорівнює .
Доведення правильності Оскільки не є степенем 2, то число — не ціле. Отже, Множення на Ділення на . Із того, що випливає, що Тому: . Також: і . Разом маємо: . Множимо на Множимо на . Додаємо Очевидно, що , оскільки число кратне .
У результаті ми перейшли від у діапазоні до у діапазоні без зміни конгруентності за модулем . Останній крок простий: необхідно отримати результат у діапазоні .
Застосування
Редукція Барретта застосовується для обчислення залишку за модулем в операціях модульного множення й модульної експоненти, які широко застосовуються в системах криптографічного захисту інформації.
Примітки