To find a factor of n, find some m such that (m,n) is not 1

Quick description

If you are trying to design an algorithm for factorizing large numbers, then an easy but useful observation is that if you can find some $m$ such that the highest common factor of $m$ and $n$ is not $1$ , then you can find a factor of $n$ by applying Euclid's algorithm (which is very efficient) to $m$ and $n$ .

Prerequisites

Elementary number theory

Example 1

Suppose that you didn't know that $91$ could be factorized as $7\times 13$ , and somebody gave you the information that $64^2\equiv 1$ mod $91$ . You could reason as follows. If $x^2\equiv 1$ mod $n$ , then $(x+1)(x-1)\equiv 0$ mod $n$ , which is the same as saying that $n$ is a factor of $(x+1)(x-1)$ . Therefore, $n$ cannot be coprime to both $x+1$ and $x-1$ . Applying that to our example, we know that $91$ has a factor in common with either $63$ or $65$ . Applying Euclid's algorithm, we find that $(91,63)=7$ and also that $(91,65)=13$ .

General discussion

The simple trick shown here has the obvious drawback that it depended on our being told a highly nontrivial piece of information. But that is not surprising, given that there is no known quick algorithm for factorizing large numbers, and it is widely believed that no such algorithm exists. From a theoretical point of view, the trick is important, and is in fact a vital component of Shor's famous proof that efficient factorizing can be done with a quantum computer.

Login or register to post comments
1073 reads