Tossup

Hendrik Lenstra developed an algorithm for performing this task using elliptic curves, whose two-stage variant is analogous to one named after Pollard. (-5[2])Dixon’s method for performing this task forms the basis of an algorithm for performing this task using continued fractions. In 1994, a quantum algorithm for performing this task in polynomial time was developed by Peter Shor. (10[2]-5[1])RSA encryption relies on the difficulty of performing this (10[1])task for large integers. (0[1]-5[1])For an integer (10[1])n, a brute force method (10[1])for performing this task checks all the integers (-5[1])from 1 to the square root of n. For 10 points, name this task that decomposes an integer into a product (10[2])of smaller integers. (10[1])■END■ (10[2])

Back to tossups

Buzzes

Summary