Question

Suppose we modified the Pollard rho method, so the iteration would be f(x) = x^2 mod n instead of f(x) = x^2 + 2 mod n. How well would it perform, and why? (You are encouraged to try some moderately large examples using a computer.)

Answer 1

Given a positive integer n, and that it is composite, find a divisor of it.

Example:

Input: n = 12;
Output: 2 [OR 3 OR 4]

Input: n = 187;
Output: 11 [OR 17]

Brute approach: Test all integers less than n until a divisor is found.
Improvisation: Test all integers less than √n

A large enough number will still mean a great deal of work. Pollard’s Rho is a prime factorization algorithm, particularly fast for a large composite number with small prime factors. The Rho algorithm’s most remarkable success was the factorization

1. wo numbers x and y are said to be congruent modulo n (x = y modulo n) if
   1. their absolute difference is an integer multiple of n, OR,
   2. each of them leaves the same remainder when divided by n.
2. The Greatest Common Divisor is the largest number which divides evenly into each of the original numbers.
3. Birthday Paradox: The probability of two persons having same birthday is unexpectedly high even for small set of people.
4. Floyd’s cycle-finding algorithm: If tortoise and hare start at same point and move in a cycle such that speed of hare is twice the speed of tortoise, then they must meet at some point.

C++ program to find a prime factor of composite using    Pollard's Rho algorithm */ #include<bits/stdc++.h> using namespace std;    /* Function to calculate (base^exponent)%modulus */ long long int modular_pow(long long int base, int exponent,                           long long int modulus) {     /* initialize result */     long long int result = 1;        while (exponent > 0)     {         /* if y is odd, multiply base with result */         if (exponent & 1)             result = (result * base) % modulus;            /* exponent = exponent/2 */         exponent = exponent >> 1;            /* base = base * base */         base = (base * base) % modulus;     }     return result; }    /* method to return prime divisor for n */ long long int PollardRho(long long int n) {     /* initialize random seed */     srand (time(NULL));        /* no prime divisor for 1 */     if (n==1) return n;        /* even number means one of the divisors is 2 */     if (n % 2 == 0) return 2;        /* we will pick from the range [2, N) */     long long int x = (rand()%(n-2))+2;     long long int y = x;        /* the constant in f(x).      * Algorithm can be re-run with a different c      * if it throws failure for a composite. */     long long int c = (rand()%(n-1))+1;        /* Initialize candidate divisor (or result) */     long long int d = 1;          /* until the prime factor isn't obtained.        If n is prime, return n */     while (d==1)     {         /* Tortoise Move: x(i+1) = f(x(i)) */         x = (modular_pow(x, 2, n) + c + n)%n;            /* Hare Move: y(i+1) = f(f(y(i))) */         y = (modular_pow(y, 2, n) + c + n)%n;         y = (modular_pow(y, 2, n) + c + n)%n;            /* check gcd of |x-y| and n */         d = __gcd(abs(x-y), n);            /* retry if the algorithm fails to find prime factor          * with chosen x and c */         if (d==n) return PollardRho(n);     }        return d; }    /* driver function */ int main() {     long long int n = 10967535067;     printf("One of the divisors for %lld is %lld.",           n, PollardRho(n));     return 0; }

chevron_right

filter_none

Output: