I found a simple algorithm for factoring semiprime numbers, you can read about it in Factoring Semiprimes and Possible Implications for RSA.
It basically works like this:
You reverse the digits in $N$, let's call this value $Ň$
You pick an integer, $k$ (normally 1, but can be other values)
A variable, $Δ$, can be any integer value between the square root of $N$ and the square root of $Ň$
You then calculate four values, if any return a value other than 1, then you have one of your prime factors:
- $gcd[N, (k × Ň) + Δ]$
- $gcd[N, (k × Ň) - Δ]$
- $gcd[N, (Δ × Ň) + k]$
- $gcd[N, (Δ × Ň) - k]$
Using this algorithm and the GMP library, it would factor 18014417929109603 in 3 seconds.
I was wondering if there were any other algorithms which were faster than this, but just as easy to implement? I know the GNFS is the fastest, but it is also incredibly hard to implement.