mathtools/internal/lib/discreteLog.go

/*
Copyright © 2025 filifa

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package lib

import (
	"errors"
	"fmt"
	"math/big"
)

// whyyyy doesn't math/big have a ceil functionnnn
func ceilSqrt(x *big.Int) *big.Int {
	z := new(big.Int).Sqrt(x)
	s := new(big.Int).Exp(z, big.NewInt(2), nil)
	if s.Cmp(x) != 0 {
		z.Add(z, big.NewInt(1))
	}

	return z
}

/*
BabyStepGiantStep computes i such that b^i = x (mod n). For more efficient computation, provide the order of the group (i.e. totient(n)).
*/
func BabyStepGiantStep(n, b, x, order *big.Int) (*big.Int, error) {
	// TODO: this function be extended to work with n, b not coprime
	// https://cp-algorithms.com/algebra/discrete-log.html

	z := new(big.Int).GCD(nil, nil, b, n)
	if z.Cmp(big.NewInt(1)) != 0 {
		return nil, fmt.Errorf("base %v and modulus %v are not coprime", b, n)
	}

	var m *big.Int
	if order == nil {
		// m = ceil(sqrt(n - 1))
		z := big.NewInt(1)
		z.Sub(n, z)
		m = ceilSqrt(z)
	} else {
		m = ceilSqrt(order)
	}

	table := make(map[string]*big.Int)
	for j := big.NewInt(1); j.Cmp(m) <= 0; j.Add(j, big.NewInt(1)) {
		a := new(big.Int).Exp(b, j, n)
		table[a.String()] = new(big.Int).Set(j)
	}

	// p = b^-m modulo n
	p := new(big.Int).Neg(m)
	p.Exp(b, p, n)

	gamma := new(big.Int).Set(x)

	for i := big.NewInt(0); i.Cmp(m) == -1; i.Add(i, big.NewInt(1)) {
		j, ok := table[gamma.String()]
		if ok {
			i.Mul(i, m)
			i.Add(i, j)
			return i, nil
		}

		gamma.Mul(gamma, p)
		gamma.Mod(gamma, n)
	}

	return nil, errors.New("no solution")
}