gpmp::Logarithms Class Reference

#include <logarithms.hpp>

Public Member Functions
uint64_t	pollard_rho_log (uint64_t a, uint64_t b, uint64_t m)
uint64_t	BSGS (uint64_t a, uint64_t b, uint64_t m)

Detailed Description

Examples

logarithms.cpp.

Definition at line 47 of file logarithms.hpp.

Member Function Documentation

BSGS()

uint64_t gpmp::Logarithms::BSGS	(	uint64_t	a,
		uint64_t	b,
		uint64_t	m
	)

Examples

logarithms.cpp.

Definition at line 98 of file logarithms.cpp.

                                                                {
    uint64_t n = (uint64_t)sqrt(m) + 1;
 
    std::unordered_map<uint64_t, uint64_t> value;
 
    // store all values of a^(n*i) of LHS
    for (uint64_t i = n; i >= 1; --i) {
        value[__LOG_PRIMES__.mod_pow(a, i * n, m)] = i;
    }
 
    for (uint64_t j = 0; j < n; ++j) {
        // calculate (a ^ j) * b and check
        uint64_t cur = (__LOG_PRIMES__.mod_pow(a, j, m) * b) % m;
 
        // If collision occurs i.e., LHS = RHS
        if (value[cur]) {
            uint64_t ans = value[cur] * n - j;
            // Check whether ans lies below m or not
            if (ans < m) {
                return ans;
            }
        }
    }
    return -1;
}

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

Referenced by main().

pollard_rho_log()

uint64_t gpmp::Logarithms::pollard_rho_log	(	uint64_t	a,
		uint64_t	b,
		uint64_t	m
	)

Examples

logarithms.cpp.

Definition at line 58 of file logarithms.cpp.

                                                                           {
    uint64_t x = rand() % (p - 1) + 1;
 
#ifdef USE_SRAND
    srand(time(NULL));
    x = rand() % (p - 1) + 1;
#endif
 
    uint64_t y1 = y;
    uint64_t y2 = y;
    uint64_t d = 1;
    std::unordered_map<uint64_t, uint64_t> values;
 
    // Compute the iterated values of the sequence x_n = g^x_n-1 mod p
    // until a collision is found
    while (d == 1) {
        x = (x * x + 1) % p;
        y1 = (y1 * g) % p;
        y2 = (y2 * g) % p;
        y2 = (y2 * g) % p;
        d = std::gcd(std::llabs(y2 - y1), p);
        values[x] = y1;
    }
 
    // Compute the discrete logarithm using the collision point
    if (d == p) {
        return -1;
    } else {
        uint64_t x0 = std::llabs(y2 - y1) / d;
        uint64_t y0 = values[x0];
        uint64_t k = 1;
        while (y0 != y) {
            y0 = (y0 * g) % p;
            k++;
        }
        return k * x0 % (p - 1);
    }
}

Referenced by main().

---

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

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