Detailed Description

Author: hacatu

Version: 0.2.0

LICENSE

This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/.

DESCRIPTION

Functions for dealing with polynomials with integer coefficients, especially over finite fields.

Definition in file polynomial.h.

Go to the source code of this file.

Data Structures
struct	nut_Poly
	A polynomial with signed integer coefficients. More...

struct	nut_Roots
	The roots of a polynomial over a finite field, ignoring multiplicity. More...

Functions
NUT_ATTR_NODISCARD bool	nut_Poly_init (nut_Poly *f, uint64_t reserve)
	Initialize a polynomial with at least a given capacity.

void	nut_Poly_destroy (nut_Poly *f)
	Free resources held by a polynomial struct.

NUT_ATTR_PURE int	nut_Poly_cmp (const nut_Poly a, const nut_Poly b)
	Asymptotically compare polynomials.

NUT_ATTR_NODISCARD bool	nut_Roots_init (nut_Roots *roots, uint64_t reserve)
	Initialize a root buffer with at least a given capacity.

void	nut_Roots_destroy (nut_Roots *roots)
	Free resources held by a root buffer.

NUT_ATTR_NODISCARD bool	nut_Poly_ensure_cap (nut_Poly *f, uint64_t cap)
	Extend the capacity of a polynomial struct if needed.

NUT_ATTR_NODISCARD bool	nut_Poly_zero_extend (nut_Poly *f, uint64_t len)
	Extend the capacity of a polynomial struct if needed and set any new terms to 0.

NUT_ATTR_NODISCARD bool	nut_Roots_ensure_cap (nut_Roots *roots, uint64_t cap)
	Extend the capacity of a root buffer if needed.

void	nut_Poly_normalize (nut_Poly *f)
	Strip off terms so the leading term is nonzero if needed.

void	nut_Poly_normalize_modn (nut_Poly *f, int64_t n, bool use_negatives)
	Reduce coefficients mod n, then normalize.

void	nut_Poly_normalize_exps_modn (nut_Poly *f, uint64_t cn)
	Reduce any exponents over cn.

NUT_ATTR_NODISCARD bool	nut_Poly_copy (nut_Poly restrict g, const nut_Poly restrict f)
	Copy a polynomial.

NUT_ATTR_NODISCARD bool	nut_Poly_setconst (nut_Poly *f, int64_t c)
	Set a polynomial to a constant (linear terms and up zero).

NUT_ATTR_PURE int64_t	nut_Poly_eval_modn (const nut_Poly *f, int64_t x, int64_t n)
	Evaluate a polynomial mod a number.

int	nut_Poly_fprint (FILE restrict file, const nut_Poly restrict f, const char vname, const char add, const char sub, const char pow, bool descending)
	Print a polynomial to a file.

int	nut_Poly_parse (nut_Poly restrict f, int64_t restrict n, const char restrict str, const char restrict *restrict end)
	Convert a string to a polynomial (and possibly modulus)

bool	nut_Poly_rand_modn (nut_Poly *f, uint64_t max_len, int64_t n)
	Generate a random polynomial.

bool	nut_Poly_add_modn (nut_Poly h, const nut_Poly f, const nut_Poly *g, int64_t n)
	Add polynomials f + g mod n and store the result in h.

bool	nut_Poly_sub_modn (nut_Poly h, const nut_Poly f, const nut_Poly *g, int64_t n)
	Subtract polynomials f - g mod n and store the result in h.

bool	nut_Poly_dot_modn (nut_Poly h, const nut_Poly f, const nut_Poly *g, int64_t n)
	Take the termwise product of polynomials f and g mod n and store the result in h.

bool	nut_Poly_scale_modn (nut_Poly g, const nut_Poly f, int64_t a, int64_t n)
	Multiply a polynomial f by a scalar a and store the result in h.

bool	nut_Poly_mul_modn (nut_Poly restrict h, const nut_Poly f, const nut_Poly *g, int64_t n)
	Multiply polynomials f*g mod n and store the result in h.

