fhelium.experimental.bootstrap.linear.evaluators

Direct and baby-step/giant-step execution of diagonal linear maps.

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.

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.