avoiding adjustments in modular computations

[bodrato at mail.dm.unipi.it]

Ciao,

Il Gio, 8 Marzo 2012 11:12 am, Zimmermann Paul ha scritto:
>> 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].

Of course, but I'd suggest again to use Gauss (or Karatsuba) for the
complex squaring, to obtain a longer sequence of additions in-between two
multiplications.
With big enough modulus it is also a good choice on the performance side :-)

Regards,
m

-- 
http://bodrato.it/