avoiding adjustments in modular computations
bodrato at mail.dm.unipi.it
bodrato at mail.dm.unipi.it
Thu Mar 8 07:36:16 CET 2012
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/
More information about the gmp-discuss
mailing list