avoiding adjustments in modular computations

[bodrato at mail.dm.unipi.it]

Ciao Paul,

Il Mer, 7 Marzo 2012 9:13 am, Zimmermann Paul ha scritto:
>> From: bodrato at mail.dm.unipi.it
>> if c >= B
>>   c = c - [3k/2]N

> you are right. We could even use c = c - k1*N where k1 = round(3B/2/N),

Right!

> But we could also do the same for the first adjustment, no?

I was trying to suggest exactly this: a single adjustment.

> reduction is always enough. I have to find another test program which
> mixes additions and multiplications on the same variables.

If you like Fibonacci, I can suggest to compute the {2^n-1}-th Fibonacci
number modulo N by computing [1,1;1,0]^{2^n-1}, using Strassen-Winograd to
square the matrix :-) and a couple of additions for the [1,1;1,0]*matrix
stage.
Using Strassen for a symmetric 2x2 matrix is obviously a nonsense, but it
will give a "long" sequence of linear operations.

Best regards,
m

-- 
http://bodrato.it/