fhelium.experimental.bootstrap.linear

Packed-slot linear-transform representations, compilers, and evaluators.

DiagonalBSGSEvaluator

class View source

DiagonalBSGSEvaluator(baby_step: int, hoist_baby_rotations: bool = True, rotation_schedule: Literal['auto', 'group_major', 'baby_major'] = 'auto', baby_steps_by_transform: Mapping[str, int] | None = None, group_batch_size: int = 16, product_implementation: str | None = None, product_chunk_size: int | None = None, giant_step_reduction: Literal['aggregate', 'independent'] = 'aggregate', modup_method: Literal['exact', 'crt', 'normalized_crt'] | None = None)

Execute a diagonal map with shared BSGS rotations and live-set scheduling.

Splitting an offset as $k=g+b$ gives

$$L(x)=\sum _g{\mathrm{Rot}}_g(\sum _b{\mathrm{Rot}}_{-g}(d_{g+b})\odot {\mathrm{Rot}}_b(x)).$$

rotation_schedule="group_major" retains shared baby rotations and finishes at most group_batch_size giant groups at a time. Each baby is released after its last group consumer. "baby_major" generates one baby at a time and updates the giant-group accumulators. "auto" selects baby-major when there are fewer giant groups than distinct babies, otherwise group-major. The selected traversal is available through schedule_for. Group batches share ciphertext loads in one represented weighted sum; the default batch size is sixteen, and one selects immediate single-group completion.

product_implementation and product_chunk_size select the weighted product consumer. None retains native selection. Group-major traversal exposes multi-term rows; baby-major traversal honors the same request with one-term calls and preserves its live set. "auto" resolves by operand representation, device and registered Backend capabilities.

giant_step_reduction="aggregate" streams giant key products into one QP accumulator, then divides once by $P{M}_d$. "independent" rescales and key-switches each giant separately before summing its Q result. These schedules differ in rounding and temporary storage. At depth $d$, diagonal scale ${\mathrm{\Delta }}_p$ and Q-group product $M_d$, the coefficient/ standard Q output has two components, depth $d+1$ and actual scale ${\mathrm{\Delta }}_{out}={\mathrm{\Delta }}_{in}{\mathrm{\Delta }}_p/M_d$. Input batch axes and ring extent are preserved. Accumulation mutates only invocation-owned products.

Direct baby keys share one hybrid decomposition when hoist_baby_rotations is true. Composed inventories use the supplied rotation callable. baby_steps_by_transform selects named-stage steps.

Attributes

Name	Type	Default/value
baby_step	int
hoist_baby_rotations	bool	True
rotation_schedule	Literal['auto', 'group_major', 'baby_major']	'auto'
baby_steps_by_transform	Mapping[str, int] | None	None
group_batch_size	int	16
product_implementation	str | None	None
product_chunk_size	int | None	None
giant_step_reduction	Literal['aggregate', 'independent']	'aggregate'
modup_method	Literal['exact', 'crt', 'normalized_crt'] | None	None

required_depths

method

def required_depths(transform: Any) -> int: ...

Return the single rescale consumed by one BSGS stage.

baby_step_for

method

def baby_step_for(transform: DiagonalLinearTransform) -> int: ...

Return the caller-selected BSGS step for one compiled transform.

schedule_for

method

def schedule_for(transform: DiagonalLinearTransform) -> str: ...

Select a traversal from the stage's represented baby/group counts.

required_rotation_offsets

method

def required_rotation_offsets(transform: Any) -> tuple[int, ...]: ...

Return the union of nonzero baby and giant rotations.

baby_rotation_offsets

method

def baby_rotation_offsets(transform: DiagonalLinearTransform) -> tuple[int, ...]: ...

Return BSGS baby steps independently of decomposition sharing.

evaluate

method

def evaluate(arithmetic: BootstrapArithmetic, ciphertext: Ciphertext, transform: Any, *, rotation_paths: Mapping[int, tuple[RotationKey, ...]], rotate: Callable[[Ciphertext, int], Ciphertext], encode_diagonal: Callable[..., Plaintext | CompressedPlaintext]) -> Ciphertext: ...

Evaluate $L(x)$ while retaining only the chosen BSGS live set.

Group-major uses the ordinary represented plaintext-product sum for a bounded block of groups. Baby-major accumulates terms in the same baby order. Giant groups finish in increasing offset order using the selected shared or independent quotient schedule. Composed rotation inventories retain prefix key switches; the aggregate schedule combines their final switches. The shared quotient divides by the complete Q depth group. Diagonal material preparation and retention remain caller-owned.

DiagonalLinearTransform

class View source

DiagonalLinearTransform(diagonals: Mapping[int, ArrayLike], slots: int, name: str = 'diagonal_linear_transform')

An immutable cyclic-diagonal linear map over packed CKKS slots.

The map is

$$y=\sum _k{d}_k\odot {\mathrm{Rot}}_k(x).$$

Each stored diagonal is a CPU complex128 NumPy vector with shape [slot]; reference accepts and returns the same one-dimensional shape. An evaluator chooses the execution algorithm for these diagonals. Offsets are cyclic modulo $S$; duplicate representatives such as -1 and slots - 1 are combined by normalized_diagonals.

