Another problem with matrix inversion

["Lorenz Minder" <lminder@gmx.net>]

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:

Reading GPRC: /etc/gprc ...Done.

                  GP/PARI CALCULATOR Version 2.3.4 (released)
       powerpc running linux (portable C/GMP-4.2.2 kernel) 32-bit version
               compiled: Jul 24 2008, gcc-4.3.1 (Debian 4.3.1-6) 
                (readline v5.2 enabled, extended help available)

                     Copyright (C) 2000-2006 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and 
comes WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.

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

Best regards,
--Lorenz
-- 
Neu: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate + Telefonanschluss für nur 17,95 Euro/mtl.!* http://dslspecial.gmx.de/freedsl-surfflat/?ac=OM.AD.PD003K11308T4569a