Addition chains API¶
Warning
In this version of Oraqle, the API is still prone to changes. Paths and names can change between any version.
The add_chains
module contains tools for generating addition chains.
add_chains
¶
Tools for generating addition chains using different constraints and objectives.
addition_chains
¶
Tools for generating short addition chains using a MaxSAT formulation.
thurber_bounds(target, max_size)
¶
Returns the Thurber bounds for a given target and a maximum size of the addition chain.
add_chain(target, max_depth, strict_cost_max, squaring_cost, solver, encoding, thurber, min_size, precomputed_values)
¶
Generates a minimumcost addition chain for a given target, abiding to the constraints.
Parameters:

target
(int
) –The target integer.

max_depth
(Optional[int]
) –The maximum depth of the addition chain

strict_cost_max
(float
) –A strict upper bound on the cost of the addition chain. I.e., cost(chain) < strict_cost_max.

squaring_cost
(float
) –The cost of doubling (squaring), compared to other additions (multiplications), which cost 1.0.

solver
(str
) –Name of the SAT solver, e.g. "glucose421" for glucose 4.2.1. See: https://pysathq.github.io/docs/html/api/solvers.html.

encoding
(int
) –The encoding to use for cardinality constraints. See: https://pysathq.github.io/docs/html/api/card.html#pysat.card.EncType.

thurber
(bool
) –Whether to use the Thurber bounds, which provide lower bounds for the elements in the chain. The bounds are ignored when
precomputed_values = True
. 
min_size
(int
) –The minimum size of the chain. It is always possible to use
math.ceil(math.log2(target))
. 
precomputed_values
(Optional[Tuple[Tuple[int, int], ...]]
) –If there are any precomputed values that can be used for free, they can be specified as a tuple of pairs (value, chain_depth).
Raises:

TimeoutError
–If the global MAXSAT_TIMEOUT is not None, and it is reached before a maxsat instance could be solved.
Returns:

Optional[List[Tuple[int, int]]]
–A minimumcost addition chain, if it exists.
addition_chains_front
¶
Tools for generating addition chains that trade off depth and cost.
addition_chains_heuristic
¶
This module contains functions for finding addition chains, while sometimes resorting to heuristics to prevent long computations.
add_chain_guaranteed(target, modulus, squaring_cost, solver='glucose421', encoding=1, thurber=True, precomputed_values=None)
cached
¶
Always generates an addition chain for a given target, which is suboptimal if the inputs are too large.
In some cases, the result is not necessarily optimal. These are the cases where we resort to a heuristic. This currently happens if:  The target exceeds 1000.  The modulus (if provided) exceeds 200.  MAXSAT_TIMEOUT is not None and a MaxSAT instance timed out
Note
This function is useful for preventing long computation, but the result is not guaranteed to be (close to) optimal.
Unlike add_chain
, this function will always return an addition chain.
Parameters:

target
(int
) –The target integer.

modulus
(Optional[int]
) –Modulus to take into account. In an exponentiation chain, this is the modulus in the exponent, i.e. x^target mod p corresponds to
modulus = p  1
. 
squaring_cost
(float
) –The cost of doubling (squaring), compared to other additions (multiplications), which cost 1.0.

solver
(str
, default:'glucose421'
) –Name of the SAT solver, e.g. "glucose421" for glucose 4.2.1. See: https://pysathq.github.io/docs/html/api/solvers.html.

encoding
(int
, default:1
) –The encoding to use for cardinality constraints. See: https://pysathq.github.io/docs/html/api/card.html#pysat.card.EncType.

thurber
(bool
, default:True
) –Whether to use the Thurber bounds, which provide lower bounds for the elements in the chain. The bounds are ignored when
precomputed_values = True
. 
precomputed_values
(Optional[Tuple[Tuple[int, int], ...]]
, default:None
) –If there are any precomputed values that can be used for free, they can be specified as a tuple of pairs (value, chain_depth).
Raises:

TimeoutError
–If the global MAXSAT_TIMEOUT is not None, and it is reached before a maxsat instance could be solved.
Returns:

List[Tuple[int, int]]
–An addition chain.
addition_chains_mod
¶
Tools for computing addition chains, taking into account the modular nature of the algebra.
hw(n)
¶
Returns the Hamming weight of n.
size_lower_bound(target)
¶
Returns a lower bound on the size of the addition chain for this target.
cost_lower_bound_monotonic(target, squaring_cost)
¶
Returns a lower bound on the cost of the addition chain for this target. The bound is guaranteed to grow monotonically with the target.
chain_cost(chain, squaring_cost)
¶
Returns the cost of the addition chain, considering doubling (squaring) to be cheaper than other additions (multiplications).
add_chain_modp(target, modulus, max_depth, strict_cost_max, squaring_cost, solver, encoding, thurber, min_size, precomputed_values=None)
¶
Computes an addition chain for target modulo p with the given constraints and optimization parameters.
The precomputed_powers are an optional set of powers that have previously been computed along with their depth. This means that those powers can be reused for free.
Returns:

Optional[List[Tuple[int, int]]]
–If it exists, a minimal addition chain meeting the given constraints and optimization parameters.
memoization
¶
This module contains tools for memoizing addition chains, as these are expensive to compute.
cache_to_disk(file_name, ignore_args)
¶
This decorator caches the calls to this function in a file on disk, ignoring the arguments listed in ignore_args
.
solving
¶
Tools for solving SAT formulations.
solve(wcnf, solver, strict_cost_max)
¶
This code is adapted from pysat's internal code to stop when we have reached a maximum cost.
Returns:

Optional[List[int]]
–A list containing the assignment (where 3 indicates that 3=True and 3 indicates that 3=False), or None if the wcnf is unsatisfiable.
extract_indices(sequence, precomputed_values=None, modulus=None)
¶
Returns the indices for each step of the addition chain.
If n precomputed values are provided, then these are considered to be the first n indices after x (i.e. x has index 0, followed by 1, ..., n representing the precomputed values).
solve_with_time_limit(wcnf, solver, strict_cost_max, timeout_secs)
¶
This code is adapted from pysat's internal code to stop when we have reached a maximum cost.
Raises:

TimeoutError
–When a timeout occurs (after
timeout_secs
seconds)
Returns:

Optional[List[int]]
–A list containing the assignment (where 3 indicates that 3=True and 3 indicates that 3=False), or None if the wcnf is unsatisfiable.