avoiding adjustments in modular computations

Zimmermann Paul Paul.Zimmermann at loria.fr
Thu Mar 8 11:12:01 CET 2012


> 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.

good idea! In the same vein, I could also compute [1,2]^n considering [1,2]
as a complex vector, with the complex multiplication [ac-bd,ad+bc].


More information about the gmp-discuss mailing list