dlog.h File Reference

Algorithms for computing discrete logarithms. More...

Go to the source code of this file.

Functions
cfe_error	cfe_baby_giant (mpz_t res, mpz_t h, mpz_t g, mpz_t p, mpz_t order, mpz_t bound)
	Baby-step giant-step method for computing the discrete logarithm in the Zp group. More...
cfe_error	cfe_baby_giant_with_neg (mpz_t res, mpz_t h, mpz_t g, mpz_t p, mpz_t _order, mpz_t bound)
	Baby-step giant-step method for computing the discrete logarithm in the Zp group finding also negative solutions. More...
cfe_error	cfe_pollard_rho (mpz_t res, mpz_t h, mpz_t g, mpz_t p, mpz_t n)
	Pollard's rho algorithm - simple, non-parallel version. More...
cfe_error	cfe_baby_giant_FP12_BN256_with_neg (mpz_t res, FP12_BN254 *h, FP12_BN254 *g, mpz_t bound)
	Baby-step giant-step method for computing the discrete logarithm in the pairing group FP12_BN254 finding also negative solutions. More...

Detailed Description

Algorithms for computing discrete logarithms.

FE schemes instantiated from the Discrete Diffie-Hellman assumption (DDH) all rely on efficient algorithms for calculating discrete logarithms.

Function Documentation

cfe_baby_giant()

cfe_error cfe_baby_giant	(	mpz_t	res,
		mpz_t	h,
		mpz_t	g,
		mpz_t	p,
		mpz_t	order,
		mpz_t	bound
	)

Baby-step giant-step method for computing the discrete logarithm in the Zp group.

It searches for a solution <= bound. If bound argument is nil, the bound is automatically set to p-1. The function returns x, where h = g^x mod p. If the solution was not found within the provided bound, it returns an error.

Parameters

res	Discrete logarithm (the result value placeholder)
h	Element
g	Generator
p	Modulus
order	Order
bound	Bound for solution

Returns

Error code

cfe_baby_giant_with_neg()

cfe_error cfe_baby_giant_with_neg	(	mpz_t	res,
		mpz_t	h,
		mpz_t	g,
		mpz_t	p,
		mpz_t	_order,
		mpz_t	bound
	)

Baby-step giant-step method for computing the discrete logarithm in the Zp group finding also negative solutions.

It searches for a solution (-bound, bound). If bound argument is nil, the bound is automatically set to p-1 and it works identically than function baby_step_giant_step. The function returns x, where h = g^x mod p. If the solution was not found within the provided bound, it returns an error.

Parameters

res	Discrete logarithm (the result value placeholder)
h	Element
g	Generator
p	Modulus
_order	Order
bound	Bound for solution

Returns

Error code

cfe_pollard_rho()

cfe_error cfe_pollard_rho	(	mpz_t	res,
		mpz_t	h,
		mpz_t	g,
		mpz_t	p,
		mpz_t	n
	)

Pollard's rho algorithm - simple, non-parallel version.

Parameters

res	Discrete logarithm (the result value placeholder)
h	Element
g	Generator
p	Modulus
n	Order

Returns

Error code

cfe_baby_giant_FP12_BN256_with_neg()

cfe_error cfe_baby_giant_FP12_BN256_with_neg	(	mpz_t	res,
		FP12_BN254 *	h,
		FP12_BN254 *	g,
		mpz_t	bound
	)

Baby-step giant-step method for computing the discrete logarithm in the pairing group FP12_BN254 finding also negative solutions.

It searches for a solution (-bound, bound). The function returns x, where h = g^x in the group. If the solution was not found within the provided bound, it returns an error.

Parameters

res	Discrete logarithm (the result value placeholder)
h	Element
g	Generator
bound	Bound for solution

Returns

Error code