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 (-5[1])(*) Shor performs it in polynomial time. RSA (-5[1])encryption (10[1])works because this task is hard to do for very large integers. (0[1])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■ (10[1])

Back to tossups

Buzzes

Summary