fhelium.experimental.bootstrap.polynomial

Polynomial approximations and encrypted evaluation schedules.

BalancedPowerEvaluator

class View source

BalancedPowerEvaluator(skip_near_zero: float = 0.0)

Evaluate a power series through a shared balanced product tree.

To construct $x^n$, the evaluator recursively multiplies $x^{\lfloor n/2\rfloor }$ by $x^{\lceil n/2\rceil }$. Every exponent is cached for one call, so terms share intermediate ciphertexts. Terms are depth-aligned using a basis scale recurrence anchored at the input. Each active coefficient multiplication consumes one final depth.

evaluate consumes a two-component coefficient-domain, standard-RNS Q ciphertext representing the basis coordinate $x$. Its dense payload axes are [component, *batch, limb, coefficient]; all batch members share depth, scale, and prime_ids. The method is functional. Each ciphertext product converts operands to NTT/Montgomery form, multiplies to three components, relinearizes back to two coefficient-domain standard components, and rescales by the complete Q group product while retaining actual scale. The final result is coefficient-domain standard RNS over Q at ciphertext.depth + required_depths(polynomial), with the corresponding prime_ids, unchanged batch shape, two components, and the coefficient-product target scale.

Attributes

Name	Type	Default/value
skip_near_zero	float	0.0

operation_inventory

method

def operation_inventory(polynomial: PolynomialApproximation) -> dict[str, int]: ...

Return multiplying operations executed by evaluate.

Coefficient multiplication counts only active nonconstant terms. Alignment multiplication counts every multiply-by-one depth advance, including advances used inside the shared power tree and before term addition. Additions and plaintext encoding are not multiplications.

required_depths

method

def required_depths(polynomial: PolynomialApproximation) -> int: ...

Count the deepest balanced-product path and coefficient product.

evaluate

method

def evaluate(arithmetic: BootstrapArithmetic, ciphertext: Ciphertext, polynomial: PolynomialApproximation, *, relinearization_key: RelinearizationKey | None=None) -> Ciphertext: ...

Evaluate $p(x)=\sum _n{a}_n{x}^n$ at a common CKKS depth.

Coefficients with magnitude at or below skip_near_zero are omitted. A constant-only polynomial still consumes one depth by multiplying the input by zero; this keeps the execution behavior equal to the declared one-depth cost. Inputs are not mutated and output storage does not alias an input.

BinaryDecompositionChebyshevEvaluator

class View source

BinaryDecompositionChebyshevEvaluator(skip_near_zero: float = 0.0)

Evaluate a Chebyshev series through shared doubling identities.

The evaluator builds only basis elements required by nonzero terms. It recursively uses

$$T_{2n}(x)=2T_n(x{)}^2-1,T_{2n+1}(x)=2T_n(x)T_{n+1}(x)-T_1(x),$$

caching every required $T_n$ and each depth-specific $T_1$ for one call. Basis-node scales follow the input scale through each product and group rescale; the advanced copies of $T_1$ use that same recurrence. Coefficient products built from basis values at one depth are accumulated before one shared rescale; the resulting depth groups are then aligned and added. This keeps intermediate inputs near the approximation's bounded domain and exposes the critical-path depth.

The coordinate, tensor axes, arithmetic-state preconditions, functional behavior, per-product transitions, output depth, active prime_ids, and depth-dependent scale schedule match BalancedPowerEvaluator; only the polynomial basis and multiplication DAG differ.

Attributes

Name	Type	Default/value
skip_near_zero	float	0.0

operation_inventory

method

def operation_inventory(polynomial: PolynomialApproximation) -> dict[str, int]: ...

Return multiplying operations executed by evaluate.

Alignment includes operand advancement within odd recurrences, the shared depth chain for $T_1=x$, and advancement between coefficient depth groups. rescale_operations counts one coefficient rescale per occupied basis depth rather than one per coefficient product.

required_depths

method

def required_depths(polynomial: PolynomialApproximation) -> int: ...

Count the deepest required recurrence plus coefficient product.

evaluate

method

def evaluate(arithmetic: BootstrapArithmetic, ciphertext: Ciphertext, polynomial: PolynomialApproximation, *, relinearization_key: RelinearizationKey | None=None) -> Ciphertext: ...

Build required $T_n(x)$ values, align term depths, and sum them.

Terms at or below skip_near_zero are omitted. As in the power evaluator, the constant-only case deliberately consumes one depth so its execution agrees with required_depths. The method is functional and returns a two-component coefficient-domain standard-RNS Q value at the arithmetic owner's target scale.

ChebyshevInterpolator

class View source

ChebyshevInterpolator(degree: int, error_samples: int = 8193)

Fit a degree-limited Chebyshev series at first-kind nodes.

degree controls both the number of interpolation nodes and the highest returned term $T_d$. error_samples controls only the dense grid used to report max_error; that sampled value is not a proof of the uniform error between grid points.

Attributes

Name	Type	Default/value
degree	int
error_samples	int	8193

approximate

method

def approximate(function: Callable[[np.ndarray], np.ndarray], *, domain: tuple[float, float]=(-1.0, 1.0), name: str='polynomial') -> PolynomialApproximation: ...

Interpolate after mapping physical $t\in [a,b]$ to $x\in [-1,1]$.

If domain=(a, b), first-kind nodes $x_j$ are evaluated physically at

$$t_j=a+(x_j+1)(b-a)/2.$$

Coefficients in the returned object are functions of normalized $x$, not directly of physical $t$. The consuming evaluator must therefore normalize its ciphertext to $x$ and account for any depth spent on that affine map.

