p3_lde/
lib.rs

1//! This crate contains a framework for low-degree tests (LDTs).
2
3#![no_std]
4#![deprecated]
5
6mod naive;
7
8pub use naive::*;
9
10extern crate alloc;
11
12use p3_field::{Field, TwoAdicField};
13use p3_matrix::dense::RowMajorMatrix;
14use p3_matrix::Matrix;
15
16/// Performs low-degree extensions, where both the original domain and the extended domain are
17/// undefined, but must be consistent between calls with the same input height.
18pub trait UndefinedLde<Val, In>
19where
20    Val: Field,
21    In: Matrix<Val>,
22{
23    type Out: Matrix<Val>;
24
25    fn lde_batch(&self, polys: In, extended_height: usize) -> Self::Out;
26}
27
28/// Performs low-degree extensions over (possibly trivial) cosets of multiplicative subgroups of the
29/// domain, `Dom`.
30pub trait TwoAdicLde<Val>
31where
32    Val: TwoAdicField,
33{
34    /// Given a batch of polynomials, each defined by `2^k` evaluations over the subgroup generated
35    /// by `EF::primitive_root_of_unity(k)`, compute their evaluations over the (possibly trivial)
36    /// coset `shift H`, where `H` is the subgroup generated by
37    /// `EF::primitive_root_of_unity(k + added_bits)`.
38    fn lde_batch(&self, polys: RowMajorMatrix<Val>, added_bits: usize) -> RowMajorMatrix<Val>;
39}
40
41/// A specialization of `TwoAdicLde` where that evaluates polynomials over a multiplicative
42/// subgroup of the domain `Dom`, or in other words, a trivial coset thereof.
43pub trait TwoAdicSubgroupLde<Val>: TwoAdicLde<Val>
44where
45    Val: TwoAdicField,
46{
47}
48
49/// A specialization of `TwoAdicLde` where that evaluates polynomials over a nontrivial coset of a
50/// multiplicative subgroup of the domain `Dom`.
51pub trait TwoAdicCosetLde<Val>: TwoAdicLde<Val>
52where
53    Val: TwoAdicField,
54{
55    fn shift(&self, lde_bits: usize) -> Val;
56}