avoiding adjustments in modular computations

[Zimmermann Paul]

       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