bool	nut_Poly_pow_modn (nut_Poly restrict g, const nut_Poly restrict f, uint64_t e, int64_t n, uint64_t cn, nut_Poly tmps[restrict static 2])
	Raise f**x mod n and store the result in g.

bool	nut_Poly_pow_modn_tmptmp (nut_Poly restrict g, const nut_Poly restrict f, uint64_t e, int64_t n, uint64_t cn)
	Raise f**x mod n and store the result in g.

bool	nut_Poly_compose_modn (nut_Poly restrict h, const nut_Poly f, const nut_Poly *g, int64_t n, uint64_t cn, nut_Poly tmps[restrict static 2])
	Compose polynomial f(g(x)) mod n and store the result in h.

bool	nut_Poly_compose_modn_tmptmp (nut_Poly restrict h, const nut_Poly f, const nut_Poly *g, int64_t n, uint64_t cn)
	Compose polynomial f(g(x)) mod n and store the result in h.

bool	nut_Poly_quotrem_modn (nut_Poly restrict q, nut_Poly restrict r, const nut_Poly restrict f, const nut_Poly restrict g, int64_t n)
	Divide two polynomials to get a quotient and remainder.

bool	nut_Poly_gcd_modn (nut_Poly restrict d, const nut_Poly restrict f, const nut_Poly *restrict g, int64_t n, nut_Poly tmps[restrict static 3])
	Find the gcd of two polynomials.

bool	nut_Poly_gcd_modn_tmptmp (nut_Poly restrict d, const nut_Poly restrict f, const nut_Poly *restrict g, int64_t n)
	Find the gcd of two polynomials.

bool	nut_Poly_powmod_modn (nut_Poly restrict h, const nut_Poly restrict f, uint64_t e, const nut_Poly *restrict g, int64_t n, nut_Poly tmps[restrict static 3])
	Compute the power of a polynomial mod another polynomial.

bool	nut_Poly_powmod_modn_tmptmp (nut_Poly restrict h, const nut_Poly restrict f, uint64_t e, const nut_Poly *restrict g, int64_t n)
	Compute the power of a polynomial mod another polynomial.

bool	nut_Poly_factors_d_modn (nut_Poly restrict f_d, const nut_Poly restrict f, uint64_t d, int64_t n, nut_Poly tmps[restrict static 4])
	Compute the product of all irreducible factors of degree d.

bool	nut_Poly_factor1_modn (nut_Poly restrict g, const nut_Poly restrict f, uint64_t d, int64_t n, nut_Poly tmps[restrict static 4])
	Attempt to find a divisor of f_d.

bool	nut_Poly_roots_modn (const nut_Poly restrict f, int64_t n, nut_Roots restrict roots, nut_Poly tmps[restrict static 6])
	Find all roots of a polynomial in an odd prime field.

bool	nut_Poly_roots_modn_tmptmp (const nut_Poly restrict f, int64_t n, nut_Roots restrict roots)
	Find all roots of a polynomial in an odd prime field.

Function Documentation

◆ nut_Poly_init()

NUT_ATTR_NODISCARD bool nut_Poly_init	(	nut_Poly *	f,
		uint64_t	reserve
	)

Initialize a polynomial with at least a given capacity.

If the given capacity is 0, it defaults to 4. The polynomial is set to the zero polynomial.

Parameters

[out]	f	polynomial to initialize
[in]	reserve	initial capacity, defaults to 4 if 0 is given

Returns: 1 on success, 0 on failure

◆ nut_Poly_destroy()

void nut_Poly_destroy ( nut_Poly * f )

Free resources held by a polynomial struct.

Parameters

[in,out] f polynomial to destroy

◆ nut_Poly_cmp()

NUT_ATTR_PURE int nut_Poly_cmp	(	const nut_Poly *	a,
		const nut_Poly *	b
	)

Asymptotically compare polynomials.

Does not assume the inputs are normalized. Finds the highest degree term without matching coefficients.

Parameters

[in] a,b polynomials to compare

Returns: -1 if a < b, 1 if a > b, 0 if a == b

◆ nut_Roots_init()

