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             :  * Discrete Logarithms
      37             :  */
      38             : #include <algorithm>
      39             : #include <cmath>
      40             : #include <cstdlib>
      41             : #include <cstring>
      42             : #include <iostream>
      43             : #include <numeric>
      44             : #include <openGPMP/arithmetic.hpp>
      45             : #include <openGPMP/nt/logarithms.hpp>
      46             : #include <openGPMP/nt/prime_test.hpp>
      47             : #include <string>
      48             : #include <unordered_map>
      49             : 
      50             : // primes object for this Logarithms file
      51             : gpmp::PrimalityTest __LOG_PRIMES__;
      52             : 
      53             : // OSX uses srand() opposed to rand()
      54             : #ifdef __APPLE__
      55             : #define USE_SRAND
      56             : #endif
      57             : 
      58           0 : uint64_t gpmp::Logarithms::pollard_rho_log(uint64_t g, uint64_t y, uint64_t p) {
      59           0 :     uint64_t x = rand() % (p - 1) + 1;
      60             : 
      61             : #ifdef USE_SRAND
      62             :     srand(time(NULL));
      63             :     x = rand() % (p - 1) + 1;
      64             : #endif
      65             : 
      66           0 :     uint64_t y1 = y;
      67           0 :     uint64_t y2 = y;
      68           0 :     uint64_t d = 1;
      69           0 :     std::unordered_map<uint64_t, uint64_t> values;
      70             : 
      71             :     // Compute the iterated values of the sequence x_n = g^x_n-1 mod p
      72             :     // until a collision is found
      73           0 :     while (d == 1) {
      74           0 :         x = (x * x + 1) % p;
      75           0 :         y1 = (y1 * g) % p;
      76           0 :         y2 = (y2 * g) % p;
      77           0 :         y2 = (y2 * g) % p;
      78           0 :         d = std::gcd(std::llabs(y2 - y1), p);
      79           0 :         values[x] = y1;
      80             :     }
      81             : 
      82             :     // Compute the discrete logarithm using the collision point
      83           0 :     if (d == p) {
      84           0 :         return -1;
      85             :     } else {
      86           0 :         uint64_t x0 = std::llabs(y2 - y1) / d;
      87           0 :         uint64_t y0 = values[x0];
      88           0 :         uint64_t k = 1;
      89           0 :         while (y0 != y) {
      90           0 :             y0 = (y0 * g) % p;
      91           0 :             k++;
      92             :         }
      93           0 :         return k * x0 % (p - 1);
      94             :     }
      95           0 : }
      96             : 
      97             : /* Baby-Step Giant-Step */
      98           0 : uint64_t gpmp::Logarithms::BSGS(uint64_t a, uint64_t b, uint64_t m) {
      99           0 :     uint64_t n = (uint64_t)sqrt(m) + 1;
     100             : 
     101           0 :     std::unordered_map<uint64_t, uint64_t> value;
     102             : 
     103             :     // store all values of a^(n*i) of LHS
     104           0 :     for (uint64_t i = n; i >= 1; --i) {
     105           0 :         value[__LOG_PRIMES__.mod_pow(a, i * n, m)] = i;
     106             :     }
     107             : 
     108           0 :     for (uint64_t j = 0; j < n; ++j) {
     109             :         // calculate (a ^ j) * b and check
     110           0 :         uint64_t cur = (__LOG_PRIMES__.mod_pow(a, j, m) * b) % m;
     111             : 
     112             :         // If collision occurs i.e., LHS = RHS
     113           0 :         if (value[cur]) {
     114           0 :             uint64_t ans = value[cur] * n - j;
     115             :             // Check whether ans lies below m or not
     116           0 :             if (ans < m) {
     117           0 :                 return ans;
     118             :             }
     119             :         }
     120             :     }
     121           0 :     return -1;
     122           0 : }