4neurons logo

This algorithm uses following property of modulus: a²≡b² (mod n) and a≠-b (mod n) → GCD(n,|a-b|)>1

If a²b² (mod n) and GCD(n,|a-b|)>1 and GCD(n,|a-b|)≠n then we've found a factor.
It's not easy to find such a and b. However I found (out of ceiling) an algorithm that work quite well for small n...
Let c=a2 mod n then (a2)2 mod n = c2 mod n
Knowing that "(a∙b) ≡ (a∙(b mod c)) (mod c)" we'll get:
c∙a2≡a4 (mod n)
thus:
(√c∙a)2≡a4 (mod n)
If √c belongs to N then GCD(n,a2-√c∙a) is very likely to be factor of n (unless it is equal n itself)
But for this to work we need to find such a that a2 mod n have natural squareroot. This seems to be troubleful.
I used following algorithm:

1. a = (floor of √n) + 1
2. c = a2 mod n
3. if √c belongs to N then we probably found a factor - return GCD(n,a2-√c*a)
   else increase a by one and goto step 2

This seemed to work for small numbers, but not for large ones. After short analysis I discovered quickly that √c belongs to N when a=(p+q)/2. For small numbers it is likely to be near √n. But average difference (p+q)/2-√n of randomly chosen p,q grows exponentially to the number of digits of n. In fact this algorithm's search area is exactly the same as for Pitagoras-Factorize algorithm. (There we assumed p+q≈2√n, here (p+q)/2≈√n)


Code