I need a program written in C++ that implements Pollard\'s Rho algorithm for fac

Question

I need a program written in C++ that implements Pollard's Rho algorithm for factoring. The program should ask for the number (up to 30 digits) to factor, and return the answer as a product of two prime numbers.
Example, the factorization for (20 digit) number: 12219662220280190629 = 3367900313 * 3628273133.
Please Help!!

Note:Pollard’s Rho works as follows :

1. Choose an initial value x0 {1 . . . n 1}. Typically choose x0 = 2.
2. Choose a value c. Dene a polynomial f(x) = (x2 + c) %n. Typically use c = 1.
3. For i = 1 calculate xi = x1 = f(x0) and x2i = x2 = f(f(x0)).
4. gcd(|xi x2i|, n) gives a factor of n.
• If the factor is greater than 1 then you’ve found a factor.
• If the factor is 0 then Pollard’s Rho failed. Start with a new c. If you get 0 for multiple
values of c then n is probably prime.
• If the factor was 1, then go back to step (3) with i + 1. Then xi+1 = f(xi) and x2(i+1) = f(f(x2i)).

Example: a factor of n = 15049 = 101 * 149.

Explanation / Answer

#include #define max_iter 80 // number of iterations before trying a new K // this, I think, should be a factor of the size of n boolean isPrime(int n) { int n, i = 3, count, c; for ( count = 2 ; count

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.