[Back] Pollard's rho algorithm can be used to factorize a number into its factors:

## Pollard's rho algorithm |

## Method

Many problems in public key encryption derive the security strength from the difficulity in factorizing a number into its prime number elements. In RSA, if we can factorize the modulus (N) into its prime numbers (\(p\) and \(q\)), and can easily crack the cipher. The Pollard's rho algorithm can be used to factorize integers, and was iinvented by John Pollard in 1975. Its main advantage is that it only requires a small amount of memory. Also its run time is proportional to the square root of the smallest prime factor. The basic algorithm takes a value (\(n\)) and a function \(g(x)\) and which is a polynomial in \(x\) computed modulo \(n\). Normally \(g(x)=(x^{2}+1) \pmod {n}\). A basic algorithm is:

package main import ( "fmt" "strconv" "os" ) func g(x,p int) int { return (x*x +1) % p } func gcd(x, y int) int { for y != 0 { x, y = y, x%y } return x } func abs(x int) int { if (x<0) { return -x } return x } func main() { x := 2 y := 2 d := 1 n:=8051 i:=1 argCount := len(os.Args[1:]) if (argCount>0) { n,_= strconv.Atoi(os.Args[1])} fmt.Printf("i\tx\ty\n-------------------\n") for d == 1 { fmt.Printf("%d\t%d\t%d\n",i,x,y) x = g(x,n) y = g(g(y,n),n) d = gcd(abs(x-y), n) i=i+1 } fmt.Printf("\n%d=%dx%d",n,d,p/d) }

A sample run is:

i x y ------------------- 1 2 2 2 5 26 3 26 7474 8051=97x83