To factor a semiprime (the product of two prime numbers), one needs to first take the inverse of the semiprime. Then count the number of digits in the decimal expansion until the sequence begins to repeat.
7*17=119 (119 is a semiprime, it is only divisible by 7 and 17)
For the next part, pretend you don’t know that 119 is 7*17.
1/119= 0.0084033613445378151260504201680672268907563025210084033613445378151260504
20168067226890756302521008403…
At the underlined digits, the sequence begins to repeat. There are 48 digits until the sequence begins to repeat. The repeating sequence is 008403361344537815126050420168067226890756302521.
Now if you take 119, and find how many times 48 goes into it evenly (or without any remainder), you can obtain the sum of 7 and 17. This is because the remainder is always 1 less than the sum of the two primes.
Let me demonstrate:
119/48=2.479
Get rid of the decimals here, and multiply 48 by 2, which is 96. 96 is Euler’s totient.
119-96 is 23. Add 1, and you get 24 (the sum of 7 and 17).
Since all semiprimes are only composed of 2 possible factors, we know that if you take 24, and divide by 2, you will always get the average of the two prime numbers. From here, it’s a simple variance problem to find the prime numbers since you know the sum of the primes, the average, and the product.
You can see more examples in the Examples section.
Some minor variations to this algorithm are needed for certain semiprimes, but the key step is always finding the number of repeating digits of the inverse of the semiprime. In fact, for most of these other semiprimes, finding the number of digits of the repeating sequence leads directly to Euler’s totient or even one of the prime factors themselves.
This might have some application in speeding up computations and discrete Fourier transformations.
You can see how it works, in the How it Works section. For the full algorithm, see the Full Semiprime Factorization section.
-Jeremy DeGroff (Copyright 2015)
degroffprimenumbers 