I'm putting together a primality tester for large numbers. When the numbers were smaller things were more straightforwards. I got refined it to a point where I could quickly test any number within the range of long long ints. I wanted to be able to test larger numbers. I've gotten it to read the numbers in as strings then convert to an array. I now have the issue of not knowing how to perform mod on arrays. (int*)mod(int) isn't too bad but (int*)mod(int*) is more complicated.

In short:

  1. Is there a relationship between n%c and n%a,n%b where a+b=c

  2. How do you take the mod of 2 sums where either sum would give you overload.

  • 1
    $\begingroup$ The description part of your question is pure implementation problem, which is not clearly stated and off-topic here. We prefer to state one question per post and also to make some research prior to asking. 1) looks like pure math, 2) part is unclear - how do you store the number if it causes overload? If this is causing all the trouble, it is unfortunatelly off-topic here because it asks about implementation details (might be on-topic on Stack Overflow). $\endgroup$ – Evil May 22 '16 at 22:28
  • $\begingroup$ Sounds like an XY problem. See en.wikipedia.org/wiki/Primality_test. $\endgroup$ – D.W. May 22 '16 at 22:47

Representing integers that are larger than the machine integer size by an array of digits is the standard way to do it, and it's usually called bignum, or more formally arbitrary-precision arithmetic.

Division on bignums is not simple. There's no shortcut: it isn't like with addition and subtraction where you can make a single loop that goes over both arrays. You can use the long division method you learned in primary school. There are more complex methods that have better performance in general; the Wikipedia article has a good overview.

There is no useful relationship between $n \bmod (a+b)$ and $n \bmod a$ and $n \bmod b$. I don't see where this would come up anyway. (On the other hand, $(a+b) \bmod p$ is either $(a \bmod p) + (b \bmod p)$ or $(a \bmod p) + (b \bmod p) - p$ depending on whether the sum overflows $p$).

When computing with numbers modulo $n$, always reduce modulo $n$ after each operation, to avoid having numbers grow too large. During one operation, it's usually useful to allow one more digit, to accumulate carries on partial results.

Note that primality testing is rarely done on large numbers, because it gets extremely slow. In cryptography, approximate algorithms are used, that have a small probability of accepting a composite number as prime (but if the algorithm says “prime”, then the number may not be prime, but it's “difficult” to factor).


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