Dado un entero compuesto n (a lo largo de este artículo, n será «el entero a factorizar»), la división por tentativa consiste en intentar dividir n entre todo número primo menor o igual a √n.
Si se encuentra un número que es divisor de n, en división entera, ese número es un factor de n. Es posible determinar un límite para los factores primos.
Entonces el valor del último número primo probado como un posible factor de n sería
Aunque todo esto está muy bien, normalmente el inconveniente de inspeccionar un n concreto para determinar el valor correcto de i es más costoso que simplemente probar con el único candidato innecesario
Puede la raíz cuadrada de n ser entera, entonces es un factor y n es un cuadrado perfecto, pero no es esta una manera buena de encontrarlos.
La división por tentativa garantiza encontrar un factor de n, puesto que comprueba todos los factores primos posibles de n. Por tanto, si el algoritmo no encuentra ningún factor, es una prueba de que n es primo.
En lo anterior no se ha tenido en cuenta la sobrecarga del test de primalidad para obtener los números primos candidatos a ser factores.
Si se utiliza una variante sin el test de primalidad, sencillamente dividiendo por todo número impar menor que la raíz cuadrada de n, ya sea primo o no, puede llegar a necesitarse alrededor de tentativas, que para un n grande es peor.
Esto significa que para un n con factores primos grandes de tamaños similares (como aquellos empleados en la criptografía asimétrica), la división por tentativa es computacionalmente impracticable.
Sin embargo, para un n con al menos un factor pequeño, la división por tentativa puede ser un método rápido para encontrar ese factor pequeño.