I start with the small primes as long as the y is bigger the a primitive long value. I check if ax+b is a root of n mod the small prime. If so I divide y by the prime. If y is a long value I switch to trial division.
If the y (reduced by the dividing primes) is lower the the maximal factor of the factor base, the y is a factor of the origianl y itself, and we can stop here.
|