NUT_ATTR_NODISCARD bool nut_Roots_init	(	nut_Roots *	roots,
		uint64_t	reserve
	)

Initialize a root buffer with at least a given capacity.

If the given capacity is 0, it defaults to 4. The list will be empty (len=0).

Parameters

[out]	roots	root buffer to initialize.
[in]	reserve	initial capacity, defaults to 4 if 0 is given

Returns: 1 on success, 0 on failure

◆ nut_Roots_destroy()

void nut_Roots_destroy ( nut_Roots * roots )

Free resources held by a root buffer.

Parameters

[in,out] roots root buffer to destroy

◆ nut_Poly_ensure_cap()

NUT_ATTR_NODISCARD bool nut_Poly_ensure_cap	(	nut_Poly *	f,
		uint64_t	cap
	)

Extend the capacity of a polynomial struct if needed.

Generally called at the beginning of most functions.

Parameters

[in,out]	f	polynomial to extend
[in]	cap	minimum capacity the polynomial should have aferwards

Returns: 1 on success, 0 on failure

◆ nut_Poly_zero_extend()

NUT_ATTR_NODISCARD bool nut_Poly_zero_extend	(	nut_Poly *	f,
		uint64_t	len
	)

Extend the capacity of a polynomial struct if needed and set any new terms to 0.

Parameters

[in,out]	f	polynomial to extend
[in]	len	length to extend poly to

Returns: 1 on success, 0 on failure

◆ nut_Roots_ensure_cap()

NUT_ATTR_NODISCARD bool nut_Roots_ensure_cap	(	nut_Roots *	roots,
		uint64_t	cap
	)

Extend the capacity of a root buffer if needed.

Called by nut_Poly_roots_modn and nut_Poly_roots_modn_tmptmp.

Parameters

[in,out]	roots	root buffer to extend
[in]	cap	minimum capacity the root buffer should have aferwards

Returns: 1 on success, 0 on failure

◆ nut_Poly_normalize()

void nut_Poly_normalize ( nut_Poly * f )

Strip off terms so the leading term is nonzero if needed.

Generally called at the end of most functions.

Parameters

[in,out] f polynomial to normalize

◆ nut_Poly_normalize_modn()

void nut_Poly_normalize_modn	(	nut_Poly *	f,
		int64_t	n,
		bool	use_negatives
	)

Reduce coefficients mod n, then normalize.

Parameters

[in,out]	f	polynomial to normalize
[in]	n	modulus to reduce coefficients by
[in]	use_negatives	if false, coefficients will be in the range [0,n), otherwise [(1-n)/2,n/2)

◆ nut_Poly_normalize_exps_modn()

void nut_Poly_normalize_exps_modn	(	nut_Poly *	f,
		uint64_t	cn
	)

Reduce any exponents over cn.

Generally called by functions that take a cn (carmichael lambda function of n) argument Remove any term x**(k*cn + a) where 0 < a <= cn and add its coefficient to term x**a

◆ nut_Poly_copy()

NUT_ATTR_NODISCARD bool nut_Poly_copy	(	nut_Poly *restrict	g,
		const nut_Poly *restrict	f
	)

Copy a polynomial.

Parameters

[out]	g	destination
[in]	f	source

Returns: 1 on success, 0 on failure

◆ nut_Poly_setconst()

NUT_ATTR_NODISCARD bool nut_Poly_setconst	(	nut_Poly *	f,
		int64_t	c
	)

Set a polynomial to a constant (linear terms and up zero).

Parameters

[out]	f	polynomial to set to constant
[in]	c	constant to set polynomial to

Returns: 1 on success, 0 on failure

◆ nut_Poly_eval_modn()

NUT_ATTR_PURE int64_t nut_Poly_eval_modn	(	const nut_Poly *	f,
		int64_t	x,
		int64_t	n
	)

Evaluate a polynomial mod a number.

Uses a Horner scheme with modulus taken after every multiply/add step.

Parameters

[in]	f	polynomial to evaluate
[in]	x	point at which to evaluate
[in]	n	modulus for the result

Returns: f(x) mod n

