gpmp::Factorization Class Reference

#include <factorization.hpp>

Public Member Functions
uint64_t	pollard_rho (uint64_t n)

Detailed Description

Examples

factors.cpp.

Definition at line 46 of file factorization.hpp.

Member Function Documentation

pollard_rho()

uint64_t gpmp::Factorization::pollard_rho

(

uint64_t

n

)

Examples

factors.cpp.

Definition at line 78 of file factorization.cpp.

                                                  {
    /* initialize random seed */
    std::mt19937_64 rng(
        std::chrono::steady_clock::now().time_since_epoch().count());
 
    /* 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) */
    std::uniform_int_distribution<uint64_t> unif_dist(2, n - 1);
    uint64_t x = unif_dist(rng);
    uint64_t y = x;
 
    /* the constant in f(x).
     * Algorithm can be re-run with a different c
     * if it throws failure for a composite. */
    std::uniform_int_distribution<uint64_t> c_dist(1, n - 1);
    uint64_t c = c_dist(rng);
 
    /* Initialize candidate divisor (or result) */
    uint64_t divisor = 1;
 
    /* until the prime factor isn't obtained.
       If n is prime, return n */
    while (divisor == 1) {
        /* Tortoise Move: x(i+1) = f(x(i)) */
        x = __FACT_PRIMES__.mod_pow(x, 2, n) + c;
        if (x >= n) {
            x -= n;
        }
 
        /* Hare Move: y(i+1) = f(f(y(i))) */
        y = __FACT_PRIMES__.mod_pow(y, 2, n) + c;
        if (y >= n) {
            y -= n;
        }
        y = __FACT_PRIMES__.mod_pow(y, 2, n) + c;
        if (y >= n) {
            y -= n;
        }
 
        /* check gcd of |x-y| and n */
        divisor = std::gcd(std::llabs(x - y), n);
 
        /* retry if the algorithm fails to find prime factor
         * with chosen x and c */
        if (divisor == n) {
            return pollard_rho(n);
        }
    }
 
    return divisor;
}

References __FACT_PRIMES__, and gpmp::PrimalityTest::mod_pow().

Referenced by main().

---

The documentation for this class was generated from the following files:

• include/openGPMP/nt/factorization.hpp
• modules/nt/factorization.cpp