title: Computing sum of linear sequence modulo n
body: <p>I'm looking to calculate the following sum efficiently:</p>
  
  <p>sum (i=0..max) (i * A mod B)</p>
  
  <p>One may assume that max, A &lt; B and that A and B are co-prime (otherwise an easy reduction is possible). Numbers are large, so simple iteration is way too inefficient.
  So far I haven't been able to come up with a polynomial-time algorithm (i.e., polynomial in log(B)), best I could find is O(sqrt(max)). Is this a known hard problem, or does anyone know of a polynomial-time algorithm?</p>
  
  <p>To be clear, the "mod B" only applies to the i*A, not to the overall sum. So e.g.</p>
  
  <p>sum(i=0..3) (i*7 mod 11) = 0 + 7 + 3 + 10 = 20.</p>