4.1.18

Prime factorization using the smallest square root of a particular integer

If n is the product of two distinct odd primes p and q, then there are 4 square roots for each squared integer a such that GCD(a,n) = 1. There appears to be a relationship between the smallest square root of ((n+1)/2)^2 (mod n) and a multiple of p or q.

Conjecture 1.: Let n be the product of two distinct odd primes p and q. If s is the smallest square root of ((n+1)/2)^2 (mod n) then (n+1)/2 - s = rp such that GCD(rp, n) = p

Empirical evidence suggests that this conjecture holds for any n as long as n is the product of two distinct primes. In fact, the following algorithm can be used to factor n.

1. Calculate k = ((n+1)/2)^2 (mod n)

2. Find the smallest square root s of k mod n

3. Calculate xp = (n+1)/2 - s

4. Return GCD(xp, n)

Example:
a. Let n  = 35

1. k = 18^2 (mod 35) = 9
2. s = sqrt(9) = 3
3. xp = 18 - 3 = 15
4. GCD (15, 35) = 5

Step #2 can be further divided into two cases. The first case relates to k being a perfect square. If k is a perfect square then there is no need to use modular arithmetic to calculate the smallest square root of k. All known algorithms for computing the square root of a perfect square in Z will return the smallest square root of k. However, if k is not a perfect square in Z then finding its square root in Z_n becomes a different problem altogether.