I'm looking for solution to a problem to calculate modulo of very large number that can contain 25000 digits or less (n) with 10 digit number (m). ( n % m ) ?

Pointer to appropriate theory resource is also welcome.


  • $\begingroup$ You mean on a computer? You'll probably have to use a bignum library of some kind – in which case this is just a programming question, rather than mathematics. $\endgroup$ – Zhen Lin Nov 4 '12 at 11:49
  • $\begingroup$ Do you have the numbers in some special form or are you asking about the general case? $\endgroup$ – Karolis Juodelė Nov 4 '12 at 11:49
  • $\begingroup$ @KarolisJuodelė General Case. $\endgroup$ – Amit Jain Nov 4 '12 at 11:51
  • $\begingroup$ Why is the case of large number different from the case of small numbers? As Zhen asked, is this a programming problem? $\endgroup$ – Karolis Juodelė Nov 4 '12 at 11:55
  • 1
    $\begingroup$ If I had to guess, the big number is obtained by exponentiating something, in which case the most efficient course of action is to keep reducing modulo $m$ while computing $n$ in the first place! $\endgroup$ – Zhen Lin Nov 4 '12 at 12:50

As small as your modulus is, I don't think you can do significantly better than ordinary long division (typically done in base $2^{64}$) to compute the remainder.

However, you can optimize the individual steps; e.g. by using an algorithm like Barrett reduction to obtain the remainder of a 2 digit x 1 digit remainder calculation.

Writing efficient (or even simply correct) division code is a very irritating task; unless you really, really like this sort of programming or are using a specialized algorithm for a very special case, you are certainly better off with a good (or even just decent) bignum package.


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.