Re: Another problem with matrix inversion

[Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr>]

On Mon, May 11, 2009 at 05:55:18AM +0200, Lorenz Minder wrote:
> Hi,
> 
> There's another problem with matrix inversion that I noticed.  In
> GP/PARI if you want to invert a matrix modulo some non-prime integer m,
> then things will not generally work out nicely.  Example:
> 
> parisize = 4000000, primelimit = 500000
> ? A = [ Mod(9, 10), Mod(1, 10), Mod(9, 10); Mod(6, 10), Mod(9, 10), Mod(7, 10); Mod(4, 10), Mod(0, 10), Mod(1, 10)];
> ? 1/A
>   ***   impossible inverse modulo: Mod(5, 10).

PARI only know perform polynomial and linear algebra over a field, so
it assumes that moduli are prime.

> ? B = chinese(1/Mod(A, 2), 1/Mod(A, 5))
> %2 = 
> [Mod(1, 10) Mod(1, 10) Mod(4, 10)]
> 
> [Mod(8, 10) Mod(7, 10) Mod(9, 10)]
> 
> [Mod(6, 10) Mod(6, 10) Mod(5, 10)]
> 
> ? A*B
> %3 = 
> [Mod(1, 10) Mod(0, 10) Mod(0, 10)]
> 
> [Mod(0, 10) Mod(1, 10) Mod(0, 10)]
> 
> [Mod(0, 10) Mod(0, 10) Mod(1, 10)]
> 
> So while A has an inverse in this case, it is not found.  The workaround
> using chinese remaindering works if the factorization is known, so this
> is going to be a problem if the modulus is an RSA modulus, for example.
> It would be better to try to run the algorithm as is, and as soon as a
> nonzero non-invertible remainder is found, to split into two instances
> with the now known partial factorization and continue.  That way, matrix
> inversion would still be n^3*O(poly(log(m))), where m is the
> modulus.
> 
> This would make it possible to compute inverses of matrices mod m if m has
> no square factors.

Yes, we are doing something similar in the round4 implementation.

Cheers,
Bill.