## Knuth's version of Pollard's rho algorithm

In section 4.5.4 of Knuth's TAOCP, he gives this version of Pollard's famous "rho" algorithm in Algorithm B (page 385 of the 3rd edition); the variable "N" indicates the number to be factored (the input argument, if you like.) (Note that "%" below represents the modulo operator).

1. B1: Initialization:
• n ← N
• x ← 5
• x' ← 2
• k ← 1
• l ← 1
2. B2: Primality test
• If n is prime, output n and terminate.
3. B3: Factor found?
• g ← gcd(x' - x, n)
• if g == 1, go to B4
• if g == n, output "failed" and stop
• output g (note that if g is not prime, its factors will not be found by this method)
• n ← n / g
• x ← x % n
• x' ← x' % n
• Go to B2
• k ← k - 1
• if k == 0
• x' ← x
• l ← 2*l
• k ← l
• x ← (x*x + 1) % n
• Go to B3

## The details

Your assignment is to write programs implementing this function in C, Racket, and Gauche.

Your programs should be able to factor the following numbers on cop3353.org:

• 35
• 367756293167964701
• 2688307493077732358348134727
• 12902144921579660477018619711827

The programming languages that you are to use for the assignment are:

• C, using GMP. Please name this source file "kr.c".
• Gauche (/usr/bin/gosh), using math.prime. Please name this source file "kr.gosh"
• Racket (/usr/bin/racket), using math/number-theory. Please name this source file "kr.racket"

Your code must compile and run on the cop3353.org server (see last note for details about logging in.)

Note that Gauche and Racket are both dialects of Scheme; once you write your code in one, you can largely re-use the same code for the other.

Your output should look like the following (order of factors reported is not important, though this algorithm tends to be better at finding smaller factors):

```COP4020_test@cop3353:~% ./kr  35
Attempting to factor N = 35 with Pollard rho algorithm from Knuth's Algorithm B in section 4.5.4 of TAOCP
Factors are:
7
5
COP4020_test@cop3353:~% ./kr.gosh  35
Attempting to factor N = 35 with Pollard rho algorithm from Knuth's Algorithm B in section 4.5.4 of TAOCP
Factors are:
7
5
COP4020_test@cop3353:~% ./kr.racket  35
Attempting to factor N = 35 with Pollard rho algorithm from Knuth's Algorithm B in section 4.5.4 of TAOCP
Factors are:
7
5
COP4020_test@cop3353:~% ./kr  367756293167964701
Attempting to factor N = 367756293167964701 with Pollard rho algorithm from Knuth's Algorithm B in section 4.5.4 of TAOCP
Factors are:
7
11
13
107
101
103
109
3001
1009
COP4020_test@cop3353:~% ./kr.gosh  367756293167964701
Attempting to factor N = 367756293167964701 with Pollard rho algorithm from Knuth's Algorithm B in section 4.5.4 of TAOCP
Factors are:
7
11
13
107
101
103
109
3001
1009
COP4020_test@cop3353:~% ./kr.racket  367756293167964701
Attempting to factor N = 367756293167964701 with Pollard rho algorithm from Knuth's Algorithm B in section 4.5.4 of TAOCP
Factors are:
7
11
13
107
101
103
109
3001
1009
COP4020_test@cop3353:~% ./kr  2688307493077732358348134727
Attempting to factor N = 2688307493077732358348134727 with Pollard rho algorithm from Knuth's Algorithm B in section 4.5.4 of TAOCP
Factors are:
689816117
7688151521
506901611
COP4020_test@cop3353:~% ./kr.gosh  2688307493077732358348134727
Attempting to factor N = 2688307493077732358348134727 with Pollard rho algorithm from Knuth's Algorithm B in section 4.5.4 of TAOCP
Factors are:
689816117
7688151521
506901611
COP4020_test@cop3353:~% ./kr.racket  2688307493077732358348134727
Attempting to factor N = 2688307493077732358348134727 with Pollard rho algorithm from Knuth's Algorithm B in section 4.5.4 of TAOCP
Factors are:
689816117
7688151521
506901611
COP4020_test@cop3353:~% ./kr  12902144921579660477018619711827
Attempting to factor N = 12902144921579660477018619711827 with Pollard rho algorithm from Knuth's Algorithm B in section 4.5.4 of TAOCP
Factors are:
359195201
35919591591591616161427
COP4020_test@cop3353:~% ./kr.gosh  12902144921579660477018619711827
Attempting to factor N = 12902144921579660477018619711827 with Pollard rho algorithm from Knuth's Algorithm B in section 4.5.4 of TAOCP
Factors are:
359195201
35919591591591616161427
COP4020_test@cop3353:~% ./kr.racket  12902144921579660477018619711827
Attempting to factor N = 12902144921579660477018619711827 with Pollard rho algorithm from Knuth's Algorithm B in section 4.5.4 of TAOCP
Factors are:
359195201
35919591591591616161427

```

## Submission

There are separate submission links for each of these assignments. Please just turn in one file for each; for the C program, turn in your source file called "kr.c" and which should require the GMP library. For the Gauche version, turn in your source file called "kr.gosh". For the Racket version, turn in your source file called "kr.racket".

There are two possible due dates for this assignment. The first is the "extra credit deadline", which is 11:59pm on November 6th. For each successful program that you turn in by November 6th, you will receive 1 point of extra credit for the class.

The second deadline is the "regular credit deadline", which is 11:59pm on November 13th. The advantage to using this deadline is that on November 7th, I will discuss in some detail how to write all three of the versions.

Please note that I am allowing only one submission for each of these versions.

Since the Racket and Gauche interpreters on the linprog servers don't seem to have survived the migration from Gentoo to CentOS, you can find these on cop3353.org. To login into cop3353.org, you will need to use the private key matching the public key that you submitted for assignment one.