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

zinc_poly/univariate/
dense.rs
