Diophantine linear system solving
Thom Mulders, Arne Storjohann · 1999
A sinq)lo randoruixed algorithnl is given for fillding an integer solubion to a s:-stclu of linear Di01)lmnt,ine equations.Givcu as input a s?;stcrrl which admits an int.cger solul.ion, the id- gorithru can 1~ used t,o find such a.solution wit,h probabilit~~ ilt least l/2.The running time (nunlber of bit operations) is esscntiall~ cubic in the dimemion of the s?;stem.The malogous result is prcsentctl for 1inca.rspst.cnls over the ring of polqonlials wit.li coefficients from a field.