Number-Theory-Utils/docs/polynomial_8h_source.html

#pragma once


#include <inttypes.h>

#include <stdlib.h>

#include <stdio.h>


#include <nut/modular_math.h>


typedef struct{

    uint64_t len;

    uint64_t cap;

    int64_t *coeffs;

} nut_Poly;


typedef struct{

    uint64_t len;

    uint64_t cap;

    int64_t *roots;

} nut_Roots;


NUT_ATTR_NODISCARD

NUT_ATTR_NONNULL(1)

NUT_ATTR_ACCESS(read_write, 1)

bool nut_Poly_init(nut_Poly *f, uint64_t reserve);


NUT_ATTR_NONNULL(1)

NUT_ATTR_ACCESS(read_write, 1)

void nut_Poly_destroy(nut_Poly *f);


NUT_ATTR_PURE

NUT_ATTR_NONNULL(1, 2)

NUT_ATTR_ACCESS(read_only, 1)

NUT_ATTR_ACCESS(read_only, 2)

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


NUT_ATTR_NODISCARD

NUT_ATTR_NONNULL(1)

NUT_ATTR_ACCESS(read_write, 1)

bool nut_Roots_init(nut_Roots *roots, uint64_t reserve);


NUT_ATTR_NONNULL(1)

NUT_ATTR_ACCESS(read_write, 1)

void nut_Roots_destroy(nut_Roots *roots);


NUT_ATTR_NODISCARD

NUT_ATTR_NONNULL(1)

NUT_ATTR_ACCESS(read_write, 1)

bool nut_Poly_ensure_cap(nut_Poly *f, uint64_t cap);


NUT_ATTR_NODISCARD

NUT_ATTR_NONNULL(1)

NUT_ATTR_ACCESS(read_write, 1)

bool nut_Poly_zero_extend(nut_Poly *f, uint64_t len);


NUT_ATTR_NODISCARD

NUT_ATTR_NONNULL(1)

NUT_ATTR_ACCESS(read_write, 1)

bool nut_Roots_ensure_cap(nut_Roots *roots, uint64_t cap);


NUT_ATTR_NONNULL(1)

NUT_ATTR_ACCESS(read_write, 1)

void nut_Poly_normalize(nut_Poly *f);


NUT_ATTR_NONNULL(1)

NUT_ATTR_ACCESS(read_write, 1)

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


NUT_ATTR_NONNULL(1)

NUT_ATTR_ACCESS(read_write, 1)

void nut_Poly_normalize_exps_modn(nut_Poly *f, uint64_t cn);


NUT_ATTR_NODISCARD

NUT_ATTR_NONNULL(1, 2)

NUT_ATTR_ACCESS(read_write, 1)

NUT_ATTR_ACCESS(read_only, 2)

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


NUT_ATTR_NODISCARD

NUT_ATTR_NONNULL(1)

NUT_ATTR_ACCESS(read_write, 1)

bool nut_Poly_setconst(nut_Poly *f, int64_t c);


NUT_ATTR_PURE

NUT_ATTR_NONNULL(1)

NUT_ATTR_ACCESS(read_only, 1)

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


NUT_ATTR_NONNULL(1, 2, 3, 4, 5, 6)

NUT_ATTR_ACCESS(read_write, 1)

NUT_ATTR_ACCESS(read_only, 2)

NUT_ATTR_ACCESS(read_only, 3)

NUT_ATTR_ACCESS(read_only, 4)

NUT_ATTR_ACCESS(read_only, 5)

NUT_ATTR_ACCESS(read_only, 6)

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);


NUT_ATTR_NONNULL(1, 2, 3)

NUT_ATTR_ACCESS(read_write, 1)

NUT_ATTR_ACCESS(write_only, 2)

NUT_ATTR_ACCESS(read_only, 3)

NUT_ATTR_ACCESS(write_only, 4)

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


NUT_ATTR_NONNULL(1)

NUT_ATTR_ACCESS(read_write, 1)

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


NUT_ATTR_NONNULL(1, 2, 3)

NUT_ATTR_ACCESS(read_write, 1)

NUT_ATTR_ACCESS(read_only, 2)

NUT_ATTR_ACCESS(read_only, 3)

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


NUT_ATTR_NONNULL(1, 2, 3)

NUT_ATTR_ACCESS(read_write, 1)

NUT_ATTR_ACCESS(read_only, 2)

NUT_ATTR_ACCESS(read_only, 3)

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


NUT_ATTR_NONNULL(1, 2, 3)

NUT_ATTR_ACCESS(read_write, 1)

NUT_ATTR_ACCESS(read_only, 2)

NUT_ATTR_ACCESS(read_only, 3)

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


NUT_ATTR_NONNULL(1, 2)

NUT_ATTR_ACCESS(read_write, 1)

NUT_ATTR_ACCESS(read_only, 2)

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


NUT_ATTR_NONNULL(1, 2, 3)

NUT_ATTR_ACCESS(read_write, 1)

NUT_ATTR_ACCESS(read_only, 2)

NUT_ATTR_ACCESS(read_only, 3)

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


