squaring modulo an integer

[Juergen Bullinger]

Hello Paul,

thank you for your answer. That doesn't look too frightening. I already
expected the worst :o)
Maybe I'll have time to test that in the next weeks.

regards
Jürgen

Am Donnerstag, den 16.02.2006, 17:33 +0100 schrieb 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
> 
-- 
Juergen Bullinger <juergen.bullinger at gmx.net>