avoiding adjustments in modular computations
bodrato at mail.dm.unipi.it
bodrato at mail.dm.unipi.it
Wed Mar 7 08:03:44 CET 2012
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/
More information about the gmp-discuss
mailing list