Packet 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 (15[2]-5[1])coined (15[1])the name of “smooth” inputs for which this task is relatively simple. A quantum algorithm for this task developed (15[1])by Peter (-5[1])(*) Shor (10[4]-5[1])performs (10[3])it (10[1])in (10[4])polynomial (10[1]-5[2])time. (10[3])RSA (-5[2])encryption (10[1]-5[1])works (10[1])because (10[1])this task (10[1])is hard (-5[1])to do (0[1])for (10[2])very large integers. (10[2]0[1]-5[2])Brute-forcing (10[1])this task checks every integer from 1 to the square root of n. For 10 points, what task decomposes an integer into a product (10[1])of smaller (10[1])integers? (10[1])■END■ (10[5])

Back to tossups

Buzzes

Summary