◆ nut_Poly_fprint()

int nut_Poly_fprint	(	FILE *restrict	file,
		const nut_Poly *restrict	f,
		const char *	vname,
		const char *	add,
		const char *	sub,
		const char *	pow,
		bool	descending
	)

Print a polynomial to a file.

Skips zero terms, coefficients of 1 or -1, powers of 0 or 1, and any leading plus sign. Thus the the format is "x^2 + 2x + 1". The zero polynomial is displayed as "0", and a leading negative sign is always displayed as "-" with no trailing space.

Parameters

[in,out]	file	file to write to
[in]	f	polynomial to print
[in]	vname	string to use for variable, eg "x"
[in]	add	string to use for adding two monomials together, eg "+" or " + "
[in]	sub	string to use for subtracting two monomials, eg "-" or " - "
[in]	pow	string to use for exponents, eg "" for "x2" or "^" for "x^2"
[in]	descending	if true, print higher terms down to lower terms, otherwise print lower terms up to higher terms (Taylor Series order)

Returns: the total number of characters printed

◆ nut_Poly_parse()

int nut_Poly_parse	(	nut_Poly *restrict	f,
		int64_t *restrict	n,
		const char *restrict	str,
		const char restrict restrict	end
	)

Convert a string to a polynomial (and possibly modulus)

Ignores whitespace, ignores variable names, allows multiplication signs, duplicate terms, and duplicate minus signs. The format is poly = monomial (+|- monomial)* ("mod" \d+)? monomial = -* ((coeff *? vpow) | coeff | vpow) coeff = \d+ vpow = \w (("**"|"^") \d+)?

Parameters

[out]	f	polynomial to store output in
[out]	n	pointer to store modulus n in if found
[in]	str	string to parse
[out]	end	pointer to store end of parsed content (first unparsed character, ie typically '\0')

Returns: 0 on failure, 1 if polynomial was parsed without modulus, 2 if both polynomial and modulus were parsed

◆ nut_Poly_rand_modn()

bool nut_Poly_rand_modn	(	nut_Poly *	f,
		uint64_t	max_len,
		int64_t	n
	)

Generate a random polynomial.

Coefficients are integers chosen uniformly on [0,n). max_len are chosen and then the polynomial is normalized (nut_Poly_normalize). So max_len minus the actual length has bounded geometric distribution with success probability 1/n.

Parameters

[out]	f	polynomial to randomize
[in]	max_len	number of coefficients to generate before normalizing. If 0, the output polynomial is always set to zero
[in]	n	modulus for coefficients

Returns: 1 on succes, 0 on failure

◆ nut_Poly_add_modn()

bool nut_Poly_add_modn	(	nut_Poly *	h,
		const nut_Poly *	f,
		const nut_Poly *	g,
		int64_t	n
	)

Add polynomials f + g mod n and store the result in h.

Parameters

[out]	h	polynomial in which to store the sum
[in]	f,g	polynomials to add
[in]	n	modulus to reduce result by

Returns: 1 on success, 0 on failure

◆ nut_Poly_sub_modn()

bool nut_Poly_sub_modn	(	nut_Poly *	h,
		const nut_Poly *	f,
		const nut_Poly *	g,
		int64_t	n
	)

Subtract polynomials f - g mod n and store the result in h.

Parameters

[out]	h	polynomial in which to store the difference f - g mod n
[in]	f,g	polynomials to subtract
[in]	n	modulus to reduce result by

Returns: 1 on success, 0 on failure

◆ nut_Poly_dot_modn()

bool nut_Poly_dot_modn	(	nut_Poly *	h,
		const nut_Poly *	f,
		const nut_Poly *	g,
		int64_t	n
	)

Take the termwise product of polynomials f and g mod n and store the result in h.

Parameters

[out]	h	polynomial in which to store the result
[in]	f,g	polynomials to multiply termwise
[in]	n	modulus to reduce result by

Returns: 1 on success, 0 on failure

◆ nut_Poly_scale_modn()

bool nut_Poly_scale_modn	(	nut_Poly *	g,
		const nut_Poly *	f,
		int64_t	a,
		int64_t	n
	)

