title: Computing (a*b) mod c quickly for c=2^N +-1
body: <p>In 32 bit integer math, basic math operations of add and multiply are computed implicitly mod 2^32, meaning your results will be the lowest order bits of the add or multiply.</p>
  
  <p>If you want to compute the result with a different modulus, you certainly could use any number of BigInt classes in different languages. And for values a,b,c &lt; 2^32 you could compute the intermediate values in 64 bit long ints and use built in % operators to reduce to the right answe</p>
  
  <p>But I've been told that there are special tricks for efficiently computing a*b mod C when C is of the form  (2^N)-1  or (2^N)+1, that don't use 64 bit math or a BigInt library and are quite efficient, more so than an arbitrary modulus evaluation, and also properly compute cases which would normally overflow a 32 bit int if you were including the intermediate multiplication.</p>
  
  <p>Unfortunately, despite hearing that such special cases have a fast evaluation method, I haven't actually found a description of the method.  "Isn't that in Knuth?" "Isn't that somewhere on Wikipedia?" are the mumblings I've heard.</p>
  
  <p>It apparently is a common technique in random number generators which are doing multiplies of a*b mod 2147483647,  since 2147483647 is a prime number equal to 2^31 -1. </p>
  
  <p>So I'll ask the experts. What's this clever special case multiply-with-mod method that I can't find any discussion of?</p>