squaring modulo an integer
Paul Zimmermann
Paul.Zimmermann at loria.fr
Thu Feb 16 17:33:48 CET 2006
> From: Juergen Bullinger <juergen.bullinger at gmx.net>
> Date: Thu, 16 Feb 2006 16:04:53 +0100
>
> 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?
I meant what is known as "Barrett division", or its equivalent for Montgomery
reduction.
> 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.
If you are doing several successive additions/multiplication modulo the same
integer m, then you can work in the "Montgomery space", where a residue n is
replaced by n*X, where m < X=2^x (usually we denote X by R, but I follow your
notations).
Now if m*m' = -1 (mod X), then compute t = m'*n (mod X), and then
(n+t*m)/X [n+t*m is exactly divisible by X].
Another useful reference is [19] from the above article, available at
<http://arith17.polito.it/final/paper-156.pdf>.
Paul
More information about the gmp-discuss
mailing list