Bill Allombert on Mon, 11 May 2009 16:06:19 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Another problem with matrix inversion |
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.