 Like the problems introduced above, \(\sc{FACTORIZATION}\) is of considerable practical importance, perhaps most famously because the security of well known cryptographic protocols assume that it is intractable in the general case (see, e.g., Cormen, Leiserson, and Rivest 2005).  But the foregoing observations still do not entail any fundamental limitation on our ability to know a number’s prime factorization. For it might still be hoped that further research will yield a more efficient algorithm which will allow us to determine the prime factorization of every number \(x\) in which we might take a practical interest. A comparison of Euclid’s algorithm and trial division again provides a useful context for describing the properties which we might expect such an algorithm to possess. For note that the prior observations suggest that we ought to measure the size of the input  \(x \in \mathbb{N}\) to a numerical algorithm not by  \(x\) itself, but rather in terms of the length of \(x\)’s binary representation. If we let \(\lvert x\rvert =_{df} \log_2(x)\) denote this quantity, then it is easy to see that the efficiency of Euclid’s algorithm is given by a function which grows proportionally to \(\lvert x\rvert^{c_1}\) for fixed \(c_1\) (in fact, \(c_1 = 1\)), whereas the efficiency of trial division is given by a function proportional \(c_2^{\lvert x\rvert}\) for fixed \(c_2\) (in fact, \(c_2 = 2\)).