squaring modulo an integer

[Juergen Bullinger]

Hello Paul,

I asked a question about squaring modulo an integer on gmp-discuss on
30. January. You were so kind to answer. You said:


>A significant speedup could be obtained for large operands as follows:
>
>- using the fact that the divisor is invariant (precomputing its inverse)
>
>- using a subquadratic implementation of Montgomery's REDC, which can
>  perform a modular reduction in 1.5 M(log m). See page 6 of
>  <http://www.loria.fr/~zimmerma/papers/ecm-submitted.pdf>.

What did you exactly mean by "precomputing its inverse"?
I think you meant the inverse modulo a power of two, right?

Is the following description of what has to be done right:
For example let n:=q*m+r with 1<=r<m (m and r are the values I expect as a result of tdiv_qr and m is the divisor).

1. build the inverse m' that m*m' = 1 (mod 2^x)
2. set t:= m'*n
3. if n is a multiple of m set r:=0, q:=t and return the result

But what happens if n is not a multiple of m? In this case we have

t= q*m*m' + r*m' = q + r*m' (mod 2^x)

but how do I get q and r now without a modular divison now?
I guess I have to choose x so that the numbers q and r*m' can be read from t by a simple bit shift operation and maybe an exact division.
In other words x would be choosen so that as many of the least significant bits in m' are 0 as there are bits in q.

I guess ist would work, but at the moment I don't know how the proper value for x can be found and I fear that the value for m' would get very large this way in comparison to m.








-- 
Juergen Bullinger <juergen.bullinger at gmx.net>