NUT_ATTR_NONNULL(1, 2, 6)

NUT_ATTR_ACCESS(read_write, 1)

NUT_ATTR_ACCESS(read_only, 2)

NUT_ATTR_ACCESS(read_write, 6)

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]);


NUT_ATTR_NONNULL(1, 2)

NUT_ATTR_ACCESS(read_write, 1)

NUT_ATTR_ACCESS(read_only, 2)

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


NUT_ATTR_NONNULL(1, 2, 3, 6)

NUT_ATTR_ACCESS(read_write, 1)

NUT_ATTR_ACCESS(read_only, 2)

NUT_ATTR_ACCESS(read_only, 3)

NUT_ATTR_ACCESS(read_write, 6)

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]);


NUT_ATTR_NONNULL(1, 2, 3)

NUT_ATTR_ACCESS(read_write, 1)

NUT_ATTR_ACCESS(read_only, 2)

NUT_ATTR_ACCESS(read_only, 3)

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


NUT_ATTR_NONNULL(1, 2, 3, 4)

NUT_ATTR_ACCESS(read_write, 1)

NUT_ATTR_ACCESS(read_write, 2)

NUT_ATTR_ACCESS(read_only, 3)

NUT_ATTR_ACCESS(read_only, 4)

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);


//TODO: use arrays for temporaries instead of single pointers, maybe provide a nut_Poly[1] typedef as is tradition

NUT_ATTR_NONNULL(1, 2, 3, 5)

NUT_ATTR_ACCESS(read_write, 1)

NUT_ATTR_ACCESS(read_only, 2)

NUT_ATTR_ACCESS(read_only, 3)

NUT_ATTR_ACCESS(read_write, 5)

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]);


NUT_ATTR_NONNULL(1, 2, 3)

NUT_ATTR_ACCESS(read_write, 1)

NUT_ATTR_ACCESS(read_only, 2)

NUT_ATTR_ACCESS(read_only, 3)

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


NUT_ATTR_NONNULL(1, 2, 4, 6)

NUT_ATTR_ACCESS(read_write, 1)

NUT_ATTR_ACCESS(read_only, 2)

NUT_ATTR_ACCESS(read_only, 4)

NUT_ATTR_ACCESS(read_write, 6)

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]);


NUT_ATTR_NONNULL(1, 2, 4)

NUT_ATTR_ACCESS(read_write, 1)

NUT_ATTR_ACCESS(read_only, 2)

NUT_ATTR_ACCESS(read_only, 4)

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);


NUT_ATTR_NONNULL(1, 2, 5)

NUT_ATTR_ACCESS(read_write, 1)

NUT_ATTR_ACCESS(read_only, 2)

NUT_ATTR_ACCESS(read_write, 5)

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]);


NUT_ATTR_NONNULL(1, 2, 5)

NUT_ATTR_ACCESS(read_write, 1)

NUT_ATTR_ACCESS(read_only, 2)

NUT_ATTR_ACCESS(read_write, 5)

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]);


NUT_ATTR_NONNULL(1, 3, 4)

NUT_ATTR_ACCESS(read_only, 1)

NUT_ATTR_ACCESS(read_write, 3)

NUT_ATTR_ACCESS(read_write, 4)

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


NUT_ATTR_NONNULL(1, 3)

NUT_ATTR_ACCESS(read_only, 1)

NUT_ATTR_ACCESS(read_write, 3)

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


modular_math.h

NUT_ATTR_ACCESS
#define NUT_ATTR_ACCESS(...)
Wrapper for gcc's access function annotation - no clang equivalent, and currently disabled because it...
Definition modular_math.h:40

NUT_ATTR_NONNULL
#define NUT_ATTR_NONNULL(...)
Wrapper for gnu::nonnull attr.
Definition modular_math.h:75

NUT_ATTR_NODISCARD
#define NUT_ATTR_NODISCARD
Wrapper for nodiscard attr - requires return value be used.
Definition modular_math.h:68

NUT_ATTR_PURE
#define NUT_ATTR_PURE
Wrapper for gnu::pure attr - similar to const but the function can read non-volatile memory (includin...
Definition modular_math.h:61

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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.

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

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

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.

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)

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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

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

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.

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

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).

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.

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.

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.

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.

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

nut_Poly
A polynomial with signed integer coefficients.
Definition polynomial.h:26

nut_Poly::cap
uint64_t cap
Maximum length polynomial the coeffs buffer can currently store.
Definition polynomial.h:31

nut_Poly::len
uint64_t len
Length of the polynomial.
Definition polynomial.h:29

nut_Poly::coeffs
int64_t * coeffs
Array of coefficients.
Definition polynomial.h:34

nut_Roots
The roots of a polynomial over a finite field, ignoring multiplicity.
Definition polynomial.h:38

nut_Roots::roots
int64_t * roots
Array of roots.
Definition polynomial.h:45

nut_Roots::len
uint64_t len
Number of roots, can be 0 if there are none.
Definition polynomial.h:40

nut_Roots::cap
uint64_t cap
Maximum number of roots the roots buffer can currently store.
Definition polynomial.h:42