I recently learned about how Fermat's factorization method was used to efficiently factorize some RSA public keys.
Basically, the RSA public key is a semiprime, meaning that its only factors are two (different) prime numbers. And, if these prime numbers are close to each other, then Fermat's factorization method can quickly find the factors. The basic form of this factorization method is (a  b) * (a + b)
, where ab
is one factor and a+b
is the other factor.
Here's my commented code in a GitHub Gist for calculating the RSA factors using Kotlin:
 I'm using
BigInteger
s in my code because the numbers I'm factoring quickly pass the limits oflong
s. All RSA public keys are much larger thanlong
.
Here's some times I benchmarked on my desktop:
20bit, 640361 , Factors: (397, 1613) in 1 ms (iterations: 204)
30bit, 903395833 , Factors: (14869, 60757) in 5 ms (iterations: 7756)
40bit, 923078151197 , Factors: (501821, 1839457) in 34 ms (iterations: 209869)
50bit, 769817083110377 , Factors: (13685611, 56250107) in 724 ms (iterations: 7222281)
60bit, 777571995069352537 , Factors: (427381733, 1819385189) in 27626 ms (iterations: 241583032)
70bit, 765702222853455251363,  Likely a larger jump in time because its past 64bits that fit into a `long`, so another path in BigInteger is used
80bit, 1105986106596451832095997,
fun benchmark(count: Int, task: () > Unit): Long {
val times = mutableListOf<Long>()
for (i in 0..count) {
val start = System.currentTimeMillis()
task.invoke()
if (i != 0) times.add(System.currentTimeMillis()  start)
}
return times.sum() / count
}
Some ideas for future performance enhancements:

Read existing publications on prime factorization, like the 'quadratic sieve' and 'general number field sieve'.

Use coroutines (multiple threads), but that's only a linear improvement

Create a custom
java.math.MutableBigInteger
.BigInteger
creates a copy on many operations. 
Find out exactly what operations are exponential and improve that
fun BigInteger.isSquare_ideas(): Boolean { // Idea 1: return this.sqrtAndRemainder()[1] == BigInteger.ZERO // Idea 2: // val bits = this.bitLength() // for (i in 0 until bits) { // if (this.testBit(i)) return false // } // return true // Idea 3: // return this.lowestSetBit == this.bitLength()  1 }
To learn more about Fermat's factorization method, see Wikipedia: https://en.wikipedia.org/wiki/Fermat%27s_factorization_method