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

Back to tossups

Buzzes

Summary