1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

use core::ops::{BitAnd, Mul, Shr};

use num::{pow::Pow, Integer, One, Unsigned};

use crate::{MaybeList, Polynomial};

impl<T, S, I> Pow<I> for Polynomial<T, S>
where
    T: Clone + One,
    S: MaybeList<T>,
    I: Unsigned + Integer + BitAnd<I, Output = I> + Shr<usize, Output = I> + Copy,
    Self: Into<Polynomial<T, Vec<T>>>,
    Polynomial<T, Vec<T>>: Mul<Polynomial<T, Vec<T>>, Output = Polynomial<T, Vec<T>>>
{
    type Output = Polynomial<T, Vec<T>>;

    fn pow(self, mut n: I) -> Self::Output
    {
        let mut x = self.into();
        let mut r = if (n & I::one()) == I::one()
        {
            x.clone()
        }
        else
        {
            Polynomial::one()
        };
    
        loop
        {
            n = n >> 1usize;
            if n == I::zero()
            {
                break;
            }
            x = x.clone()*x.clone();
            if (n & I::one()) == I::one()
            {
                r = r*x.clone();
            }
        }
    
        r
    }
}