How useful is factoring large numbers - Not for cryptography!

464 Views Asked by At

This is a question for my curiosity.

Apart from its implications to cryptography. Is factoring large numbers really useful?

Are there any examples of where the ability to factor huge numbers, 1K bits plus would be useful?

Sorry if this is not really a mathematical question, but I reasoned someone with a maths background would be more able to answer this question. I guess I could have asked on physics forums as well.

1

There are 1 best solutions below

1
On BEST ANSWER

Some examples:

Suppose you want to know all integers whose reciprocals in base $b$ have repeating digit patterns with period dividing $n$. This amounts to finding all factors of $b^n-1$, cf. the Cunningham project. Likewise you may have given some integer $b$ and want to find all integers modulo which $b$ has multiplicative order dividing $n$. For example, with $b=2$, $n=2^k$, knowing suitable moduli would enable optimization of algorithmic details in FFT-based multiplications of long numbers. Again, this means factoring $b^n-1$, which for the choice $b=2$ and $n=2^k$ boils down to factoring Fermat numbers: Note that $2^{2^k}-1 = \prod_{j=0}^{k-1}(2^{2^j}+1)$.

On the theoretical side, factorizations of numbers up to a few hundred decimal digits help raising the lower bound for odd perfect numbers, cf. papers by Brent, Cohen and te Riele and the oddperfect project.