Let be a monic polynomial of degree with coefficients in and suppose that is a Solinas prime. Given a number with up to bits, we want to find a number congruent to mod with only as many bits as – that is, with at most bits.
First, represent in base :
Next, generate a -by- matrix by stepping times the linear-feedback shift register defined over by the polynomial : starting with the -integer register , shift right one position, injecting on the left and adding (component-wise) the output value times the vector at each step (see [1] for details). Let be the integer in the th register on the th step and note that the first row of is given by . Then if we denote by the integer vector given by:
- ,
it can be easily checked that:
- .
Thus represents an -bit integer congruent to .
For judicious choices of (again, see [1]), this algorithm involves only a relatively small number of additions and subtractions (and no divisions!), so it can be much more efficient than the naive modular reduction algorithm ().