Bitcoin Core  27.99.0 P2P Digital Currency
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

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 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 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 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 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: