# How to calculate modulo of large integer (number having 25000 digits)

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.

Thanks

-
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. –  Zhen Lin Nov 4 '12 at 11:49
Do you have the numbers in some special form or are you asking about the general case? –  Karolis Juodelė Nov 4 '12 at 11:49
@KarolisJuodelė General Case. –  Jaini Nov 4 '12 at 11:51
Why is the case of large number different from the case of small numbers? As Zhen asked, is this a programming problem? –  Karolis Juodelė Nov 4 '12 at 11:55
@KarolisJuodelė Yes, this is a programming problem but I do not want to use bignum library. Because I think there must be interesting property of modulo which can do the task efficiently. Any good source for modular arithmetic in and out? –  Jaini Nov 4 '12 at 12:00

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.

-