Attributes

Name	Type	Default/value
diagonals	Mapping[int, ArrayLike]
slots	int
name	str	'diagonal_linear_transform'

normalized_diagonals

method

def normalized_diagonals() -> dict[int, np.ndarray]: ...

Map every offset to $kmodS$ and combine equal rotations.

The stored arrays remain immutable. A new mapping is returned because two input offsets can normalize to the same cyclic key and must then be added elementwise. Returned vectors retain shape [slot].

reference

method

def reference(values: ArrayLike) -> np.ndarray: ...

Apply $L(x)=\sum _k{d}_k\odot {\mathrm{Rot}}_k(x)$ in NumPy.

values must have shape [slot]. The returned CPU complex128 array has shape [slot]. This plaintext oracle does not encode, rescale, consume depths, or model CKKS error.

DirectDiagonalEvaluator

class View source

DirectDiagonalEvaluator()

Evaluate each cyclic diagonal independently, then rescale once.

For every nonzero offset this strategy rotates the input, multiplies it by the corresponding encoded diagonal, and adds the product to an accumulator. All products have pending scale ${\mathrm{\Delta }}_{\mathrm{i}\mathrm{n}}{\mathrm{\Delta }}_p$, so the sum is rescaled only after every diagonal has been accumulated. It is simple but can require one direct rotation key for every nonzero diagonal.

The input is a two-component coefficient-domain standard-RNS Q ciphertext with data axes [component, *batch, limb, coefficient], ring extent $N$, and one homogeneous prime_ids tuple. If the removed Q group has product $M_d$, the functional result has the same component and batch axes, depth $\ell +1$, scale

$${\mathrm{\Delta }}_{\mathrm{o}\mathrm{u}\mathrm{t}}=\frac{{\mathrm{\Delta }}_{\mathrm{i}\mathrm{n}}{\mathrm{\Delta }}_p}{M_d},$$

and Q prime_ids with the complete group removed. The output remains in coefficient domain with standard residues; temporary diagonal plaintexts are NTT-domain Montgomery RNS. The result does not alias an input.

required_depths

method

def required_depths(transform: Any) -> int: ...

Return the single rescale consumed by one diagonal stage.

required_rotation_offsets

method

def required_rotation_offsets(transform: Any) -> tuple[int, ...]: ...

Return direct non-zero diagonal offsets.

evaluate

method

def evaluate(arithmetic: BootstrapArithmetic, ciphertext: Ciphertext, transform: Any, *, rotation_paths: Mapping[int, tuple[RotationKey, ...]], rotate: Callable[[Ciphertext, int], Ciphertext], encode_diagonal: Callable[..., Plaintext | CompressedPlaintext]) -> Ciphertext: ...

Apply $L(x)$ directly and consume one Q rescale depth.

The input must match the engine's slot count. For offset zero the input is reused directly; every other term requests one rotation through the supplied rotation-key strategy. Each diagonal is encoded at the input depth, multiplied into its rotated ciphertext, and accumulated at pending scale. A single final rescale advances the output by one depth.

Raises

• TypeError: If transform uses another stage representation.
• ValueError: If slot count or diagonal content is invalid.

Radix2FourierTransformCompiler

class View source

Radix2FourierTransformCompiler(stage_count: int, imaginary_unit_correction: bool = False, scale_stage: int | None = None)

Synthesize CKKS basis transforms from radix-2 butterflies.

Let $C$ be the unscaled coeffs_to_slots map and $T$ the unscaled slots_to_coeffs map in the engine's cyclotomic slot order. The compiler's convention is

$$T(C(x))=Sx.$$

Consequently a plaintext round trip uses forward scale=1 and inverse scale=1/S. The supplied scale multiplies the numerical map; it is not a CKKS metadata scale and does not change the diagonal plaintext encoding scale selected later by the evaluator.

stage_count controls only algebraic layer collapse. A smaller value consumes fewer CKKS depths but materializes more diagonals in each stage; a larger value retains sparse butterflies but spends more depths. The choice of direct, BSGS, distributed, or custom execution remains independent. scale_stage places the transform's numerical factor in one selected stage; None uses the first forward or final inverse stage.

Attributes

Name	Type	Default/value
stage_count	int
imaginary_unit_correction	bool	False
scale_stage	int | None	None

compile

method

def compile(*, slots: int, direction: TransformDirection, generator: int, scale: float=1.0) -> tuple[DiagonalLinearTransform, ...]: ...

Compile $C$ or $T$ into ordered cyclic-diagonal stages.

Compilation proceeds in four steps:

1. validate the cyclotomic slot orbit and build root tables;
2. construct one three-diagonal transform per radix-2 layer;
3. compose adjacent layers according to stage_count;
4. fold scale into the first forward stage or final inverse stage so the normalization is applied once in the complete transform.

slots is $S$ and every stored diagonal has axes [slot]. generator must enumerate $S$ distinct odd cyclotomic exponents modulo $4S$. direction chooses $C$ or $T$. Returns immutable CPU complex128 stages in online execution order; compilation performs no encryption.