avoiding adjustments in modular computations

[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/