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?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ That will depend on what you do with $\mu$. What about describing it? $\endgroup$– fgrieu ♦Apr 10, 2021 at 17:53
-
$\begingroup$ 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. $\endgroup$– LipApr 12, 2021 at 7:40
-
$\begingroup$ 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$). $\endgroup$– fgrieu ♦Apr 12, 2021 at 7:52
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$.