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

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?

• That will depend on what you do with $\mu$. What about describing it?
– fgrieu
Apr 10, 2021 at 17:53
• I try to calculate the product $a$ of two integers which might be larger than $n$, and then do the modular operation. I want to use a larger $\mu$ to fit the product.
– Lip
Apr 12, 2021 at 7:40
• Computing $c\gets u\cdot v\bmod n$ when $a=u\cdot v$ is larger than $n^2-1$: at least one of $u$ or $v$ is larger than $n-1$. The usual technique computes $\tilde u\gets u\bmod n$ and $\tilde v\gets v\bmod n$, then $c\gets\tilde u\cdot\tilde v\bmod n$, where the intermediary product is now small enough for regular Barrett reduction. For large arguments, this is faster, because the multiplication involves smaller arguments and is less costly. If $u$ (or $v$) is already larger than $n^2-1$, we can use repeated steps of Barrett reduction to compute $\tilde u$ (or $\tilde v$).
– fgrieu
Apr 12, 2021 at 7:52

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 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$$.