avoiding adjustments in modular computations
Zimmermann Paul
Paul.Zimmermann at loria.fr
Wed Mar 7 09:13:15 CET 2012
Dear Marco,
> Date: Wed, 7 Mar 2012 08:03:44 +0100 (CET)
> From: bodrato at mail.dm.unipi.it
>
> Ciao Paul,
>
> Il Ven, 2 Marzo 2012 5:04 pm, Zimmermann Paul ha scritto:
> > I wrote a short note showing that in some cases we can completely avoid
> > adjustment steps (for example x = x - N) in computations modulo N:
> >
> > http://www.loria.fr/~zimmerma/papers/norm.pdf
>
> A small comment about the adjustment step for addition of "symmetric
> word-aligned". In many cases, you suggest, we can also skip the check. But
> I'd write it differently for the pieces of code where we can not avoid it.
> You write:
>
> if c >= B:
> c = c - kN
> if c >= B
> c = c - N
>
> At first I'd suggest to use c = c - kN also in the secondary branch, but
> it's probably even better to just write (if k>=2):
>
> if c >= B
> c = c - [3k/2]N
>
> There is a branch hidden in this code (the sign choice), but the resulting
> distribution should be more symmetric.
>
> Regards,
> m
>
> --
> http://bodrato.it/papers/
you are right. We could even use c = c - k1*N where k1 = round(3B/2/N), where
you suggest k = round(3k/2). The idea is that if c is in [B,2B], the "mean"
value should be around 3B/2.
But we could also do the same for the first adjustment, no?
Anyway in my experiments the second adjustment is never used, even if I choose
N near from B. This is because my test program only performs multiplications
on a and b, and |a|, |b| remain bounded by N, thus |a|+|b| < 2N, and one
reduction is always enough. I have to find another test program which mixes
additions and multiplications on the same variables.
Paul
More information about the gmp-discuss
mailing list