Multiply a polynomial f by a scalar a and store the result in h.

Parameters

[out]	g	polynomial in which to store a*f mod n
[in]	f	polynomial to multiply by a scalar
[in]	a	scalar to multiply by
[in]	n	modulus to reduce result by

Returns: 1 on success, 0 on failure

◆ nut_Poly_mul_modn()

bool nut_Poly_mul_modn	(	nut_Poly *restrict	h,
		const nut_Poly *	f,
		const nut_Poly *	g,
		int64_t	n
	)

Multiply polynomials f*g mod n and store the result in h.

Uses the basic algorithm

Parameters

[out]	h	polynomial in which to store f*g mod n
[in]	f,g	polynomials to multiply
[in]	n	modulus to reduce result by

Returns: 1 on success, 0 on failure

◆ nut_Poly_pow_modn()

bool nut_Poly_pow_modn	(	nut_Poly *restrict	g,
		const nut_Poly *restrict	f,
		uint64_t	e,
		int64_t	n,
		uint64_t	cn,
		nut_Poly	tmps[restrict static 2]
	)

Raise f**x mod n and store the result in g.

Parameters

[out]	g	polynomial in which to store f**x
[in]	f	polynomial to find a power of
[in]	e	exponent to raise f to
[in]	n	modulus to reduce result by
[in]	cn	carmichael lambda function of n, basically modulus for exponents, see `carmichael_lambda` and `nut_sieve_carmichael`
[in]	tmps	polynomial for scratch work, must have 1 initialized (or at least zeroed out) polynomial (`nut_Poly_pow_modn_tmptmp`)

Returns: 1 on success, 0 on failure

◆ nut_Poly_pow_modn_tmptmp()

bool nut_Poly_pow_modn_tmptmp	(	nut_Poly *restrict	g,
		const nut_Poly *restrict	f,
		uint64_t	e,
		int64_t	n,
		uint64_t	cn
	)

Raise f**x mod n and store the result in g.

Like nut_Poly_pow_modn except temporary polynomials are allocated and freed internally instead of using supplied temporaries.

Parameters

[out]	g	polynomial in which to store f**x
[in]	f	polynomial to find a power of
[in]	e	exponent to raise f to
[in]	n	modulus to reduce result by
[in]	cn	carmichael lambda function of n, basically modulus for exponents, see `carmichael_lambda` and `nut_sieve_carmichael`

Returns: 1 on success, 0 on failure

◆ nut_Poly_compose_modn()

bool nut_Poly_compose_modn	(	nut_Poly *restrict	h,
		const nut_Poly *	f,
		const nut_Poly *	g,
		int64_t	n,
		uint64_t	cn,
		nut_Poly	tmps[restrict static 2]
	)

Compose polynomial f(g(x)) mod n and store the result in h.

Parameters

[out]	h	polynomial in which to store f(g(x)) mod n
[in]	f,g	polynomials to compose
[in]	n	modulus to reduce result by
[in]	cn	carmichael lambda function of n, basically modulus for exponents, see `carmichael_lambda` and `nut_sieve_carmichael`
[in]	tmps	polynomial for scratch work, must have 1 initialized (or at least zeroed out) polynomial (`nut_Poly_compose_modn_tmptmp`)

Returns: 1 on success, 0 on failure

◆ nut_Poly_compose_modn_tmptmp()

bool nut_Poly_compose_modn_tmptmp	(	nut_Poly *restrict	h,
		const nut_Poly *	f,
		const nut_Poly *	g,
		int64_t	n,
		uint64_t	cn
	)

Compose polynomial f(g(x)) mod n and store the result in h.

Like nut_Poly_compose_modn except temporary polynomials are allocated and freed internally instead of using supplied temporaries.

Parameters

[out]	h	polynomial in which to store f(g(x)) mod n
[in]	f,g	polynomials to compose
[in]	n	modulus to reduce result by
[in]	cn	carmichael lambda function of n, basically modulus for exponents, see `carmichael_lambda` and `nut_sieve_carmichael`

