Checking for factor base

Question

In algorithms like Dixon's factorization a factor base is used, which contains all primes below a bound.

Then calculates $x^2 \mod n$, and then checks it is in factor base or not.

Suppose $P$ is the factor base for bound $B$.

We calculate the value $x^2 \mod n$, then how to check whether the result contains only prime factors from the factor base?

Let $x^2 \mod n=q_1^{e_1}q_2^{e_2}q_3^{e_3}\cdots q_k^{e_k}$ and $P=\{p_1,p_2,p_3,\cdots,p_l\}$

Then how to check whether each $q_i$ is present in factor base? and how to get corresponding arity $e_i$?

Is it achieved by repetitive division or by means of any other efficient methods?

Answer 1

It can be done using any method you have at your disposal. Obviously, the more efficient method you use, the more efficient your algorithm will be, but even using trial division will yield a significantly more efficient algorithm than if you used trial division for the entire factorisation. Algorithms based on elliptic curves are also commonly used since they are especially good at identifying small prime factors.

By the way, this is not directly related to cryptography so you may get better answers on Math.SE.