An application of Arbitrary precision: Pollard Rho and Euler Phi code

An application of our int_t arbitrary precision class is to implement a factoring algorithm known as Pollard Rho and use the factoring to produce the Euler Phi of n. The code is implemented in C++.

Pollard Rho is an earlier precursor to more advanced algorithms such as the Quadratic Sieve and Generalized Number Field Sieve. It has limitations on factoring 96 bit semi-primes, although it maybe able to factor larger numbers provided they are not semi-primes. A semi-prime is a number whose factors are two unique primes. These numbers play a significant role in modern cryptography algorithms such as the RSA algorithm.

The main function of Pollard Rho as implemented in our int_t class looks like the following:

```/* Copyright (c) 2017 ObjectSoftware.biz. All rights reserved. Presented under GPL v2. */
int_t rho(int_t N) {
int_t divisor;
int_t c  = N.getRand(N.getBitLength(N));
int_t x  = N.getRand(N.getBitLength(N));
int_t xx = x;

// check divisibility by 2
if ((N % int_t::TWO) == int_t::ZERO) return int_t::TWO;

do {
x  =  ((((x * x)  % N) + c) % N);
xx = ((((xx * xx) % N) + c) % N);
xx = ((((xx * xx) % N) + c) % N);
divisor = (x - xx).gcd(N);
} while(divisor == int_t::ONE);

return divisor;
}
```

Notice that we have implemented the gcd algorithm as well as most operators within the int_t class and this allows for the calculation to be implemented almost as if it was using a built-in type. Because int_t uses GMP underneath, the code is arbitrary precise. However, there are limitations in what can be computed in a reasonable time frame. The Pollard Rho algorithm works by selecting an integer for which the gcd with N is not one. And by doing so, it finds a factoring. Since this non-deterministic, its possible that the algorithm doesn’t find a factoring, or takes too long to find a factoring if N is large (since the factors would also be large and infrequently occurring in a number sequence.

Once we have a factoring, we can apply the definition of Euler Phi to compute the Totient function of N. The following is the code:

```/* Copyright (c) 2017 ObjectSoftware.biz. All rights reserved. Presented under GPL v2. */
int_t phi(int_t n)
{
mpf_t rtvl, one, fraction, sub;
mpf_init(rtvl);
mpf_init(one);
mpf_init(fraction);
mpf_init(sub);
mpf_set_ui(rtvl,1);
mpf_set_ui(one, 1);
mpf_set_ui(sub, 0);

set uniq;
for(list::iterator i = factors.begin();
i != factors.end(); ++i) {
if(uniq.find((*i)) == uniq.end()) {
uniq.insert((*i));
}
}
for(set::iterator i = uniq.begin();
i != uniq.end(); ++i) {
mpf_t tmp;
mpf_init(tmp);
const char *str = (*i).toString().c_str();
mpf_set_str(tmp,str,10);
mpf_div(fraction,one,tmp);
mpf_sub(sub,one,fraction);
mpf_mul(rtvl,rtvl,sub);
mpf_clear(tmp);
}
mp_exp_t exp;
char *tmp = new char[4096];
gmp_sprintf(tmp,"%.Ff",rtvl);
int_t r = compute(tmp,n);
delete[] tmp;
mpf_clear(rtvl);
mpf_clear(one);
mpf_clear(sub);
mpf_clear(fraction);
return r;
}
```

The Euler Phi algorithm above is:

Given a factoring of n
select uniq prime factors.
Then compute the product of 1-1/prime
for all prime factors of N, and
multiply the ratio by N.
The end result is Euler Phi

Notice that it is possible to factor N given Euler Phi of N; however, computing Euler Phi should be clear is as difficult as factoring N. Thus, one can not break algorithms such as RSA simply by computing Euler Phi of the modulus and applying the quadratic equation to solve because this is as hard as factoring N directly. Note that the above implementation of Euler Phi is much faster than the one given using trial division as Pollard Rho is faster than trial division for N up to about 96 bits, and subsequently calculating Euler Phi from N’s factors is faster than simply counting factors for N.

Please write to us for a complete implementation of the above. Thanks