22
$\begingroup$

This seems like a question that should have an easy answer, but I don't have a definitive one:

If I have two $n$ bit numbers $a, p$, what is the complexity of computing $a\bmod p$ ?

Merely dividing $a$ by $p$ would take time $O(M(n))$ where $M(n)$ is the complexity of multiplication. But can $\bmod$ be performed slightly faster ?

$\endgroup$
2
  • 1
    $\begingroup$ Maybe a dumb question, but can you convert $a$ to be written in base $p$ and then look at the LSB? $\endgroup$
    – Pål GD
    Jun 27, 2013 at 20:45
  • 2
    $\begingroup$ You could, but that seems like extra work, and would probably require division. $\endgroup$
    – Suresh
    Jun 28, 2013 at 0:33

1 Answer 1

12
$\begingroup$

Shoup (Section 3.3.5, Theorem 3.3, p. 62) gives a bound for computing the residue $r$ in time $O(n\log q)$ where $a = q\cdot p +r$ and $\log a = n$.

I guess that if $p$ and $a$ are both roughly $n$ bit numbers, then $q$ (and hence $\log q$) should be rather small, giving $O(n)$.

If $a$ is an $n$-bit number, and $p$ is relatively small, then the multiplication approach should be faster.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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