title: Better ways to implement a modulo operation (algorithm question)
body: <p>I've been trying to implement a modular exponentiator recently.  I'm writing the code in VHDL, but I'm looking for advice of a more algorithmic nature.  The main component of the modular exponentiator is a modular multiplier which I also have to implement myself.  I haven't had any problems with the multiplication algorithm- it's just adding and shifting and I've done a good job of figuring out what all of my variables mean so that I can multiply in a pretty reasonable amount of time.</p>
  
  <p>The problem that I'm having is with implementing the modulus operation in the multiplier.  I know that performing repeated subtractions will work, but it will also be slow.  I found out that I could shift the modulus to effectively subtract large multiples of the modulus but I think there might still be better ways to do this.  The algorithm that I'm using works something like this (weird pseudocode follows):  </p>
  
  <pre><code>result,modulus : integer (n bits) (previously defined)
  shiftcount : integer (initialized to zero)
  while( (modulus&lt;result) and  (modulus(n-1) != 1) ){
       modulus = modulus &lt;&lt; 1
       shiftcount++
  }
  for(i=shiftcount;i&gt;=0;i--){
       if(modulus&lt;result){result = result-modulus}
       if(i!=0){modulus = modulus &gt;&gt; 1}
  }
  </code></pre>
  
  <p>So...is this a good algorithm, or at least a good place to start?  Wikipedia doesn't really discuss algorithms for implementing the modulo operation, and whenever I try to search elsewhere I find really interesting but incredibly complicated (and often unrelated) research papers and publications.  If there's an obvious way to implement this that I'm not seeing, I'd really appreciate some feedback.  </p>