Let f(t) = t^d - c_{d-1}t^{d-1} - ... - c_0 be a
monic polynomial of degree d with coefficients in \mathbb{Z} and suppose that p = f(2^m) is a Solinas prime. Given a number n with up to 2md bits, we want to find a number
congruent to n mod p with only as many bits as p – that is, with at most md bits. First, represent n in base 2^m: :n = \sum_{j=0}^{2d-1}A_j2^{mj} Next, generate a d-by-d
matrix X = (X_{i,j}) by stepping d times the
linear-feedback shift register defined over \mathbb{Z} by the polynomial f: starting with the d-integer register [0 | 0 |...| 0 | 1], shift right one position, injecting 0 on the left and adding (component-wise) the output value times the vector [c_0,...,c_{d-1}] at each step (see [1] for details). Let X_{i,j} be the integer in the jth register on the ith step and note that the first row of X is given by (X_{0,j}) = [c_0,...,c_{d-1}]. Then if we denote by B = (B_i) the integer vector given by: :(B_0 ... B_{d-1}) = (A_0 ... A_{d-1}) + (A_d ... A_{2d-1})X, it can be easily checked that: :\sum_{j=0}^{d-1}B_j2^{mj}\equiv\sum_{j=0}^{2d-1}A_j2^{mj} \mod p. Thus B represents an md-bit integer congruent to n. For judicious choices of f (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 (n - p \cdot (n / p)). ==Examples==