squaring modulo an integer

[Paul Zimmermann]

> 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