What if the bitlength of the value evaluated in Barrett reduction is greater than 2k the modulus?

Question

For $c\equiv a \pmod n$, in Barrett Reduction, $\mu = \lfloor{\frac{2^{2k}}{n} \rfloor}$ is precomputed, where $k = \lceil{\log_2{n}} \rceil$ and the bitlength of $a$ is assumed to be less than $2k$. What if the bitlength of $a$ is much greater than $2k$? Is the result of Barrett Reduction still correct?

Answer 1

This depends upon how close $\mu/2^{2k}$ is to $1/n$.

In Barrett reduction we approximate the integer $q=[a/n]$ with $q'=[a\mu/2^{2k}]$ in the operation $$a\mapsto a-qn.$$ If we write $\delta=1/n - \mu/2^{2k}$ then the difference between $a/n$ and $a\mu/2^{2k}$ is $a\delta$ and if this is less than 1 then $q$ and $q'$ differ by at most 1 (which is why Barrett has a possible extra $-n$ step). In general, we know that $\delta<1/2^{2k}$ and so $a\delta<1$ for $a<2^{2k}$. For larger values of $a$, note $q-q'$ can be as large as $[a\delta]+1$ and so the number of surplus multiples of $n$ could be that large. In the worst cases, if $a$ is $m$ bits where $m>2k$, then we could be off by $2^{m-2k}$ multiples of $n$. We can of course apply Barrett iteratively or do more conditional subtracts, but this soon stops being efficient in comparison to direct computation of $q$.

Of course, there are also good very good cases where $\delta$ is small (a lower bound is $\delta\ge 1/2^{2k}n$) and we get good behaviour for a large range of $a$ (up to $a<n2^{2k}$ in the best case).

If you want a more accurate generalisation, you can for example use $\mu=[2^{m}/n]$ and shift $a\mu$ right by $m$ and conditional subtract. This is guaranteed fine for $a<2^{m}$, but be careful how $a\mu$ fits into various word sizes. The size $2k$ is chosen simply because it useful when multiplying two numbers less than $n$ together and reducing modulo $n$.