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

PS: Sorry, I answered to the wrong list... :-/

Just for fun, the sequence I suggested in PARI/GP syntax:
{
 e=21;
 a11=1;a12=1;a21=1;a22=0;
 for(i=1,e,
   s1=a22+a12;a22=a22-a21;s3=a22+a12;s4=s3-a11;
   p1=s1^2;p2=a22^2;p3=s3^2;p4=a11^2;p5=a12*a21;p6=s4*a12;p7=a21*s4;
   s1=p3+p5;s4=p1-s1;s3=s1-p2;a21=p4+p5;a22=s3-p6;a11=s4-p7+a21;a12=p2+s4+a22
 );
 a12==fibonacci(2^(e+1)-1)
}


-- 
http://bodrato.it/papers/