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 minimum-cost 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 minimum-cost addition chain, if it exists.

addition_chains_front

Tools for generating addition chains that trade off depth and cost.

chain_depth(chain, precomputed_values=None, modulus=None)

Return the depth of the addition chain.

gen_pareto_front(target, modulus, squaring_cost, solver='glucose42', encoding=1, thurber=True, precomputed_values=None)

Returns a Pareto front of addition chains, trading of cost and depth.

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.