Larger linear algebra jobs in the past have failed because the only dependency possible was the trivial one, and that can happen even if the matrix is not square (there could be duplicate columns, for example). The odds of that happening are actually the odds that the matrix contains enough duplicate columns to wipe out the nullspace, and I would think the odds of columns being duplicated are fairly small for larger factor bases.
If the input has exactly two factors, you can enumerate the cases where one factor or the other is found, and it turns out the fraction of successful dependencies is 2/3 and not 1/2, so the odds of having 1016 dependencies fail are lower than your estimate. Even if you did have failures, the QS code would restart, find the old relations, and rerun the linear algebra.
Last fiddled with by jasonp on 20090124 at 18:07
