1

What is the current state of the art method for determining, the residue of a large integer $k$ modulo $m$?

The only useful idea I can think of, which Ive seen used in base 10, is if $k$ was written in a positional numeral system with base $p$, and $\gcd(p,m)=1$, I could pick off each digit and multiply it by its corresponding power of $p$ reduced modulo $m$, which could be done efficiently if one had knowledge of the order of $p$ modulo $m$ (as the reduced exponents modulo $m$ would eventually be periodic, with primitive period $\mathrm{ord}_m(p)$) but I don't think for large numbers the modulo order can be obtained easily, so does any one know of a more efficient method?

Sigur
  • 6,416
  • 3
  • 25
  • 45
Ethan Splaver
  • 10,613
  • What is wrong with dividing $k$ by $m$ and noting the remainder? – Gerry Myerson Jan 23 '13 at 00:24
  • It takes to long, you can more easily determine the remainder using other methods – Ethan Splaver Jan 23 '13 at 00:24
  • http://en.wikipedia.org/wiki/Division_algorithm is a good start. – Greg Martin Jan 23 '13 at 00:48
  • I am looking for how to obtain the residue from dividing one integer by another, not the quotient of the two, this requires more work then the latter – Ethan Splaver Jan 23 '13 at 00:50
  • Is finding that weighted sum really any faster than just dividing and noting the remainder? It may be faster for modulus $3$ if the number is written in base $10$, but is it faster in general? – Gerry Myerson Jan 23 '13 at 01:08
  • When large integers are involving it it can be much faster. And as long as the base of the positional system and the modulus are coprime we can find such weighted sums, also if one is working with many integers some fixed modulus, it would be very time consuming to continually divide them. – Ethan Splaver Jan 23 '13 at 01:09

0 Answers0