Lorenz Minder on Mon, 11 May 2009 05:57:01 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
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: 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