fhelium.experimental.bootstrap.polynomial

Polynomial approximations and encrypted evaluation schedules.

EvenChebyshevEvaluator

class View source

EvenChebyshevEvaluator(evaluator: Any)

Evaluate sum a_(2j) T_(2j)(x) as sum a_(2j) T_j(T2(x)).

evaluator selects the inner polynomial schedule. Forming T2(x)=2x²−1 consumes one ciphertext multiplication, relinearization and complete Q group rescale. The inner evaluator consumes the resulting actual scale. Odd coefficients must be zero; constants use the inner evaluator directly. Output preserves input representation and batch axes.

Attributes

Name	Type	Default/value
evaluator	Any

required_depths

method

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

operation_inventory

method

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

relinearization_depths

method

def relinearization_depths(polynomial: PolynomialApproximation, *, input_depth: int=0) -> tuple[int, ...] | None: ...

Compose the actual T2 product and the folded evaluator's consumers.

evaluate

method

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

BlockedChebyshevEvaluator

class View source

BlockedChebyshevEvaluator(baby_step: int | None = None, skip_near_zero: float = 0.0)

Evaluate $P(x)=\sum _j{A}_j(x)T_{jm}(x)$ with shared binary nodes.

Descending elimination uses $T_{jm+i}=2T_{jm}{T}_i-T_{jm-i}$ without refitting the polynomial. Giants use the original-coordinate binary recurrence. With baby_step=None, $m$ is the smallest power of two satisfying $m^2\ge \mathrm{deg}P$. The plan determines the actual depth cost; constants and low degrees use the direct binary schedule.

At final depth $f$, babies are restricted to $f-2$ while preserving each actual scale $S_k$. Coefficient plaintext scales $p_k=C/S_k$ are selected so every binary64 product is the common $C$. One block rescale produces $A=C/M_{f-2}$. Giants retain common scale $G$ at $f-1$; nonconstant giant products are summed as CT3 before one relinearization/rescale. The $j=0$ block is multiplied by encoded one at scale $G$. All output terms have actual scale $(AG)/M_{f-1}$. Constants are added after block rescale at scale $A$. $M_d$ is the complete dropped prime-group product.

Input and output are CT2 over Q with the same batch axes. The input domain is preserved when retaining NTT; otherwise output is coefficient form. NTT intermediates follow BootstrapArithmetic.retain_ntt. The approximation's domain remains caller-owned; complex inputs are evaluated as $P(z)$ and are never projected to their real part.

Attributes

Name	Type	Default/value
baby_step	int | None	None
skip_near_zero	float	0.0

plan

method

def plan(polynomial: PolynomialApproximation) -> ChebyshevBlockPlan: ...

Return the shared coefficient, basis, depth and operation plan.

required_depths

method

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

Return the depth consumed by this polynomial's selected plan.

operation_inventory

method

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

Count products, relinearizations and group rescales in the plan.

relinearization_depths

method

def relinearization_depths(polynomial: PolynomialApproximation, *, input_depth: int=0) -> tuple[int, ...]: ...

Return basis-product depths and the single delayed giant-sum depth.

evaluate

method

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

Execute the plan, retaining actual scales and the input domain.

ChebyshevBlockPlan

class View source

ChebyshevBlockPlan(polynomial: PolynomialApproximation, baby_step: int, coefficients: tuple[tuple[complex, ...], ...], basis_depths: tuple[tuple[int, int], ...], required_depths: int, inventory: tuple[tuple[str, int], ...])

Coefficient blocks, shared binary nodes and their depth schedule.

coefficients[j][i] multiplies T_i(x) T_(j*m)(x). A baby step of zero denotes the direct low-degree schedule. basis_depths records each node's depth relative to the input, in dependency order.

Attributes

Name	Type	Default/value
polynomial	PolynomialApproximation
baby_step	int
coefficients	tuple[tuple[complex, ...], ...]
basis_depths	tuple[tuple[int, int], ...]
required_depths	int
inventory	tuple[tuple[str, int], ...]

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 in the shared power schedule.

required_depths

method

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

Count the deepest shared power node plus its coefficient rescale.

relinearization_depths

method

def relinearization_depths(polynomial: PolynomialApproximation, *, input_depth: int=0) -> tuple[int, ...]: ...

Return product-input depths of the required shared power nodes.

evaluate

method

def evaluate(arithmetic: BootstrapArithmetic, ciphertext: Ciphertext, polynomial: PolynomialApproximation, *, relinearization_key: RelinearizationKey | EvaluationKeySet | Mapping[int, 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),$$

Shared basis nodes are retained until their last polynomial or recurrence consumer. Depth-specific $T_1$ copies serve the odd recurrences. 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 in the shared basis schedule.

required_depths

method

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

Count the deepest shared basis node plus its coefficient rescale.

relinearization_depths

method

def relinearization_depths(polynomial: PolynomialApproximation, *, input_depth: int=0) -> tuple[int, ...]: ...

Return product-input depths of the required shared basis nodes.

evaluate

method

def evaluate(arithmetic: BootstrapArithmetic, ciphertext: Ciphertext, polynomial: PolynomialApproximation, *, relinearization_key: RelinearizationKey | EvaluationKeySet | Mapping[int, 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. A constant-only polynomial consumes one depth, as reported by 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 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.

relinearization_depths

method

def relinearization_depths(polynomial: PolynomialApproximation, *, input_depth: int=0) -> tuple[int, ...]: ...

Return Horner product depths after the leading coefficient rescale.

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 | EvaluationKeySet | Mapping[int, 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 determines the product DAG and its required depths.

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.

relinearization_depths

method

def relinearization_depths(polynomial: PolynomialApproximation, *, input_depth: int=0) -> tuple[int, ...]: ...

Return basis and aligned giant-product depths from the fixed schedule.

evaluate

method

def evaluate(arithmetic: BootstrapArithmetic, ciphertext: Ciphertext, polynomial: PolynomialApproximation, *, relinearization_key: RelinearizationKey | EvaluationKeySet | Mapping[int, 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.