1
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ That will depend on what you do with $\mu$. What about describing it? $\endgroup$
    – fgrieu
    Apr 10 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$
    – Lip
    Apr 12 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 at 7:52
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.