Barrett Reduction

In modular arithmetic, Barrett reduction is a reduction algorithm introduced in 1986 by P.D. Barrett. A naive way of computing

:$c = a \,\bmod\, n \,$

would be to use a fast division algorithm. Barrett reduction is an algorithm designed to optimize this operation assuming $n$ is constant, and a, replacing divisions by multiplications.

General idea

Let $s=1/n$ be the inverse of $n$ as a floating point number. Then

:$a \,\bmod\, n = a-\lfloor a s\rfloor n$

where $\lfloor x \rfloor$ denotes the floor function. The result is exact, as long as $s$ is computed with sufficient accuracy.

Single-word Barrett reduction

Barrett initially considered an integer version of the above algorithm when the values fit into machine words.

When calculating $a \,\bmod\, n$ using the method above, but with integers, the obvious analogue would be to use division by $n$:

func reduce(a uint) uint

However, division can be expensive and, in cryptographic settings, may not be a constant-time instruction on some CPUs. Thus Barrett reduction approximates $1/n$ with a value $m/2^k$ because division by $2^k$ is just a right-shift and so it is cheap.

In order to calculate the best value for $m$ given $2^k$ consider:

:$\frac = \frac \;\Longleftrightarrow\; m = \frac$

In order for $m$ to be an integer, we need to round $/$ somehow. Rounding to the nearest integer will give the best approximation but can result in $m/2^k$ being larger than $1/n$, which can cause underflows. Thus $m = \lfloor / \rfloor$ is generally used.

Thus we can approximate the function above with:

func reduce(a uint) uint

However, since $m/2^k \le 1/n$, the value of q in that function can end up being one too small, and thus a is only guaranteed to be within
func_reduce(a_uint)_uint_

Since_$m/2^k$_is_only_an_approximation,_the_valid_range_of_$a$_needs_to_be_considered._The_error_of_the_approximation_of_$1/n$_is:

:$e_=_\frac_-_\frac$

Thus_the_error_in_the_value_of_q_is_$ae$._As_long_as_$ae_<_1$_then_the_reduction_is_valid_thus_$a_<_1/e$._The_reduction_function_might_not_immediately_give_the_wrong_answer_when_$a_\ge_1/e$_but_the_bounds_on_$a$_must_be_respected_to_ensure_the_correct_answer_in_the_general_case.

By_choosing_larger_values_of_$k$,_the_range_of_values_of_$a$_for_which_the_reduction_is_valid_can_be_increased,_but_larger_values_of_$k$_may_cause_overflow_problems_elsewhere.

__Example_

Consider_the_case_of_$n_=_101$_when_operating_with_16-bit_integers.

The_smallest_value_of_$k$_that_makes_sense_is_$k_=_7$_because_if_$2^k_<_n$_then_the_reduction_will_only_be_valid_for_values_that_are_already_minimal!_For_a_value_of_seven,_$m_=_\lfloor_2^k_/_n_\rfloor_=_\lfloor_128_/_101_\rfloor_=_1$._For_a_value_of_eight_$m_=_\lfloor_256_/_101_\rfloor_=_2$._Thus_$k_=_8$_provides_no_advantage_because_the_approximation_of_$1/101$_in_that_case_($2/256$)_is_exactly_the_same_as_$1/128$._For_$k_=_9$,_we_get_$m_=_\lfloor_512_/_101_\rfloor_=_5$,_which_is_a_better_approximation.

Now_we_consider_the_valid_input_ranges_for_$k_=_7$_and_$k_=_9$._In_the_first_case,_$e_=_1/n_-_m/2^k_=_1/101_-_1/128_=_27/12928$_so_$a_<_1/e$_implies_$a_<_478.81$._Since_$a$_is_an_integer,_effectively_the_maximum_value_is_478._(In_practice_the_function_happens_to_work_for_values_up_to_504.)

If_we_take_$k_=_9$_then_$e_=_1/101_-_5/512_=_7/51712$_and_so_the_maximum_value_of_$a$_is_7387._(In_practice_the_function_happens_to_work_until_7473.)

The_next_value_of_$k$_that_results_in_a_better_approximation_is_13,_giving_$81/8192$._However,_note_that_the_intermediate_value_$ax$_in_the_calculation_will_then_overflow_an_unsigned_16-bit_value_when_$810_\le_a$,_thus_$k_=_7$_works_better_in_this_situation.

__Proof_for_range_for_a_specific_k_

Let_$k_0$_be_the_smallest_integer_such_that_$2^>n$._Take_$k_0+1$_as_a_reasonable_value_for_$k$_in_the_above_equations._As_in_the_code_snippets_above,_let

*_$q_=_\left\lfloor_\frac_\right\rfloor_$_and
*_$r_=_a_-_q_n$.

Because_of_the_floor_function_

In__mathematics_and_computer_science,_the_floor_function_is_the_function__that_takes_as_input_a_real_number_,_and_gives_as_output_the_greatest_integer_less_than_or_equal_to_,_denoted__or_.__Similarly,_the_ceiling_function_maps__to_the_least_int_...