sketch_impl.h File Reference

#include <random>
#include "util.h"
#include "sketch.h"
#include "int_utils.h"

Include dependency graph for sketch_impl.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	SketchImpl< F >

Functions
template<typename F >
void	PolyMod (const std::vector< typename F::Elem > &mod, std::vector< typename F::Elem > &val, const F &field)
	Compute the remainder of a polynomial division of val by mod, putting the result in mod. More...
template<typename F >
void	DivMod (const std::vector< typename F::Elem > &mod, std::vector< typename F::Elem > &val, std::vector< typename F::Elem > &div, const F &field)
	Compute the quotient of a polynomial division of val by mod, putting the quotient in div and the remainder in val. More...
template<typename F >
F::Elem	MakeMonic (std::vector< typename F::Elem > &a, const F &field)
	Make a polynomial monic. More...
template<typename F >
void	GCD (std::vector< typename F::Elem > &a, std::vector< typename F::Elem > &b, const F &field)
	Compute the GCD of two polynomials, putting the result in a. More...
template<typename F >
void	Sqr (std::vector< typename F::Elem > &poly, const F &field)
	Square a polynomial. More...
template<typename F >
void	TraceMod (const std::vector< typename F::Elem > &mod, std::vector< typename F::Elem > &out, const typename F::Elem &param, const F &field)
	Compute the trace map of (param*x) modulo mod, putting the result in out. More...
template<typename F >
bool	RecFindRoots (std::vector< std::vector< typename F::Elem >> &stack, size_t pos, std::vector< typename F::Elem > &roots, bool fully_factorizable, int depth, typename F::Elem randv, const F &field)
	One step of the root finding algorithm; finds roots of stack[pos] and adds them to roots. More...
template<typename F >
std::vector< typename F::Elem >	FindRoots (const std::vector< typename F::Elem > &poly, typename F::Elem basis, const F &field)
	Returns the roots of a fully factorizable polynomial. More...
template<typename F >
std::vector< typename F::Elem >	BerlekampMassey (const std::vector< typename F::Elem > &syndromes, size_t max_degree, const F &field)
template<typename F >
std::vector< typename F::Elem >	ReconstructAllSyndromes (const std::vector< typename F::Elem > &odd_syndromes, const F &field)
template<typename F >
void	AddToOddSyndromes (std::vector< typename F::Elem > &osyndromes, typename F::Elem data, const F &field)
template<typename F >
std::vector< typename F::Elem >	FullDecode (const std::vector< typename F::Elem > &osyndromes, const F &field)

Function Documentation

AddToOddSyndromes()

template<typename F >

void AddToOddSyndromes	(	std::vector< typename F::Elem > &	osyndromes,
		typename F::Elem	data,
		const F &	field
	)

Definition at line 336 of file sketch_impl.h.

Here is the caller graph for this function:

BerlekampMassey()

template<typename F >

std::vector<typename F::Elem> BerlekampMassey	(	const std::vector< typename F::Elem > &	syndromes,
		size_t	max_degree,
		const F &	field
	)

Definition at line 281 of file sketch_impl.h.

Here is the caller graph for this function:

DivMod()

template<typename F >

void DivMod	(	const std::vector< typename F::Elem > &	mod,
		std::vector< typename F::Elem > &	val,
		std::vector< typename F::Elem > &	div,
		const F &	field
	)

Compute the quotient of a polynomial division of val by mod, putting the quotient in div and the remainder in val.

Definition at line 38 of file sketch_impl.h.

Here is the caller graph for this function:

FindRoots()

template<typename F >

std::vector<typename F::Elem> FindRoots	(	const std::vector< typename F::Elem > &	poly,
		typename F::Elem	basis,
		const F &	field
	)

Returns the roots of a fully factorizable polynomial.

This function assumes that the input polynomial is square-free and not the zero polynomial (represented by an empty vector).

In case the square-free polynomial is not fully factorizable, i.e., it has fewer roots than its degree, the empty vector is returned.

Definition at line 263 of file sketch_impl.h.

Here is the call graph for this function:

Here is the caller graph for this function:

FullDecode()

template<typename F >

std::vector<typename F::Elem> FullDecode	(	const std::vector< typename F::Elem > &	osyndromes,
		const F &	field
	)

Definition at line 346 of file sketch_impl.h.

Here is the call graph for this function:

GCD()

template<typename F >

void GCD	(	std::vector< typename F::Elem > &	a,
		std::vector< typename F::Elem > &	b,
		const F &	field
	)

Compute the GCD of two polynomials, putting the result in a.

b will be cleared.

Definition at line 76 of file sketch_impl.h.

Here is the call graph for this function:

Here is the caller graph for this function:

MakeMonic()

template<typename F >

F::Elem MakeMonic	(	std::vector< typename F::Elem > &	a,
		const F &	field
	)

Make a polynomial monic.

Definition at line 62 of file sketch_impl.h.

Here is the caller graph for this function:

PolyMod()

template<typename F >

void PolyMod	(	const std::vector< typename F::Elem > &	mod,
		std::vector< typename F::Elem > &	val,
		const F &	field
	)

Compute the remainder of a polynomial division of val by mod, putting the result in mod.

Definition at line 18 of file sketch_impl.h.

Here is the caller graph for this function:

RecFindRoots()

template<typename F >

bool RecFindRoots	(	std::vector< std::vector< typename F::Elem >> &	stack,
		size_t	pos,
		std::vector< typename F::Elem > &	roots,
		bool	fully_factorizable,
		int	depth,
		typename F::Elem	randv,
		const F &	field
	)

One step of the root finding algorithm; finds roots of stack[pos] and adds them to roots.

Stack elements >= pos are destroyed.

It operates on a stack of polynomials. The polynomial operated on is stack[pos], where elements of stack with index higher than pos are used as scratch space.

stack[pos] is assumed to be square-free polynomial. If fully_factorizable is true, it is also assumed to have no irreducible factors of degree higher than 1.

This implements the Berlekamp trace algorithm, plus an efficient test to fail fast in case the polynomial cannot be fully factored.

Definition at line 128 of file sketch_impl.h.

Here is the call graph for this function:

Here is the caller graph for this function:

ReconstructAllSyndromes()

template<typename F >

std::vector<typename F::Elem> ReconstructAllSyndromes	(	const std::vector< typename F::Elem > &	odd_syndromes,
		const F &	field
	)

Definition at line 325 of file sketch_impl.h.

Here is the caller graph for this function:

Sqr()

template<typename F >

void Sqr	(	std::vector< typename F::Elem > &	poly,
		const F &	field
	)

Square a polynomial.

Definition at line 92 of file sketch_impl.h.

Here is the caller graph for this function:

TraceMod()

template<typename F >

void TraceMod	(	const std::vector< typename F::Elem > &	mod,
		std::vector< typename F::Elem > &	out,
		const typename F::Elem &	param,
		const F &	field
	)

Compute the trace map of (param*x) modulo mod, putting the result in out.

Definition at line 102 of file sketch_impl.h.

Here is the call graph for this function:

Here is the caller graph for this function: