The most efficient classical method of performing this operation is selecting a pair of small-degreepolynomials over the rationals with a common integer root in the General Number Field Sieve.
The most efficient classical method of performing this operation is selecting a pair of small-degreepolynomials over the rationals with a common integer root in the General Number Field Sieve. Amethod of doing this which finds a cycle in a pseudo-random sequence is Pollard's rho algorithm.Shor developed a polynomial-time algorithm for doing this on a (*) quantum computer. The ability toperform this function quickly for large inputs would defeat RSA encryption. A simple method ofperforming this operation is trial division, and this problem is somewhat more difficult than primalitytesting. For 10 points, identify this operation which decomposes a number into the product of powers ofprimes.
The most efficient classical method of performing this operation is selecting a pair of small-degreepolynomials over the rationals with a common integer root in the General Number Field Sieve.
prime factorization [or integer factorization; accept factoring instead of "factorization"]