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. (15[1])Leonard Adleman coined (15[1])the name of “smooth” inputs for which this task is relatively simple. A quantum algorithm for this task developed by Peter (*) Shor performs (10[1])it in polynomial time. RSA encryption works (10[1])because this task is hard to do for (10[1])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? ■END■

Back to tossups

Buzzes

Summary