# Fast algorithm for modular division (residue)

I'm looking for a fast algorithm to perform division of large numbers (by hand). Traditional long division just isn't fast enough for my needs.

In most of these cases, I'm only looking for the modulus/remainder of the division, so if there is a fast algorithm specifically for this purpose, it would suffice. (But, if there is a way to get the quotient as well, it would also help).

Edit: Now that I think about it, the algorithm for synthetic division/synthetic substitution involves no division (and addition/multiplication is typically easier and faster than division). Is there perhaps a clever way to adapt this algorithm for fast numerical division?

-
When you say "by hand," how large are the numbers involved here, and what exactly are your needs? –  Qiaochu Yuan Oct 10 '10 at 0:02