max_error is measured on error_samples equally spaced normalized coordinates after fitting. Approximation runs on CPU binary64/complex128 arrays and returns no encrypted tensor.

HornerPowerEvaluator

class View source

HornerPowerEvaluator()

Evaluate a power polynomial by a corrected depth-aware Horner chain.

For degree $d\ge 1$, evaluation starts with

$$r=c_{d}x+c_{d-1}$$

and then applies $r\leftarrow rx+c_i$ for $i=d-2,\dots ,0$. Thus the leading term remains $c_d{x}^d$. A depth-specific copy of $x$ is advanced once per ciphertext product and retained for that iteration, avoiding repeated advancement from the entry depth. The evaluator does not omit zero coefficients: the declared algebraic degree and execution schedule are stable properties of the coefficient tuple.

A constant polynomial deliberately consumes one depth by multiplying the input by zero. A linear polynomial consumes one coefficient-multiplication depth and requires no relinearization key. Degree $d\ge 2$ consumes exactly $d$ depths and requires one compatible QP relinearization key.

required_depths

method

def required_depths(polynomial: PolynomialApproximation) -> int: ...

Return one depth for constants or the declared power degree.

operation_inventory

method

def operation_inventory(polynomial: PolynomialApproximation) -> dict[str, int]: ...

Return the corrected-Horner multiplication inventory.

evaluate

method

def evaluate(arithmetic: BootstrapArithmetic, ciphertext: Ciphertext, polynomial: PolynomialApproximation, *, relinearization_key: RelinearizationKey | None=None) -> Ciphertext: ...

Evaluate a power polynomial with a corrected Horner recurrence.

The input must be a complete two-component coefficient-domain, standard-RNS Q ciphertext at its recorded actual scale. The method validates all context, key, scale, and available-depth requirements before allocating encrypted temporaries. The functional output is in the same arithmetic state at ciphertext.depth + required_depths(polynomial) and the arithmetic owner's target scale.

PatersonStockmeyerPowerEvaluator

class View source

PatersonStockmeyerPowerEvaluator(baby_step: int)

Evaluate a power polynomial with one fixed baby-step size.

baby_step=k is part of the evaluator identity and is never selected at runtime. The evaluator writes

$$p(x)=\sum _g{q}_g(x)(x^k{)}^g,\mathrm{deg}{q}_g<k.$$

Balanced shared powers $x,\dots ,x^k$ are constructed once. Baby powers are advanced to one common depth before coefficient multiplication, then the $q_g$ values are combined by Horner evaluation in $x^k$. Depth-specific copies of shared powers are cached for the invocation. If the highest group is a constant, its first giant step is the plaintext product $c_d{x}^k$, not an encrypted-zero seed followed by a ciphertext product.

Basis powers follow the input's actual scale recurrence. Coefficient accumulators use a common multiple of those scales chosen so the final product reaches the requested output scale. This keeps additions coherent without changing the polynomial's coefficients or its input coordinate.

The declared coefficient tuple, including zero entries, fixes the schedule. baby_step therefore controls a reproducible DAG rather than an unreliable degree-only estimate.

Attributes

Name	Type	Default/value
baby_step	int

required_depths

method

def required_depths(polynomial: PolynomialApproximation) -> int: ...

Return the critical-path depth cost for this fixed k.

operation_inventory

method

def operation_inventory(polynomial: PolynomialApproximation) -> dict[str, int]: ...

Return ciphertext, coefficient, and alignment counts.

evaluate

method

def evaluate(arithmetic: BootstrapArithmetic, ciphertext: Ciphertext, polynomial: PolynomialApproximation, *, relinearization_key: RelinearizationKey | None=None) -> Ciphertext: ...

Evaluate with the fixed baby/giant schedule and depth caches.

PolynomialApproximation

class View source

PolynomialApproximation(basis: PolynomialBasis, coefficients: tuple[complex, ...], domain: tuple[float, float] = (-1.0, 1.0), name: str = 'polynomial', max_error: float | None = None)

An immutable polynomial produced independently of its evaluation DAG.

The coefficient convention is ascending degree. For basis="power",

$$p(x)=\sum _{n=0}^d{a}_n{x}^n,$$

while basis="chebyshev" means

$$p(x)=\sum _{n=0}^d{a}_n{T}_n(x),T_0(x)=1,T_1(x)=x.$$

domain=(a, b) records the physical interval used to design the approximation. The evaluator input is nevertheless normalized $x$ unless (a, b) == (-1, 1); the caller owns the affine map.

Attributes

• basis: Basis in which coefficients are expressed.
• coefficients: Ascending coefficients: entry i multiplies either $x^i$ or $T_i(x)$.
• domain: Plaintext interval on which the approximation was designed.
• name: Human-readable diagnostic name.
• max_error: Optional sampled or certified approximation error.

Attributes

Name	Type	Default/value
basis	PolynomialBasis
coefficients	tuple[complex, ...]
domain	tuple[float, float]	(-1.0, 1.0)
name	str	'polynomial'
max_error	float | None	None

degree

property

degree: int

Return the algebraic degree including trailing zero entries.

evaluate_plaintext

method

def evaluate_plaintext(values: np.ndarray) -> np.ndarray: ...

Evaluate $p(x)$ elementwise without homomorphic arithmetic.

values may have any NumPy-broadcastable shape, which is preserved in the output. They are coordinates in the polynomial's basis domain. For a Chebyshev approximation created on a physical interval other than $[-1,1]$, callers must first apply the same affine normalization described by the approximator. This method is a numerical oracle; it does not model CKKS rounding or depth consumption.