Returns: 1 on success, 0 on failure

◆ nut_Poly_quotrem_modn()

bool nut_Poly_quotrem_modn	(	nut_Poly *restrict	q,
		nut_Poly *restrict	r,
		const nut_Poly *restrict	f,
		const nut_Poly *restrict	g,
		int64_t	n
	)

Divide two polynomials to get a quotient and remainder.

f = q*g + r mod n. Uses extended synthetic division. Note that while weaker forms of polynomial division can be defined for weaker forms of rings than fields, the synthetic division algorithm can fail if the coefficient ring is not a field because division by the leading coefficient might fail. Even if n is composite, if the leading coefficient of the divisor is 1 then this algorithm will not fail, otherwise, this function fails.

Parameters

[out]	q,r	polynomials in which to store the quotient and remainder such that f = q*g + r mod n
[in]	f,g	polynomials to divide
[in]	n	modulus to reduce result by

Returns: 1 on success, 0 on failure. Can fail if the leading cofficient of g is not invertable mod n, as well as on allocation failure

◆ nut_Poly_gcd_modn()

bool nut_Poly_gcd_modn	(	nut_Poly *restrict	d,
		const nut_Poly *restrict	f,
		const nut_Poly *restrict	g,
		int64_t	n,
		nut_Poly	tmps[restrict static 3]
	)

Find the gcd of two polynomials.

