method is trial division: checking if the number is divisible by prime numbers , , , and so on, up to the square root of . For larger numbers, especially when using a computer, various more sophisticated factorization algorithms are more efficient. A prime factorization algorithm typically involves testing whether each factor is prime each time a factor is found.

When the numbers are sufficiently large, no efficient non-quantum