Нашли опечатку? Выделите ее мышкой и нажмите Ctrl+Enter
Название: Solving linear diophantine systems
Авторы: Mulders T., Storjohann A.
Аннотация:
A simple randomized algorithm is given for finding an integer solution to a system of linear Diophanrinc equations. Given as input a system which admits au integer solution, the algorithm ran be used to find such a solution with probability at least 1/2. The running time (number of bit operations) is essentially cubic in the dimension of the system. The analogous result is presented for linear systems over the ring of polynomials with coefficients from a field.