The gcd is reduced to be monic, so if n is not prime this can fail. If d = gcd(f, g), then there is some pair of polynomials a and b so that f = ad and g = bd (d is a common divisor), and for any other common divisor h, d = ch for some polynomial c (d is greatest because it has at least as high degree as any other common divisor. Note that in the integers, we have two choices for gcd, which are associates (meaning one is the negative of the other) and we pick the positive one by convention. Similarly for polynomials with coefficients from a field, the the gcd is not unique and any associate of the gcd is also a gcd. Thus we restrict the gcd to be monic.

Parameters

[out]	d	polynomial in which to store the monic gcd, or store 0 if both f and n are 0
[in]	f,g	polynomials to take the gcd of
[in]	n	modulus for the coefficient ring
[in]	tmps	polynomials for scratch work, cannot be NULL (`nut_Poly_gcd_modn_tmptmp`)

Returns: 1 on success, 0 on failure. Can fail if a non-invertable leading coefficient is encountered, as well as on allocation failure.

◆ nut_Poly_gcd_modn_tmptmp()

bool nut_Poly_gcd_modn_tmptmp	(	nut_Poly *restrict	d,
		const nut_Poly *restrict	f,
		const nut_Poly *restrict	g,
		int64_t	n
	)

Find the gcd of two polynomials.

Like nut_Poly_gcd_modn except temporary polynomials are allocated and freed internally instead of using supplied temporaries. Less efficient because early checking is not done.

Parameters

[out]	d	polynomial in which to store the monic gcd, or store 0 if both f and n are 0
[in]	f,g	polynomials to take the gcd of
[in]	n	modulus for the coefficient ring

Returns: 1 on success, 0 on failure. Can fail if a non-invertable leading coefficient is encountered, as well as on allocation failure.

◆ nut_Poly_powmod_modn()

bool nut_Poly_powmod_modn	(	nut_Poly *restrict	h,
		const nut_Poly *restrict	f,
		uint64_t	e,
		const nut_Poly *restrict	g,
		int64_t	n,
		nut_Poly	tmps[restrict static 3]
	)

Compute the power of a polynomial mod another polynomial.

Uses binary exponentiation. The coefficients themselves are in the cyclic group Z_n as usual.

Parameters

[out]	h	polynomial in which to store the result
[in]	f	base
[in]	e	exponent
[in]	g	modulus
[in]	n	coefficient modulus
[in]	tmps	polynomials for scratch work, must have 3 initialized (or at least zeroed out) polynomials (`nut_Poly_powmod_modn_tmptmp`)

Returns: 1 on success, 0 on failure. Can fail if a non-invertable leading coefficient is encountered, as well as on allocation failure.

◆ nut_Poly_powmod_modn_tmptmp()

bool nut_Poly_powmod_modn_tmptmp	(	nut_Poly *restrict	h,
		const nut_Poly *restrict	f,
		uint64_t	e,
		const nut_Poly *restrict	g,
		int64_t	n
	)

Compute the power of a polynomial mod another polynomial.

Like nut_Poly_powmod_modn except temporary polynomials are allocated and freed internally instead of using supplied temporaries. Less efficient because early checking is not done.

Parameters

[out]	h	polynomial in which to store the result
[in]	f	base
[in]	e	exponent
[in]	g	modulus
[in]	n	coefficient modulus

Returns: 1 on success, 0 on failure. Can fail if a non-invertable leading coefficient is encountered, as well as on allocation failure.

◆ nut_Poly_factors_d_modn()

bool nut_Poly_factors_d_modn	(	nut_Poly *restrict	f_d,
		const nut_Poly *restrict	f,
		uint64_t	d,
		int64_t	n,
		nut_Poly	tmps[restrict static 4]
	)

Compute the product of all irreducible factors of degree d.

This should be called repeatedly on squarefree factors, or else it will extract repeat factors for d > 1. Thus if we only want roots in the field Z_p, or equivalently we only want linear factors, we can call this function without bothering to make f squarefree first. In the general case, getting the squarefree factorization of f is easy: any repeated root of f (in Z_p or indeed the splitting field of f) is also a root of f' the derivative of f, so we can say the squarefree part of f is f / gcd(f, f'). We can repeat this to find polynomials representing roots which occur exactly once (f / gcd(f, f')), roots which occur exactly twice (sqrt(gcd(f, f') / gcd(f, f''))), roots which occur exactly thrice (cbrt(gcd(f, f'') / gcd(f, f'''))), etc. Eventually, these quotients will saturate and just become 1 forever. If f is already squarefree, let f_i be the product of all irreducible factors of f with degree i. Then we have f_1 = gcd(x^p-x, f), f_2 = gcd(x^(p^2), f/f_1), f_3 = gcd(x^(p^3), f/f_1/f_2), etc. Once the expression f/f_1/f_2/.../f_i becomes 1, we are done. This clearly takes at most k steps, where k is the degree of f. It is possible to show an irreducible f is irreducible by only showing it has no factors of degree k/q for any prime divisor q, ie f | x^(p^k) but gcd(f, x^(p^(k/q))) = 1 for all q. This function only takes care of computing gcd(x^(p^d)-x, f/f_1/.../f_(d-1)) given p, d, and f/f_1/.../f_(d-1).

Parameters

[out]	f_d	the product of all degree d irreducible factors of f
[in]	f	the polynomial to factor, which should be squarefree and have no irreducible factors with degree less than d
[in]	d	the degree of irreducible factors to extract. Note that f should be free from irreducible factors with lower degree, so once d exceeds half the degree of f, f must be irreducible.
[in]	n	coefficient modulus. MUST be prime.
[in]	tmps	polynomials for scratch work, must have 4 initialized (or at least zeroed out) polynomials

Returns: 1 on success, 0 on failure

◆ nut_Poly_factor1_modn()

bool nut_Poly_factor1_modn	(	nut_Poly *restrict	g,
		const nut_Poly *restrict	f,
		uint64_t	d,
		int64_t	n,
		nut_Poly	tmps[restrict static 4]
	)

Attempt to find a divisor of f_d.

Given a squarefree polynomial f whose irreducible factors all have degree d, if f has degree k which is greater than d (it must be a multiple of d) it must split. Mod an odd prime p, we can find a nontrivial factor of f by 1) choosing a random r with degree less than k (if gcd(r, f) isn't 1 we are done), 2) computing s = r^((p^d-1)/2) mod f, 3) gcd(s + 1, f) is a nontrivial factor with probability greater than 1/2. This works because not only does x^(p^d)-x factor as x(x^((p^d-1)/2)-1)(x^((p^d-1)/2)+1), this holds if we replace x with any polynomial. If a factor isn't contained in the first term, it has about a 1/2 chance of being contained in the second term, hence this algorithm. This function returns a single nontrivial factor g, and both g and f/g may need to be factored further if they are not degree d. Note that if f is degree 2 with irreducible factors of degree 1, completing the square/using the quadratic formula is faster, although for such small polynomials this is unimportant.

Parameters

[out]	g	a nontrivial factor of f. Both g and f/g could potentially need to be factored further with more calls to this method.
[in]	f	the polynomial to factor, which should be squarefree and have multiple irreducible factors of degree d
[in]	d	the degree of irreducible factors of f
[in]	n	coefficient modulus. MUST be prime.
[in]	tmps	polynomials for scratch work, must have 4 initialized (or at least zeroed out) polynomials

Returns: 1 on success, 0 on failure

◆ nut_Poly_roots_modn()

bool nut_Poly_roots_modn	(	const nut_Poly *restrict	f,
		int64_t	n,
		nut_Roots *restrict	roots,
		nut_Poly	tmps[restrict static 6]
	)

Find all roots of a polynomial in an odd prime field.

Uses the Cantor-Zassenhaus algorithm, specialized for linear factors (so we can skip squarefree factorization). This is implemented in the functions nut_Poly_factors_d_modn and nut_Poly_factor1_modn. After the first function, we know how many roots there are and allocate a buffer. The second function is called as many times as needed to find all the roots. TODO: optimize factoring quadratics using quadratic formula.

Parameters

[in]	f	polynomial to find roots of
[in]	n	modulus of the coefficient field. MUST be prime.
[out]	roots	store roots here.
[in]	tmps	polynomials for scratch work, must have 6 initialized (or at least zeroed out) polynomials (`nut_Poly_roots_modn_tmptmp`)

Returns: 1 on success (including if the polynomial has 0 roots), 0 on failure.

◆ nut_Poly_roots_modn_tmptmp()

bool nut_Poly_roots_modn_tmptmp	(	const nut_Poly *restrict	f,
		int64_t	n,
		nut_Roots *restrict	roots
	)

Find all roots of a polynomial in an odd prime field.

Like nut_Poly_roots_modn except temporary polynomials are allocated and freed internally instead of using supplied temporaries.

Parameters

[in]	f	polynomial to find roots of
[in]	n	modulus of the coefficient field. MUST be prime.
[out]	roots	store roots here.

Returns: 1 on success (including if the polynomial has 0 roots), 0 on failure.

Detailed Description

LICENSE

DESCRIPTION

Data Structures

Functions

Function Documentation

◆ nut_Poly_init()

◆ nut_Poly_destroy()

◆ nut_Poly_cmp()

◆ nut_Roots_init()

◆ nut_Roots_destroy()

◆ nut_Poly_ensure_cap()

◆ nut_Poly_zero_extend()

◆ nut_Roots_ensure_cap()

◆ nut_Poly_normalize()

◆ nut_Poly_normalize_modn()

◆ nut_Poly_normalize_exps_modn()

◆ nut_Poly_copy()

◆ nut_Poly_setconst()

◆ nut_Poly_eval_modn()

◆ nut_Poly_fprint()

◆ nut_Poly_parse()

◆ nut_Poly_rand_modn()

◆ nut_Poly_add_modn()

◆ nut_Poly_sub_modn()

◆ nut_Poly_dot_modn()

◆ nut_Poly_scale_modn()

◆ nut_Poly_mul_modn()

◆ nut_Poly_pow_modn()

◆ nut_Poly_pow_modn_tmptmp()

◆ nut_Poly_compose_modn()

◆ nut_Poly_compose_modn_tmptmp()

◆ nut_Poly_quotrem_modn()

◆ nut_Poly_gcd_modn()

◆ nut_Poly_gcd_modn_tmptmp()

◆ nut_Poly_powmod_modn()

◆ nut_Poly_powmod_modn_tmptmp()

◆ nut_Poly_factors_d_modn()

◆ nut_Poly_factor1_modn()

◆ nut_Poly_roots_modn()

◆ nut_Poly_roots_modn_tmptmp()