zinc_poly/univariate/
dense.rs

1use crate::{
2    ConstCoeffBitWidth, EvaluatablePolynomial, EvaluationError, Polynomial,
3    univariate::{binary_ref::BinaryRefPoly, binary_u64::BinaryU64Poly},
4};
5
6use core::slice;
7use crypto_primitives::{
8    FieldConfig, ProjectElementWithConfig, Ring, RingConfig, Semiring, SemiringConfig, SetConfig,
9    boolean::Boolean,
10};
11use itertools::Itertools;
12use num_traits::{
13    CheckedAdd, CheckedMul, CheckedNeg, CheckedSub, ConstOne, ConstZero, One, Pow, Zero,
14};
15use rand::{distr::StandardUniform, prelude::*};
16use std::{
17    array,
18    fmt::{Debug, Display},
19    hash::Hash,
20    iter::{Product, Sum},
21    marker::PhantomData,
22    ops::{Add, AddAssign, Deref, DerefMut, Mul, MulAssign, Neg, Sub, SubAssign},
23};
24use zinc_transcript::traits::{ConstTranscribable, GenTranscribable};
25use zinc_utils::{
26    add,
27    from_ref::FromRef,
28    inner_product::{InnerProduct, InnerProductError},
29    mul_by_scalar::MulByScalar,
30    named::Named,
31    projectable_to_field::ProjectableToField,
32    rem,
33};
34
35/// Configuration of the polynomial semiring $S[X]$ over the (semi)ring
36/// configured by `S`, with [`DynamicPolynomial`] as its element.
37///
38/// Implements exactly the layer its coefficients provide: [`SemiringConfig`]
39/// over a semiring, additionally [`RingConfig`] over a ring. The polynomial
40/// ring is never a field, hence no [`FieldConfig`]; Euclidean division (which
41/// needs coefficient inversion), evaluation and other polynomial-specific
42/// operations are provided as inherent methods.
43///
44/// Checked operations delegate to the coefficient config's checked
45/// operations, so overflow behavior follows the coefficients (e.g. `Int`
46/// coefficients can overflow, field coefficients cannot).
47#[derive(Debug, Clone, Copy, PartialEq, Eq)]
48pub struct DensePolynomialConfig<'a, S: SemiringConfig, const DEGREE_PLUS_ONE: usize> {
49    pub cfg: &'a S,
50}
51
52/// Extension trait providing [`DensePolynomialConfig`] from a coefficient
53/// config, so that the same config can be used to perform operations on
54/// dynamic polynomials: `cfg.poly_cfg().mul(&p, &q)`.
55pub trait HasDensePolynomialConfig: SemiringConfig + Sized {
56    #[inline(always)]
57    fn dense_poly_cfg<const DEGREE_PLUS_ONE: usize>(
58        &self,
59    ) -> DensePolynomialConfig<'_, Self, DEGREE_PLUS_ONE> {
60        DensePolynomialConfig { cfg: self }
61    }
62}
63
64impl<S: SemiringConfig> HasDensePolynomialConfig for S {}
65
66impl<'a, S: SemiringConfig, const DEGREE_PLUS_ONE: usize> SetConfig
67    for DensePolynomialConfig<'a, S, DEGREE_PLUS_ONE>
68{
69    type Element = DensePolynomial<S::Element, DEGREE_PLUS_ONE>;
70}
71
72impl<'a, S: SemiringConfig, const DEGREE_PLUS_ONE: usize> SemiringConfig
73    for DensePolynomialConfig<'a, S, DEGREE_PLUS_ONE>
74{
75    fn is_zero(&self, value: &Self::Element) -> bool {
76        value.coeffs.iter().all(|c| self.cfg.is_zero(c))
77    }
78
79    fn zero(&self) -> Self::Element {
80        DensePolynomial {
81            coeffs: array::from_fn(|_| self.cfg.zero()),
82        }
83    }
84
85    fn one(&self) -> Self::Element {
86        let mut coeffs = array::from_fn(|_| self.cfg.zero());
87        coeffs[0] = self.cfg.one();
88        DensePolynomial { coeffs }
89    }
90
91    fn add(&self, x: &Self::Element, y: &Self::Element) -> Self::Element {
92        let mut res = x.clone();
93        for i in 0..DEGREE_PLUS_ONE {
94            self.cfg.add_assign(&mut res.coeffs[i], &y.coeffs[i]);
95        }
96        res
97    }
98
99    fn sub(&self, x: &Self::Element, y: &Self::Element) -> Self::Element {
100        let mut res = x.clone();
101        for i in 0..DEGREE_PLUS_ONE {
102            self.cfg.sub_assign(&mut res.coeffs[i], &y.coeffs[i]);
103        }
104        res
105    }
106
107    fn mul(&self, _x: &Self::Element, _y: &Self::Element) -> Self::Element {
108        unimplemented!("Polynomial multiplication is not implemented")
109    }
110
111    fn pow_u32(&self, x: &Self::Element, y: u32) -> Self::Element {
112        match y {
113            0 => self.one(),
114            1 => x.clone(),
115            _ => unimplemented!("Polynomial multiplication is not implemented"),
116        }
117    }
118
119    fn checked_add(&self, x: &Self::Element, y: &Self::Element) -> Option<Self::Element> {
120        let mut res = self.zero();
121        for i in 0..DEGREE_PLUS_ONE {
122            res.coeffs[i] = self.cfg.checked_add(&x.coeffs[i], &y.coeffs[i])?;
123        }
124        Some(res)
125    }
126
127    fn checked_sub(&self, x: &Self::Element, y: &Self::Element) -> Option<Self::Element> {
128        let mut res = self.zero();
129        for i in 0..DEGREE_PLUS_ONE {
130            res.coeffs[i] = self.cfg.checked_sub(&x.coeffs[i], &y.coeffs[i])?;
131        }
132        Some(res)
133    }
134
135    fn checked_mul(&self, _x: &Self::Element, _y: &Self::Element) -> Option<Self::Element> {
136        unimplemented!("Polynomial multiplication is not implemented")
137    }
138
139    fn checked_pow_u32(&self, x: &Self::Element, y: u32) -> Option<Self::Element> {
140        Some(match y {
141            0 => self.one(),
142            1 => x.clone(),
143            _ => unimplemented!("Polynomial multiplication is not implemented"),
144        })
145    }
146
147    fn sum<I: Iterator<Item = Self::Element>>(&self, iter: I) -> Self::Element {
148        iter.fold(self.zero(), |acc, x| {
149            self.checked_add(&acc, &x).expect("overflow in sum")
150        })
151    }
152
153    fn sum_refs<'b, I: Iterator<Item = &'b Self::Element> + 'b>(&self, iter: I) -> Self::Element {
154        iter.fold(self.zero(), |acc, x| {
155            self.checked_add(&acc, x).expect("overflow in sum")
156        })
157    }
158
159    fn product<I: Iterator<Item = Self::Element>>(&self, iter: I) -> Self::Element {
160        iter.fold(self.one(), |acc, x| {
161            self.checked_mul(&acc, &x).expect("overflow in product")
162        })
163    }
164
165    fn product_refs<'b, I: Iterator<Item = &'b Self::Element>>(&self, iter: I) -> Self::Element {
166        iter.fold(self.one(), |acc, x| {
167            self.checked_mul(&acc, x).expect("overflow in product")
168        })
169    }
170}
171
172impl<'a, S: SemiringConfig, const DEGREE_PLUS_ONE: usize>
173    DensePolynomialConfig<'a, S, DEGREE_PLUS_ONE>
174{
175    /// Create a new polynomial with the given coefficients.
176    /// If the input has fewer than N+1 coefficients, the remaining slots will
177    /// be filled with zeros. If the input has more than N+1 coefficients,
178    /// it will panic.
179    #[allow(clippy::arithmetic_side_effects)]
180    pub fn new_padded(
181        &self,
182        coeffs: impl AsRef<[S::Element]>,
183    ) -> DensePolynomial<S::Element, DEGREE_PLUS_ONE> {
184        DensePolynomial::new_with_zero(coeffs, self.cfg.zero())
185    }
186}
187
188impl<'a, S: RingConfig, const DEGREE_PLUS_ONE: usize> RingConfig
189    for DensePolynomialConfig<'a, S, DEGREE_PLUS_ONE>
190{
191    fn neg(&self, x: &Self::Element) -> Self::Element {
192        let mut res = x.clone();
193        res.coeffs.iter_mut().for_each(|c| *c = self.cfg.neg(c));
194        res
195    }
196
197    fn checked_neg(&self, x: &Self::Element) -> Option<Self::Element> {
198        let mut res = self.zero();
199        for i in 0..DEGREE_PLUS_ONE {
200            res.coeffs[i] = self.cfg.checked_neg(&x.coeffs[i])?;
201        }
202        Some(res)
203    }
204}
205
206#[derive(Debug, Clone, Copy, PartialEq, Eq)]
207pub struct DensePolynomial<R, const DEGREE_PLUS_ONE: usize> {
208    /// Coefficients of the polynomial, lowest degree first
209    pub coeffs: [R; DEGREE_PLUS_ONE],
210}
211
212impl<R: Semiring, const DEGREE_PLUS_ONE: usize> DensePolynomial<R, DEGREE_PLUS_ONE> {
213    /// Right-rotate the coefficient vector by `c` positions.
214    ///
215    /// The output coefficient at position `i` is the input coefficient at
216    /// `(i + c) mod DEGREE_PLUS_ONE`.
217    pub fn rotate_right(&self, c: usize) -> Self {
218        assert!(
219            c > 0 && c < DEGREE_PLUS_ONE,
220            "rotate_right count {} out of range (must satisfy 0 < c < {})",
221            c,
222            DEGREE_PLUS_ONE,
223        );
224        let coeffs = array::from_fn(|i| self.coeffs[rem!(add!(i, c), DEGREE_PLUS_ONE)].clone());
225        DensePolynomial { coeffs }
226    }
227
228    /// Right-shift the coefficient vector by `c` positions.
229    ///
230    /// The output coefficient at position `i` is the input coefficient at
231    /// `i + c`, or zero when that index is outside the coefficient vector.
232    pub fn shr(&self, c: usize) -> Self {
233        assert!(
234            c > 0 && c < DEGREE_PLUS_ONE,
235            "shr count {} out of range (must satisfy 0 < c < {})",
236            c,
237            DEGREE_PLUS_ONE,
238        );
239        let coeffs = array::from_fn(|i| {
240            let j = add!(i, c);
241            if j < DEGREE_PLUS_ONE {
242                self.coeffs[j].clone()
243            } else {
244                R::zero()
245            }
246        });
247        DensePolynomial { coeffs }
248    }
249}
250
251impl<R: Debug + Clone, const DEGREE_PLUS_ONE: usize> DensePolynomial<R, DEGREE_PLUS_ONE> {
252    #[inline(always)]
253    pub fn new(coeffs: [R; DEGREE_PLUS_ONE]) -> Self {
254        DensePolynomial { coeffs }
255    }
256
257    /// Create a new polynomial with the given coefficients.
258    /// If the input has fewer than N+1 coefficients, the remaining slots will
259    /// be filled with zeros. If the input has more than N+1 coefficients,
260    /// it will panic.
261    #[allow(clippy::arithmetic_side_effects)]
262    pub fn new_with_zero(coeffs: impl AsRef<[R]>, zero: R) -> Self {
263        let coeffs = coeffs.as_ref();
264        assert!(
265            coeffs.len() <= DEGREE_PLUS_ONE,
266            "Too many coefficients provided: expected at most {}, got {}",
267            DEGREE_PLUS_ONE,
268            coeffs.len()
269        );
270
271        let mut coeffs = coeffs.to_vec();
272        coeffs.resize(DEGREE_PLUS_ONE, zero);
273        let coeffs = coeffs.try_into().expect("unreachable");
274
275        DensePolynomial { coeffs }
276    }
277}
278
279impl<R: Display, const DEGREE_PLUS_ONE: usize> Display for DensePolynomial<R, DEGREE_PLUS_ONE> {
280    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
281        write!(f, "[")?;
282        let mut first = true;
283        for coeff in self.coeffs.iter() {
284            if first {
285                first = false;
286            } else {
287                write!(f, ", ")?;
288            }
289            write!(f, "{}", coeff)?;
290        }
291        write!(f, "]")?;
292        Ok(())
293    }
294}
295
296impl<R: Default, const DEGREE_PLUS_ONE: usize> Default for DensePolynomial<R, DEGREE_PLUS_ONE> {
297    fn default() -> Self {
298        DensePolynomial {
299            coeffs: array::from_fn::<_, DEGREE_PLUS_ONE, _>(|_| R::default()),
300        }
301    }
302}
303
304impl<R: Hash, const DEGREE_PLUS_ONE: usize> Hash for DensePolynomial<R, DEGREE_PLUS_ONE> {
305    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
306        for coeff in self.coeffs.iter() {
307            coeff.hash(state);
308        }
309    }
310}
311
312impl<R: Semiring + Zero, const DEGREE_PLUS_ONE: usize> Zero
313    for DensePolynomial<R, DEGREE_PLUS_ONE>
314{
315    fn zero() -> Self {
316        Self {
317            coeffs: array::from_fn::<_, DEGREE_PLUS_ONE, _>(|_| R::zero()),
318        }
319    }
320
321    fn is_zero(&self) -> bool {
322        self.coeffs.iter().all(|c| c.is_zero())
323    }
324}
325
326impl<R: Semiring + Zero + One, const DEGREE_PLUS_ONE: usize> One
327    for DensePolynomial<R, DEGREE_PLUS_ONE>
328{
329    fn one() -> Self {
330        let mut coeffs = array::from_fn(|_| R::zero());
331        coeffs[0] = R::one();
332        Self { coeffs }
333    }
334}
335
336impl<R: Ring, const DEGREE_PLUS_ONE: usize> Neg for DensePolynomial<R, DEGREE_PLUS_ONE> {
337    type Output = Self;
338
339    #[allow(clippy::arithmetic_side_effects)] // By design
340    fn neg(mut self) -> Self::Output {
341        self.coeffs.iter_mut().for_each(|c| *c = -c.clone());
342        self
343    }
344}
345
346impl<R: Semiring, const DEGREE_PLUS_ONE: usize> Add for DensePolynomial<R, DEGREE_PLUS_ONE> {
347    type Output = Self;
348
349    #[allow(clippy::arithmetic_side_effects, clippy::op_ref)]
350    #[inline(always)]
351    fn add(self, rhs: Self) -> Self::Output {
352        self + &rhs
353    }
354}
355
356impl<'a, R: Semiring, const DEGREE_PLUS_ONE: usize> Add<&'a Self>
357    for DensePolynomial<R, DEGREE_PLUS_ONE>
358{
359    type Output = Self;
360
361    #[allow(clippy::arithmetic_side_effects)]
362    #[inline(always)]
363    fn add(mut self, rhs: &'a Self) -> Self::Output {
364        self += rhs;
365        self
366    }
367}
368
369impl<R: Semiring, const DEGREE_PLUS_ONE: usize> Sub for DensePolynomial<R, DEGREE_PLUS_ONE> {
370    type Output = Self;
371
372    #[allow(clippy::arithmetic_side_effects, clippy::op_ref)]
373    #[inline(always)]
374    fn sub(self, rhs: Self) -> Self::Output {
375        self - &rhs
376    }
377}
378
379impl<'a, R: Semiring, const DEGREE_PLUS_ONE: usize> Sub<&'a Self>
380    for DensePolynomial<R, DEGREE_PLUS_ONE>
381{
382    type Output = Self;
383
384    #[allow(clippy::arithmetic_side_effects)]
385    #[inline(always)]
386    fn sub(mut self, rhs: &'a Self) -> Self::Output {
387        self -= rhs;
388        self
389    }
390}
391
392impl<R: Semiring, const DEGREE_PLUS_ONE: usize> Mul for DensePolynomial<R, DEGREE_PLUS_ONE> {
393    type Output = Self;
394
395    #[allow(clippy::arithmetic_side_effects, clippy::op_ref)]
396    #[inline(always)]
397    fn mul(self, rhs: Self) -> Self::Output {
398        self * &rhs
399    }
400}
401
402impl<'a, R: Semiring, const DEGREE_PLUS_ONE: usize> Mul<&'a Self>
403    for DensePolynomial<R, DEGREE_PLUS_ONE>
404{
405    type Output = Self;
406
407    fn mul(self, _rhs: &'a Self) -> Self::Output {
408        unimplemented!("Polynomial multiplication is not implemented")
409    }
410}
411
412impl<R: Semiring, const DEGREE_PLUS_ONE: usize> Pow<u32> for DensePolynomial<R, DEGREE_PLUS_ONE> {
413    type Output = Self;
414
415    fn pow(self, _rhs: u32) -> Self::Output {
416        unimplemented!("Polynomial multiplication is not implemented")
417    }
418}
419
420impl<R: Semiring, const DEGREE_PLUS_ONE: usize> AddAssign for DensePolynomial<R, DEGREE_PLUS_ONE> {
421    #[allow(clippy::arithmetic_side_effects)]
422    #[inline(always)]
423    fn add_assign(&mut self, rhs: Self) {
424        *self += &rhs;
425    }
426}
427
428impl<'a, R: Semiring, const DEGREE_PLUS_ONE: usize> AddAssign<&'a Self>
429    for DensePolynomial<R, DEGREE_PLUS_ONE>
430{
431    #[allow(clippy::arithmetic_side_effects)]
432    #[inline(always)]
433    fn add_assign(&mut self, rhs: &'a Self) {
434        for i in 0..DEGREE_PLUS_ONE {
435            self.coeffs[i] += &rhs.coeffs[i];
436        }
437    }
438}
439
440impl<R: Semiring, const DEGREE_PLUS_ONE: usize> SubAssign for DensePolynomial<R, DEGREE_PLUS_ONE> {
441    #[allow(clippy::arithmetic_side_effects)]
442    #[inline(always)]
443    fn sub_assign(&mut self, rhs: Self) {
444        *self -= &rhs;
445    }
446}
447
448impl<'a, R: Semiring, const DEGREE_PLUS_ONE: usize> SubAssign<&'a Self>
449    for DensePolynomial<R, DEGREE_PLUS_ONE>
450{
451    #[allow(clippy::arithmetic_side_effects)]
452    #[inline(always)]
453    fn sub_assign(&mut self, rhs: &'a Self) {
454        for i in 0..DEGREE_PLUS_ONE {
455            self.coeffs[i] -= &rhs.coeffs[i];
456        }
457    }
458}
459
460impl<R: Semiring, const DEGREE_PLUS_ONE: usize> MulAssign for DensePolynomial<R, DEGREE_PLUS_ONE> {
461    #[allow(clippy::arithmetic_side_effects)]
462    #[inline(always)]
463    fn mul_assign(&mut self, rhs: Self) {
464        *self *= &rhs;
465    }
466}
467
468impl<'a, R: Semiring, const DEGREE_PLUS_ONE: usize> MulAssign<&'a Self>
469    for DensePolynomial<R, DEGREE_PLUS_ONE>
470{
471    fn mul_assign(&mut self, _rhs: &'a Self) {
472        unimplemented!("Polynomial multiplication is not implemented")
473    }
474}
475
476impl<R: Ring + Zero, const DEGREE_PLUS_ONE: usize> CheckedNeg
477    for DensePolynomial<R, DEGREE_PLUS_ONE>
478{
479    fn checked_neg(&self) -> Option<Self> {
480        let mut coeffs = self.coeffs.clone();
481
482        coeffs
483            .iter_mut()
484            .filter(|coeff| !coeff.is_zero())
485            .try_for_each(|x| {
486                *x = x.checked_neg()?;
487                Some(())
488            })?;
489
490        Some(Self { coeffs })
491    }
492}
493
494impl<R: Semiring, const DEGREE_PLUS_ONE: usize> CheckedAdd for DensePolynomial<R, DEGREE_PLUS_ONE> {
495    fn checked_add(&self, other: &Self) -> Option<Self> {
496        let mut coeffs = self.coeffs.clone();
497
498        coeffs.iter_mut().zip(other).try_for_each(|(a, b)| {
499            *a = a.checked_add(b)?;
500            Some(())
501        })?;
502
503        Some(Self { coeffs })
504    }
505}
506
507impl<R: Semiring, const DEGREE_PLUS_ONE: usize> CheckedSub for DensePolynomial<R, DEGREE_PLUS_ONE> {
508    fn checked_sub(&self, other: &Self) -> Option<Self> {
509        let mut coeffs = self.coeffs.clone();
510
511        coeffs.iter_mut().zip(other).try_for_each(|(a, b)| {
512            *a = a.checked_sub(b)?;
513            Some(())
514        })?;
515
516        Some(Self { coeffs })
517    }
518}
519
520impl<R: Semiring, const DEGREE_PLUS_ONE: usize> CheckedMul for DensePolynomial<R, DEGREE_PLUS_ONE> {
521    fn checked_mul(&self, _other: &Self) -> Option<Self> {
522        unimplemented!("Polynomial multiplication is not implemented")
523    }
524}
525
526impl<R: Semiring, const DEGREE_PLUS_ONE: usize> Sum for DensePolynomial<R, DEGREE_PLUS_ONE> {
527    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
528        iter.fold(Self::zero(), |acc, x| {
529            acc.checked_add(&x).expect("overflow in sum")
530        })
531    }
532}
533
534impl<'a, R: Semiring, const DEGREE_PLUS_ONE: usize> Sum<&'a Self>
535    for DensePolynomial<R, DEGREE_PLUS_ONE>
536{
537    fn sum<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
538        iter.fold(Self::zero(), |acc, x| {
539            acc.checked_add(x).expect("overflow in sum")
540        })
541    }
542}
543
544impl<R: Semiring, const DEGREE_PLUS_ONE: usize> Product for DensePolynomial<R, DEGREE_PLUS_ONE> {
545    fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
546        iter.fold(Self::one(), |acc, x| {
547            acc.checked_mul(&x).expect("overflow in product")
548        })
549    }
550}
551
552impl<'a, R: Semiring, const DEGREE_PLUS_ONE: usize> Product<&'a Self>
553    for DensePolynomial<R, DEGREE_PLUS_ONE>
554{
555    fn product<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
556        iter.fold(Self::one(), |acc, x| {
557            acc.checked_mul(x).expect("overflow in product")
558        })
559    }
560}
561
562impl<R, const DEGREE_PLUS_ONE: usize> Distribution<DensePolynomial<R, DEGREE_PLUS_ONE>>
563    for StandardUniform
564where
565    StandardUniform: Distribution<R>,
566    StandardUniform: Distribution<[R; DEGREE_PLUS_ONE]>, // This one we get for free
567{
568    fn sample<Gen: Rng + ?Sized>(&self, rng: &mut Gen) -> DensePolynomial<R, DEGREE_PLUS_ONE> {
569        let coeffs: [R; DEGREE_PLUS_ONE] = rng.random();
570        DensePolynomial { coeffs }
571    }
572}
573
574//
575// Zip-specific traits
576//
577impl<R: Semiring, const DEGREE_PLUS_ONE: usize> Polynomial<R>
578    for DensePolynomial<R, DEGREE_PLUS_ONE>
579{
580    const DEGREE_BOUND: usize = DEGREE_PLUS_ONE - 1;
581}
582
583impl<R: Semiring, const DEGREE_PLUS_ONE: usize> EvaluatablePolynomial<R, R>
584    for DensePolynomial<R, DEGREE_PLUS_ONE>
585{
586    type EvaluationPoint = R;
587
588    fn evaluate_at_point(&self, point: &R) -> Result<R, EvaluationError> {
589        // Horner's method.
590        let mut result = self
591            .coeffs
592            .last()
593            .ok_or(EvaluationError::EmptyPolynomial)?
594            .clone();
595
596        for coeff in self.coeffs.iter().rev().skip(1) {
597            let term = result.checked_mul(point).ok_or(EvaluationError::Overflow)?;
598            result = term.checked_add(coeff).ok_or(EvaluationError::Overflow)?;
599        }
600
601        Ok(result)
602    }
603}
604
605impl<R: Semiring + ConstTranscribable, const DEGREE_PLUS_ONE: usize> ConstCoeffBitWidth
606    for DensePolynomial<R, DEGREE_PLUS_ONE>
607{
608    const COEFF_BIT_WIDTH: usize = R::NUM_BITS;
609}
610
611impl<R: Semiring + Named, const DEGREE_PLUS_ONE: usize> Named
612    for DensePolynomial<R, DEGREE_PLUS_ONE>
613{
614    fn type_name() -> String {
615        format!("Poly<{}, {}>", R::type_name(), Self::DEGREE_BOUND)
616    }
617}
618
619impl<R: ConstTranscribable + Default, const DEGREE_PLUS_ONE: usize> GenTranscribable
620    for DensePolynomial<R, DEGREE_PLUS_ONE>
621{
622    #[allow(clippy::arithmetic_side_effects)]
623    fn read_transcription_bytes_exact(bytes: &[u8]) -> Self {
624        assert_eq!(
625            bytes.len(),
626            R::NUM_BYTES * DEGREE_PLUS_ONE,
627            "Invalid byte length for DensePolynomial: expected {}, got {}",
628            R::NUM_BYTES * DEGREE_PLUS_ONE,
629            bytes.len()
630        );
631
632        // Can't use as_chunks because generic parameters may not be used in const
633        // operations.
634        let coeffs = bytes
635            .chunks_exact(R::NUM_BYTES)
636            .map(R::read_transcription_bytes_exact)
637            .collect_array()
638            .expect("Unreachable");
639        Self { coeffs }
640    }
641
642    fn write_transcription_bytes_exact(&self, buf: &mut [u8]) {
643        for (chunk, coeff) in buf.chunks_exact_mut(R::NUM_BYTES).zip(self.coeffs.iter()) {
644            coeff.write_transcription_bytes_exact(chunk);
645        }
646    }
647}
648
649impl<R: ConstTranscribable + Default, const DEGREE_PLUS_ONE: usize> ConstTranscribable
650    for DensePolynomial<R, DEGREE_PLUS_ONE>
651{
652    const NUM_BYTES: usize = R::NUM_BYTES * DEGREE_PLUS_ONE;
653}
654
655// Conversions.
656
657impl<R, S, const DEGREE_PLUS_ONE: usize> FromRef<DensePolynomial<S, DEGREE_PLUS_ONE>>
658    for DensePolynomial<R, DEGREE_PLUS_ONE>
659where
660    R: Semiring + FromRef<S> + Default,
661{
662    fn from_ref(value: &DensePolynomial<S, DEGREE_PLUS_ONE>) -> Self {
663        let mut coeffs = array::from_fn::<_, DEGREE_PLUS_ONE, _>(|_| R::default());
664        coeffs
665            .iter_mut()
666            .zip(value.coeffs.iter())
667            .for_each(|(coeff, other_coeff)| {
668                *coeff = R::from_ref(other_coeff);
669            });
670        DensePolynomial { coeffs }
671    }
672}
673
674impl<R, const DEGREE_PLUS_ONE: usize> FromRef<BinaryRefPoly<DEGREE_PLUS_ONE>>
675    for DensePolynomial<R, DEGREE_PLUS_ONE>
676where
677    R: Semiring + FromRef<Boolean> + Default,
678{
679    #[inline(always)]
680    fn from_ref(value: &BinaryRefPoly<DEGREE_PLUS_ONE>) -> Self {
681        Self::from_ref(value.inner())
682    }
683}
684
685impl<R, const DEGREE_PLUS_ONE: usize> FromRef<BinaryU64Poly<DEGREE_PLUS_ONE>>
686    for DensePolynomial<R, DEGREE_PLUS_ONE>
687where
688    R: Semiring + FromRef<Boolean> + Default,
689{
690    #[inline(always)]
691    fn from_ref(value: &BinaryU64Poly<DEGREE_PLUS_ONE>) -> Self {
692        let mut coeffs = array::from_fn::<_, DEGREE_PLUS_ONE, _>(|_| R::default());
693        coeffs.iter_mut().enumerate().for_each(|(i, coeff)| {
694            if value.inner() & (1 << i) != 0 {
695                *coeff = R::from_ref(&Boolean::ONE);
696            } else {
697                *coeff = R::from_ref(&Boolean::ZERO);
698            }
699        });
700        DensePolynomial { coeffs }
701    }
702}
703
704impl<R, S, const DEGREE_PLUS_ONE: usize> From<&DensePolynomial<S, DEGREE_PLUS_ONE>>
705    for DensePolynomial<R, DEGREE_PLUS_ONE>
706where
707    R: Semiring + FromRef<S> + Default,
708{
709    fn from(value: &DensePolynomial<S, DEGREE_PLUS_ONE>) -> Self {
710        Self::from_ref(value)
711    }
712}
713
714impl<R: Zero + One, const DEGREE_PLUS_ONE: usize> From<bool>
715    for DensePolynomial<R, DEGREE_PLUS_ONE>
716{
717    fn from(value: bool) -> Self {
718        let mut coeffs = array::from_fn(|_| R::zero());
719        coeffs[0] = if value { R::one() } else { R::zero() };
720        Self { coeffs }
721    }
722}
723
724impl<const DEGREE_PLUS_ONE: usize> FromRef<i64> for DensePolynomial<i128, DEGREE_PLUS_ONE> {
725    fn from_ref(value: &i64) -> Self {
726        let mut coeffs = array::from_fn(|_| 0_i128);
727        coeffs[0] = i128::from(*value);
728        Self { coeffs }
729    }
730}
731
732impl<R, S, Out, const DEGREE_PLUS_ONE: usize> MulByScalar<S, DensePolynomial<Out, DEGREE_PLUS_ONE>>
733    for DensePolynomial<R, DEGREE_PLUS_ONE>
734where
735    R: Semiring + MulByScalar<S, Out>,
736    Out: Semiring + Copy,
737{
738    fn mul_by_scalar<const CHECK: bool>(
739        self,
740        rhs: &S,
741    ) -> Option<DensePolynomial<Out, DEGREE_PLUS_ONE>> {
742        let mut coeffs = [Out::default(); DEGREE_PLUS_ONE];
743
744        coeffs
745            .iter_mut()
746            .zip(self.coeffs)
747            .filter(|(_, coeff)| !coeff.is_zero())
748            .try_for_each(|(out, x)| {
749                *out = x.mul_by_scalar::<CHECK>(rhs)?;
750                Some(())
751            })?;
752
753        Some(DensePolynomial { coeffs })
754    }
755}
756
757/// Projection by evaluation: the coefficients are projected into the field
758/// and the polynomial is evaluated at the sampled point.
759impl<E, C, const DEGREE_PLUS_ONE: usize> ProjectableToField<C>
760    for DensePolynomial<E, DEGREE_PLUS_ONE>
761where
762    C: FieldConfig + ProjectElementWithConfig<E> + Clone + Send + Sync + 'static,
763{
764    fn prepare_projection(
765        cfg: &C,
766        sampled_value: &C::Element,
767    ) -> impl Fn(&DensePolynomial<E, DEGREE_PLUS_ONE>) -> C::Element {
768        let cfg = cfg.clone();
769        let sampled_value = sampled_value.clone();
770
771        move |poly: &DensePolynomial<E, DEGREE_PLUS_ONE>| {
772            // Horner's method, projecting coefficients on the fly.
773            let mut result = cfg.zero();
774            for coeff in poly.coeffs.iter().rev() {
775                cfg.mul_assign(&mut result, &sampled_value);
776                let projected = cfg.project(coeff);
777                cfg.add_assign(&mut result, &projected);
778            }
779            result
780        }
781    }
782}
783
784impl<R, const DEGREE_PLUS_ONE: usize> DensePolynomial<R, DEGREE_PLUS_ONE> {
785    #[inline(always)]
786    pub fn iter(&self) -> std::slice::Iter<'_, R> {
787        self.coeffs.iter()
788    }
789
790    #[inline(always)]
791    pub fn iter_mut(&mut self) -> std::slice::IterMut<'_, R> {
792        self.coeffs.iter_mut()
793    }
794}
795
796impl<R, const DEGREE_PLUS_ONE: usize> IntoIterator for DensePolynomial<R, DEGREE_PLUS_ONE> {
797    type Item = R;
798
799    type IntoIter = std::array::IntoIter<R, DEGREE_PLUS_ONE>;
800
801    #[inline(always)]
802    fn into_iter(self) -> Self::IntoIter {
803        self.coeffs.into_iter()
804    }
805}
806
807impl<'a, R, const DEGREE_PLUS_ONE: usize> IntoIterator for &'a DensePolynomial<R, DEGREE_PLUS_ONE> {
808    type Item = &'a R;
809
810    type IntoIter = slice::Iter<'a, R>;
811
812    fn into_iter(self) -> Self::IntoIter {
813        self.coeffs.iter()
814    }
815}
816
817impl<R, const DEGREE_PLUS_ONE: usize> AsRef<[R]> for DensePolynomial<R, DEGREE_PLUS_ONE> {
818    fn as_ref(&self) -> &[R] {
819        self.coeffs.as_slice()
820    }
821}
822
823impl<R, const DEGREE_PLUS_ONE: usize> Deref for DensePolynomial<R, DEGREE_PLUS_ONE> {
824    type Target = [R];
825
826    fn deref(&self) -> &Self::Target {
827        self.coeffs.as_slice()
828    }
829}
830
831impl<R, const DEGREE_PLUS_ONE: usize> DerefMut for DensePolynomial<R, DEGREE_PLUS_ONE> {
832    fn deref_mut(&mut self) -> &mut Self::Target {
833        &mut self.coeffs
834    }
835}
836
837#[derive(Clone, Debug)]
838pub struct DensePolyInnerProduct<
839    Ctx,
840    R,
841    Rhs,
842    Out,
843    I: InnerProduct<Ctx, [R], Rhs, Out>,
844    const DEGREE_PLUS_ONE: usize,
845>(PhantomData<(I, Ctx, R, Rhs, Out)>);
846
847impl<C, R, Rhs, Out, I, const DEGREE_PLUS_ONE: usize>
848    InnerProduct<C, DensePolynomial<R, DEGREE_PLUS_ONE>, Rhs, Out>
849    for DensePolyInnerProduct<C, R, Rhs, Out, I, DEGREE_PLUS_ONE>
850where
851    I: InnerProduct<C, [R], Rhs, Out>,
852{
853    #[inline(always)]
854    fn inner_product<const CHECK: bool>(
855        cfg: &C,
856        lhs: &DensePolynomial<R, DEGREE_PLUS_ONE>,
857        rhs: &[Rhs],
858        zero: Out,
859    ) -> Result<Out, InnerProductError> {
860        I::inner_product::<CHECK>(cfg, &lhs.coeffs, rhs, zero)
861    }
862}
863
864#[cfg(test)]
865mod tests {
866    use super::*;
867
868    fn bits(coeffs: [u8; 8]) -> DensePolynomial<Boolean, 8> {
869        DensePolynomial {
870            coeffs: coeffs.map(|b| Boolean::new(b != 0)),
871        }
872    }
873
874    #[test]
875    fn rotate_right_permutes_coefficients() {
876        // Non-periodic pattern: rotate_right by different counts must yield
877        // observably different outputs.
878        let u = bits([1, 1, 1, 0, 0, 1, 0, 0]);
879        // rotate_right(u, 3).coeffs[i] = u.coeffs[(i + 3) mod 8]
880        // (u[3], u[4], u[5], u[6], u[7], u[0], u[1], u[2])
881        // = (0,    0,    1,    0,    0,    1,    1,    1)
882        assert_eq!(u.rotate_right(3), bits([0, 0, 1, 0, 0, 1, 1, 1]));
883        // rotate_right(u, 5).coeffs[i] = u.coeffs[(i + 5) mod 8]
884        // (u[5], u[6], u[7], u[0], u[1], u[2], u[3], u[4])
885        // = (1,    0,    0,    1,    1,    1,    0,    0)
886        assert_eq!(u.rotate_right(5), bits([1, 0, 0, 1, 1, 1, 0, 0]));
887        // Distinct outputs witness that rotation is not periodic on this input.
888        assert_ne!(u.rotate_right(3), u.rotate_right(5));
889    }
890
891    #[test]
892    fn rotate_right_is_cyclic() {
893        let u = bits([1, 1, 0, 0, 1, 0, 0, 0]);
894        let r1 = u.rotate_right(3);
895        let r2 = r1.rotate_right(5); // (3 + 5) mod 8 == 0, identity
896        assert_eq!(r2, u);
897    }
898
899    #[test]
900    fn shr_drops_low_bits_and_zero_pads_top() {
901        let u = bits([1, 0, 1, 0, 1, 0, 1, 0]);
902        // shr(u, 3).coeffs[i] = u.coeffs[i + 3] if i + 3 < 8 else 0
903        assert_eq!(u.shr(3), bits([0, 1, 0, 1, 0, 0, 0, 0]));
904    }
905
906    #[test]
907    fn shr_max_zeros_all_but_top() {
908        let u = bits([1, 1, 1, 1, 1, 1, 1, 1]);
909        // c = 7 keeps only u.coeffs[7] at position 0
910        assert_eq!(u.shr(7), bits([1, 0, 0, 0, 0, 0, 0, 0]));
911    }
912
913    #[test]
914    #[should_panic(expected = "rotate_right count")]
915    fn rotate_right_panics_on_zero() {
916        let _ = bits([1, 0, 0, 0, 0, 0, 0, 0]).rotate_right(0);
917    }
918
919    #[test]
920    #[should_panic(expected = "rotate_right count")]
921    fn rotate_right_panics_on_full_width() {
922        let _ = bits([1, 0, 0, 0, 0, 0, 0, 0]).rotate_right(8);
923    }
924
925    #[test]
926    #[should_panic(expected = "shr count")]
927    fn shr_panics_on_zero() {
928        let _ = bits([1, 0, 0, 0, 0, 0, 0, 0]).shr(0);
929    }
930
931    #[test]
932    #[should_panic(expected = "shr count")]
933    fn shr_panics_on_full_width() {
934        let _ = bits([1, 0, 0, 0, 0, 0, 0, 0]).shr(8);
935    }
936}
zinc_poly/univariate/dense.rs

zinc_poly/univariate/
dense.rs
