squaring modulo an integer
Juergen Bullinger
juergen.bullinger at gmx.net
Thu Feb 16 16:04:53 CET 2006
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>
More information about the gmp-discuss
mailing list