Line data    Source code

       1             : /*************************************************************************
       2             :  *
       3             :  *  Project
       4             :  *                         _____ _____  __  __ _____
       5             :  *                        / ____|  __ \|  \/  |  __ \
       6             :  *  ___  _ __   ___ _ __ | |  __| |__) | \  / | |__) |
       7             :  * / _ \| '_ \ / _ \ '_ \| | |_ |  ___/| |\/| |  ___/
       8             :  *| (_) | |_) |  __/ | | | |__| | |    | |  | | |
       9             :  * \___/| .__/ \___|_| |_|\_____|_|    |_|  |_|_|
      10             :  *      | |
      11             :  *      |_|
      12             :  *
      13             :  * Copyright (C) Akiel Aries, <akiel@akiel.org>, et al.
      14             :  *
      15             :  * This software is licensed as described in the file LICENSE, which
      16             :  * you should have received as part of this distribution. The terms
      17             :  * among other details are referenced in the official documentation
      18             :  * seen here : https://akielaries.github.io/openGPMP/ along with
      19             :  * important files seen in this project.
      20             :  *
      21             :  * You may opt to use, copy, modify, merge, publish, distribute
      22             :  * and/or sell copies of the Software, and permit persons to whom
      23             :  * the Software is furnished to do so, under the terms of the
      24             :  * LICENSE file. As this is an Open Source effort, all implementations
      25             :  * must be of the same methodology.
      26             :  *
      27             :  *
      28             :  *
      29             :  * This software is distributed on an AS IS basis, WITHOUT
      30             :  * WARRANTY OF ANY KIND, either express or implied.
      31             :  *
      32             :  ************************************************************************/
      33             : 
      34             : /*
      35             :  * Some core concepts seen in Number Theory specifically
      36             :  * Integer Factorization
      37             :  */
      38             : #include <algorithm>
      39             : #include <chrono>
      40             : #include <cstdlib>
      41             : #include <cstring>
      42             : #include <future>
      43             : #include <iostream>
      44             : #include <numeric>
      45             : #include <openGPMP/arithmetic.hpp>
      46             : #include <openGPMP/nt/factorization.hpp>
      47             : #include <openGPMP/nt/prime_test.hpp>
      48             : #include <random>
      49             : #include <stdio.h>
      50             : #include <string>
      51             : #include <vector>
      52             : 
      53             : // declare Basics and Primality class objects
      54             : gpmp::Basics __FACT_BASICS__;
      55             : gpmp::Factorization __FACTOR__;
      56             : gpmp::PrimalityTest __FACT_PRIMES__;
      57             : 
      58             : // OSX uses srand() opposed to rand()
      59             : #ifdef __APPLE__
      60             : #define USE_SRAND
      61             : #endif
      62             : 
      63             : /*
      64             : std::vector<std::future<uint64_t>> gpmp::Factorization::pollard_rho_thread(
      65             :     const std::vector<uint64_t> &nums_to_factorize) {
      66             :     gpmp::ThreadPool pool(2);
      67             :     gpmp::Factorization factors;
      68             :     std::vector<std::future<uint64_t>> results;
      69             : 
      70             :     for (const auto &num : nums_to_factorize) {
      71             :         results.emplace_back(pool.enqueue(
      72             :             &gpmp::Factorization::pollard_rho, &factors, num));
      73             :     }
      74             : 
      75             :     return results;
      76             : }*/
      77             : 
      78           0 : uint64_t gpmp::Factorization::pollard_rho(uint64_t n) {
      79             :     /* initialize random seed */
      80             :     std::mt19937_64 rng(
      81           0 :         std::chrono::steady_clock::now().time_since_epoch().count());
      82             : 
      83             :     /* no prime divisor for 1 */
      84           0 :     if (n == 1) {
      85           0 :         return n;
      86             :     }
      87             : 
      88             :     /* even number means one of the divisors is 2 */
      89           0 :     if (n % 2 == 0) {
      90           0 :         return 2;
      91             :     }
      92             : 
      93             :     /* we will pick from the range [2, N) */
      94           0 :     std::uniform_int_distribution<uint64_t> unif_dist(2, n - 1);
      95           0 :     uint64_t x = unif_dist(rng);
      96           0 :     uint64_t y = x;
      97             : 
      98             :     /* the constant in f(x).
      99             :      * Algorithm can be re-run with a different c
     100             :      * if it throws failure for a composite. */
     101           0 :     std::uniform_int_distribution<uint64_t> c_dist(1, n - 1);
     102           0 :     uint64_t c = c_dist(rng);
     103             : 
     104             :     /* Initialize candidate divisor (or result) */
     105           0 :     uint64_t divisor = 1;
     106             : 
     107             :     /* until the prime factor isn't obtained.
     108             :        If n is prime, return n */
     109           0 :     while (divisor == 1) {
     110             :         /* Tortoise Move: x(i+1) = f(x(i)) */
     111           0 :         x = __FACT_PRIMES__.mod_pow(x, 2, n) + c;
     112           0 :         if (x >= n) {
     113           0 :             x -= n;
     114             :         }
     115             : 
     116             :         /* Hare Move: y(i+1) = f(f(y(i))) */
     117           0 :         y = __FACT_PRIMES__.mod_pow(y, 2, n) + c;
     118           0 :         if (y >= n) {
     119           0 :             y -= n;
     120             :         }
     121           0 :         y = __FACT_PRIMES__.mod_pow(y, 2, n) + c;
     122           0 :         if (y >= n) {
     123           0 :             y -= n;
     124             :         }
     125             : 
     126             :         /* check gcd of |x-y| and n */
     127           0 :         divisor = std::gcd(std::llabs(x - y), n);
     128             : 
     129             :         /* retry if the algorithm fails to find prime factor
     130             :          * with chosen x and c */
     131           0 :         if (divisor == n) {
     132           0 :             return pollard_rho(n);
     133             :         }
     134             :     }
     135             : 
     136           0 :     return divisor;
     137             : }