At the heart of an algorithm for calculating optimal addition chains I prune by either showing a linear Diophantine equation has no solutions or enumerate some small number of solutions and reject them via other criteria. It is the standard Frobenius equation:
$\sum_{i=1}^za_ix_i=n$
For a given $n$ I may try to solve billions of these equations as I traverse a search tree. A particular point in the search tree defines the $a_i$ values. I must try to solve with $1\le x_i \le l_i$. $l_i$ is defined by the remaining tree depth along the searched path. If I can prove the equation has no solutions I can prune a branch of the tree. This is a very effective technique. If i think the equation has only a small search space I try to enumerate possible solutions using a backtracking search. For equations I think have a large search space I calculate $g=GCD(a_1,...,a_z)$ and then check that $g|n$. This GCD is very costly and I use a bunch of tests to try and avoid it if I can see it will succeed.
Are there other techniques I might use where I do a large number of GCDs with different numbers and make sure the GCD divides a fixed $n$? Preprocess $n$ in some way?
I find that trying to solve the linear equation directly with something like the Blankinship algorithm is too slow. Backtracking search works better even though it searches parts of the tree were no solutions are possible because of divisibility. Divisions are a real killer to performance.
Is it possible somehow while doing all the divisions in a backtracking search to find ranges for the $x_i$ values to deduce something about the basis vectors for solutions to the linear equation?