Of coarse we have to calculate \floor{q_i^2} mod N to determine the factors over the factor base. The squaring is very time consuming.
Maybe we can improve here if we do some restrictions.

If we have a sieving interval M the resulting size of the values of q(x) is in O(M*sqrt (N)).
For QS M is O(exp (sqrt (log (N) * log log (N))) and the values were bounded by O(N).
So I expect the running time to be decreased only by an constant factor in the exponent (something like sqrt (2)), which is far away from the NFS.
But for the CFRAC the same should hold as well??
I'm going to implement it. I already have a MPQS in place so lets see how it will be compared with it.

The answer to my first question is rather simple if q(x) is getting greater then N we have to reduce it by applying mod N on the result. But then we can not be sure that 'a' still divides q(x), so we have to limit M. and choose different a's.