I have been trying to read a lot of literature concerning the above subject but I've not found anything useful to help my case.
Suppose you're given a linear diophantine in $a_1,a_2,\ldots,a_k$ where $k\leq 10$, and we are asked to tell if $a_1 x_1 + a_2 x_2 + \cdots+a_kx_k = N$ has a non negative solution or not?
We are given many such queries, so I think regular Euclid method wouldn't be sufficient.
Also,since I anyway brought the topic, could we utilise the calculation of the Frobenius Number of the equation to answer the above query.
One useful approach is to combine integer linear programming with lattice reduction, e.g. see Lichtblau: Integer Linear Programming, Frobenius Instances, and Frobenius Numbers