Round 9: Tossup 3

The SNFS algorithm for this task has been partially used by the Cunningham Project. Finding a cycle in a pseudorandom sequence is used to perform this task by Pollard's rho algorithm. Leonard Adleman coined the name of “smooth” inputs for which this task is relatively simple. A quantum algorithm for this task developed by Peter (*) Shor performs it in polynomial time. RSA encryption works because this task (10[1])is hard to do for very large integers. Brute-forcing this task checks every integer from 1 to the square root of n. For 10 points, what task decomposes an integer into a product of smaller integers? (10[1])■END■

Back to tossups

Buzzes

Summary