Lorenz Minder on Mon, 11 May 2009 05:57:01 +0200

 Another problem with matrix inversion

```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:

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

```