Documentation
¶
Overview ¶
Package dict implements dictionary and run-length addition chain algorithms.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
Types ¶
type Algorithm ¶
type Algorithm struct {
// contains filtered or unexported fields
}
Algorithm implements a general dictionary-based chain construction algorithm, as in [braueraddsubchains] Algorithm 1.26. This operates in three stages: decompose the target into a sum of dictionray terms, use a sequence algorithm to generate the dictionary, then construct the target from the dictionary terms.
func NewAlgorithm ¶
func NewAlgorithm(d Decomposer, a alg.SequenceAlgorithm) *Algorithm
NewAlgorithm builds a dictionary algorithm that breaks up integers using the decomposer d and uses the sequence algorithm s to generate dictionary entries.
func (Algorithm) FindChain ¶
FindChain builds an addition chain producing n. This works by using the configured Decomposer to represent n as a sum of dictionary terms, then delegating to the SequenceAlgorithm to build a chain producing the dictionary, and finally using the dictionary terms to construct n. See [genshortchains] Section 2 for a full description.
type Decomposer ¶
Decomposer is a method of breaking an integer into a dictionary sum.
type FixedWindow ¶
type FixedWindow struct {
K uint // Window size.
}
FixedWindow breaks integers into k-bit windows.
func (FixedWindow) Decompose ¶
func (w FixedWindow) Decompose(x *big.Int) Sum
Decompose represents x in terms of k-bit windows from left to right.
func (FixedWindow) String ¶
func (w FixedWindow) String() string
type Hybrid ¶
Hybrid is a mix of the sliding window and run length decomposition methods, similar to the "Hybrid Method" of [genshortchains] Section 3.3.
type RunLength ¶
type RunLength struct {
T uint // Maximal run length. Zero means no limit.
}
RunLength decomposes integers in to runs of 1s up to a maximal length. See [genshortchains] Section 3.1.
type RunsAlgorithm ¶
type RunsAlgorithm struct {
// contains filtered or unexported fields
}
RunsAlgorithm is a custom variant of the dictionary approach that decomposes a target into runs of ones. It leverages the observation that building a dictionary consisting of runs of 1s of lengths l₁, l₂, ..., l_k can itself be reduced to first finding an addition chain for the run lengths. Then from this chain we can build a chain for the runs themselves.
func NewRunsAlgorithm ¶
func NewRunsAlgorithm(a alg.SequenceAlgorithm) *RunsAlgorithm
NewRunsAlgorithm constructs a RunsAlgorithm using the given sequence algorithm to generate addition sequences for run lengths. Note that since run lengths are far smaller than the integers themselves, this sequence algorithm does not need to be able to handle large integers.
func (RunsAlgorithm) String ¶
func (a RunsAlgorithm) String() string
type SlidingWindow ¶
type SlidingWindow struct {
K uint // Window size.
}
SlidingWindow breaks integers into k-bit windows, skipping runs of zeros where possible. See [hehcc:exp] section 9.1.3 or [braueraddsubchains] section 1.2.3.
func (SlidingWindow) Decompose ¶
func (w SlidingWindow) Decompose(x *big.Int) Sum
Decompose represents x in base 2ᵏ.
func (SlidingWindow) String ¶
func (w SlidingWindow) String() string
type Sum ¶
type Sum []Term
Sum is the representation of an integer as a sum of dictionary terms. See [hehcc:exp] definition 9.34.
func (Sum) Dictionary ¶
Dictionary returns the distinct D values in the terms of this sum. The values are returned in ascending order.
func (Sum) SortByExponent ¶
func (s Sum) SortByExponent()
SortByExponent sorts terms in ascending order of the exponent E.
Source Files