0
$\begingroup$

Example: Suppose I have a number a with 100 decimal digits, b with 200 decimal digits, and m with 10 decimal digits.

Would the speed of the computation a mod m vary greatly from b mod m because of the size of a vs b?

$\endgroup$
2
$\begingroup$

Yes. You are doing long division. Whatever method you use, you will lose you a roughly constant number of digits per step, so there will be twice as many (well, about $\frac{190}{90}$ times as many) steps for $b$ as for $a$.

$\endgroup$
0
$\begingroup$

In general it does, however, for certain special cases it will not.

A simple example is when $m$ is a power of 2. Then, the reminder is exactly the last $\log m$ bits of $n$, regardless of the size of $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.