Skip to content

Polynomial

add(p, q)

Adds two polynomials.

Parameters:

Name Type Description Default
p VectorInt

polynomial's \(p\) coefficients.

 required
q VectorInt

polynomial's \(q\) coefficients.

 required

Returns:

Type Description
VectorInt

Coefficients array of polynomial \(p + q\).
Source code in src/lbpqc/primitives/polynomial/poly.py 
148
149
150
151
152
153
154
155
156
157
158
159
160
161
@enforce_type_check
def add(p: VectorInt, q: VectorInt) -> VectorInt:
    r'''Adds two polynomials.

    Args:
        p: polynomial's $p$ coefficients.
        q: polynomial's $q$ coefficients.

    Returns:
        Coefficients array of polynomial $p + q$.
    '''

    max_deg = max(deg(p), deg(q), 0)
    return trim(pad(p, max_deg) + pad(q, max_deg))

deg(p, *, error_if_zero_poly=False)

Returns degree of a given polynomial calculated as an index of the last nonzero ceofficient. Returns -1 as a degree of zero polynomial if error_if_zero_poly is set to False.

Parameters:

Name Type Description Default
p VectorInt

Polynomial's coefficients.

 required
error_if_zero_poly bool

Parameter deciding how to treat degree of zero polynomial.

 False

Returns:

Type Description
int

Degree of the given polynomial.

Raises:

Type Description
ValueError

If given empty numpy array.
ValueError

If given zero polynomial and error_if_zero_poly is set to True.
Source code in src/lbpqc/primitives/polynomial/poly.py 
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
@enforce_type_check
def deg(p: VectorInt,*, error_if_zero_poly: bool = False) -> int:
    r'''
    Returns degree of a given polynomial calculated as an index of the last nonzero ceofficient.
    Returns -1 as a degree of zero polynomial if `error_if_zero_poly` is set to `False`.

    Args:
        p: Polynomial's coefficients.
        error_if_zero_poly: Parameter deciding how to treat degree of zero polynomial.

    Returns:
        Degree of the given polynomial.

    Raises:
        ValueError: If given empty numpy array.
        ValueError: If given zero polynomial **and** error_if_zero_poly is set to True.
    '''
    if len(p) == 0: raise ValueError("degree undefined for an empty numpy array")

    if len(nonzeros := np.nonzero(p)[0]) == 0:
        if error_if_zero_poly: raise ValueError("Degree of zero polynomial is undefined")
        return -1
    else:
        return nonzeros[-1]

is_zero_poly(p)

Checks if given polynomial is zero polynomial.

Parameters:

Name Type Description Default
p VectorInt

Polynomial's coefficients.

 required

Returns:

Type Description
bool

True if \(p \equiv 0\), False otherwise
Source code in src/lbpqc/primitives/polynomial/poly.py 
14
15
16
17
18
19
20
21
22
23
24
25
26
@enforce_type_check
def is_zero_poly(p: VectorInt) -> bool:
    r'''Checks if given polynomial is zero polynomial.

    Args:
        p: Polynomial's coefficients.

    Returns:
        True if $p \equiv 0$, False otherwise
    '''
    if len(p) == 0: raise ValueError("Empty numpy array is not a proper polynomial")

    return np.count_nonzero(p) == 0

monomial(coeff, degree)

For given degree \(d\) and coefficient \(c\), constructs a monomial $$ cX^{d - 1} $$

Parameters:

Name Type Description Default
coeff int

Monomial's coefficient.

 required
degree int

Monomial's degree.

 required

Returns:

Type Description
VectorInt

Coefficients' array with only nonzero entry coeff at degree index.

Examples:

\(7X^5\)

>>> monomial(7, 5)
array([0,0,0,0,0,5])
Source code in src/lbpqc/primitives/polynomial/poly.py 
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
@enforce_type_check
def monomial(coeff: int, degree: int) -> VectorInt:
    r'''
    For given degree $d$ and coefficient $c$, constructs a monomial
    $$
        cX^{d - 1}
    $$

    Args:
        coeff: Monomial's coefficient.
        degree: Monomial's degree.

    Returns:
        Coefficients' array with only nonzero entry `coeff` at `degree` index.

    Examples:
        $7X^5$
        >>> monomial(7, 5)
        array([0,0,0,0,0,5])
    '''
    p = np.zeros(degree + 1, dtype=int)
    p[degree] = coeff
    return p

mul(p, q)

Multiplies polynomials \(p\) and \(q\).

Parameters:

Name Type Description Default
p Vector

polynomial's \(p\) coefficients.

 required
q Vector

polynomial's \(q\) coefficients.

 required

Returns:

Type Description
Vector

Coefficients array of polynomial \(p \cdot q\).
Source code in src/lbpqc/primitives/polynomial/poly.py 
180
181
182
183
184
185
186
187
188
189
190
191
192
@enforce_type_check
def mul(p: Vector, q: Vector) -> Vector:
    r'''Multiplies polynomials $p$ and $q$.

    Args:
        p: polynomial's $p$ coefficients.
        q: polynomial's $q$ coefficients.

    Returns:
        Coefficients array of polynomial $p \cdot q$.
    '''

    return np.polymul(p[::-1], q[::-1])[::-1]

pad(p, max_deg)

Pad's polynomial's coefficient's array with zero entries for powers higher than polynomial's degree, so that length of resulting array is equal to max_deg + 1.

Parameters:

Name Type Description Default
p VectorInt

Polynomial's coefficients.

 required
max_deg int

Degree that \(p\) is to be expanded to.

 required

Returns:

Type Description
VectorInt

Coefficient's array with length equal to max_deg + 1, filled with zeros at indices greater than \(\deg(p)\).

Examples:

\(p = X^3 + 7X - 2\)

>>> p = np.array([-2, 7, 0, 1])
>>> pad(p, 5)
array([-2, 7, 0, 1, 0, 0])
Source code in src/lbpqc/primitives/polynomial/poly.py 
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
@enforce_type_check
def pad(p: VectorInt, max_deg: int) -> VectorInt:
    r'''
    Pad's polynomial's coefficient's array with zero entries for powers higher than polynomial's degree,
    so that length of resulting array is equal to max_deg + 1.

    Args:
        p: Polynomial's coefficients.
        max_deg: Degree that $p$ is to be expanded to.

    Returns:
        Coefficient's array with length equal to `max_deg` + 1, filled with zeros at indices greater than $\deg(p)$.

    Examples:
        $p = X^3 + 7X - 2$
        >>> p = np.array([-2, 7, 0, 1])
        >>> pad(p, 5)
        array([-2, 7, 0, 1, 0, 0])
    '''
    if is_zero_poly(p):
        return zero_poly(max_deg)

    d = deg(p)
    if max_deg < d: raise ValueError("max_deg has to be greater or equal to the degree of a given polynomial p")

    return np.pad(trim(p), (0, max_deg - d))

sub(p, q)

Subtract polynomial \(q\) from polynomial \(p\).

Parameters:

Name Type Description Default
p VectorInt

polynomial's \(p\) coefficients.

 required
q VectorInt

polynomial's \(q\) coefficients.

 required

Returns:

Type Description
VectorInt

Coefficients array of polynomial \(p - q\).
Source code in src/lbpqc/primitives/polynomial/poly.py 
164
165
166
167
168
169
170
171
172
173
174
175
176
177
@enforce_type_check
def sub(p: VectorInt, q: VectorInt) -> VectorInt:
    r'''Subtract polynomial $q$ from polynomial $p$.

    Args:
        p: polynomial's $p$ coefficients.
        q: polynomial's $q$ coefficients.

    Returns:
        Coefficients array of polynomial $p - q$.
    '''

    max_deg = max(deg(p), deg(q), 0)
    return trim(pad(p, max_deg) - pad(q, max_deg))

trim(p)

Trims zero coefficients of powers higher than polynomial's degree, so that resulting coefficient's arrray has length of \(\deg(p) + 1\).

If p is zero polynomial, then returns np.array([0], dtype=int).

Parameters:

Name Type Description Default
p VectorInt

Polynomial's coefficients.

 required

Returns:

Type Description
VectorInt

Coefficient's array of length at most \(\deg(p)\).

Examples:

>>> p = np.array([1,0,2,3,0,0,0])
>>> trim(p)
array([1,0,2,3])
Source code in src/lbpqc/primitives/polynomial/poly.py 
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
@enforce_type_check
def trim(p: VectorInt) -> VectorInt:
    r'''
    Trims zero coefficients of powers higher than polynomial's degree,
    so that resulting coefficient's arrray has length of $\deg(p) + 1$.

    If p is zero polynomial, then returns `np.array([0], dtype=int)`.

    Args:
        p: Polynomial's coefficients.

    Returns:
        Coefficient's array of length at most $\deg(p)$.

    Examples:
        >>> p = np.array([1,0,2,3,0,0,0])
        >>> trim(p)
        array([1,0,2,3])
    '''
    if is_zero_poly(p):
        return np.zeros(1, dtype=int)

    return p[:deg(p) + 1].copy()

zero_poly(max_deg=0)

Explicitly constructs zero polynomial, i.e. a coefficient's array of length max_deg + 1 filled with zeros.

Parameters:

Name Type Description Default
max_deg int

.

 0

Returns:

Type Description
VectorInt

Coefficients' array of length max_deg + 1 filled with zeros.
Source code in src/lbpqc/primitives/polynomial/poly.py 
133
134
135
136
137
138
139
140
141
142
143
144
@enforce_type_check
def zero_poly(max_deg: int = 0) -> VectorInt:
    r'''Explicitly constructs zero polynomial, i.e. a coefficient's array of length `max_deg` + 1 filled with zeros.

    Args:
        max_deg: .

    Returns:
        Coefficients' array of length `max_deg` + 1 filled with zeros.
    '''

    return np.zeros(max_deg + 1, dtype=int)

This class implements operations over \(\mathbb{Z}_p[X]\) polynomial ring, i.e. polynomials which coefficients are reduced modulo \(p\).

It's important to note that polynomials are represented as numpy's arrays with entries corresponding to coefficients in order of increasing powers.
Instance of ModIntPolyRing class represents the polynomials ring.
It's methods implements operations in this rings, but polynomials in their inputs and outputs are still numpy's arrays.

Attributes:

Name Type Description
modulus int

modulus \(p\) of the \(\mathbb{Z}_p[X]\) polynomial ring.
Source code in src/lbpqc/primitives/polynomial/modpoly.py 
  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
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
class ModIntPolyRing:
    r'''This class implements operations over $\mathbb{Z}_p[X]$ polynomial ring, i.e. polynomials which coefficients are reduced modulo $p$.

    It's important to note that polynomials are represented as numpy's arrays with entries corresponding to coefficients in order of increasing powers.  
    Instance of `ModIntPolyRing` class represents the polynomials ring.  
    It's methods implements operations in this rings, but polynomials in their inputs and outputs are still numpy's arrays.

    Attributes:
        modulus (int): modulus $p$ of the $\mathbb{Z}_p[X]$ polynomial ring.
    '''
    @enforce_type_check
    def __init__(self, modulus: int) -> None:
        r'''
        Constructs the ring object for a given **modulus**.

        Args:
            modulus: Ring modulus.
        '''
        if modulus <= 1: raise ValueError("Modulus has to be greater than 1")
        self.modulus = modulus


    @enforce_type_check
    def reduce(self, polynomial: VectorInt) -> VectorModInt:
        r'''
        Reduces the given polynomial to it's cannonical equivalence class in the ring, i.e. reduces polynomials' coefficients modulo **modulus**.

        Args:
            polynomial: Polynomial's coefficients array.

        Returns:
            Array of coefficients reduced modulo **modulus**.
        '''
        return poly.trim(polynomial % self.modulus)


    @enforce_type_check
    def is_zero(self, polynomial: VectorInt) -> bool:
        r'''
        Checks whether given polynomial is zero polynomial in the ring,
        so whether all it's coefficients are divisible by **modulus**.

        Args:
            polynomial: Coefficients array of polynomial to be checked.

        Returns:
            `True` if polynomial is zero polynomial in the ring else `False`
        '''
        return poly.is_zero_poly(self.reduce(polynomial))


    @enforce_type_check
    def deg(self, polynomial: VectorInt) -> int:
        r'''Calculates degree of the given polynomial.

        Args:
            polynomial: polynomial's coefficients

        Returns:
            degree of the polynomial in the ring.
        '''

        return poly.deg(self.reduce(polynomial))


    @enforce_type_check
    def add(self, polynomial_a: VectorInt, polynomial_b: VectorInt) -> VectorModInt:
        r'''Adds polynomial $a$ to polynomial $b$.

        Args:
            polynomial_a: polynomial's $a$ coefficients.
            polynomial_b: polynomial's $b$ coefficients.

        Returns:
            Coefficients array of polynomial $a + b$.
        '''

        return self.reduce(poly.add(polynomial_a, polynomial_b))

    @enforce_type_check
    def sub(self, polynomial_a: VectorInt, polynomial_b: VectorInt) -> VectorModInt:
        r'''Subtract polynomial $b$ from polynomial $a$.

        Args:
            polynomial_a: polynomial's $a$ coefficients.
            polynomial_b: polynomial's $b$ coefficients.

        Returns:
            Coefficients array of polynomial $a - b$.
        '''


        return self.reduce(poly.sub(polynomial_a, polynomial_b))


    @enforce_type_check
    def mul(self, polynomial_a: VectorInt, polynomial_b: VectorInt) -> VectorModInt:
        r'''Multiplies polynomial $a$ and polynomial $b$.

        Args:
            polynomial_a: polynomial's $a$ coefficients.
            polynomial_b: polynomial's $b$ coefficients.

        Returns:
            Coefficients array of polynomial $a \cdot b$.
        '''

        return self.reduce(poly.mul(polynomial_a, polynomial_b))


    @enforce_type_check
    def euclidean_div(self,  polynomial_a: VectorInt, polynomial_b: VectorInt) -> Tuple[VectorModInt, VectorModInt]:
        r'''Euclidean division (long division) for polynomials in the ring.

        Args:
            polynomial_a: .
            polynomial_b: .

        Returns:
            Quotient and Remainder polynomials.
        '''

        if self.is_zero(polynomial_b): raise ZeroDivisionError("Can't divide by zero polynomial")

        q = poly.zero_poly()
        r = self.reduce(polynomial_a)

        d = self.deg(polynomial_b)
        c = polynomial_b[d]
        while (dr := self.deg(r)) >= d:
            s = poly.monomial(r[dr] * modinv(c, self.modulus), dr - d)
            q = self.add(q, s)
            r = self.sub(r, self.mul(s, polynomial_b))

        return q, r


    @enforce_type_check
    def rem(self, polynomial_a: VectorInt, polynomial_b: VectorInt) -> VectorModInt:
        r'''Computes only remainder of the euclidean divions of two ring's polynomials.

        Args:
            polynomial_a: .
            polynomial_b: .

        Returns:
            Remainder of the euclidean division.
        '''

        if self.is_zero(polynomial_b): raise ZeroDivisionError("Can't divide by zero polynomial")

        _, r = self.euclidean_div(polynomial_a, polynomial_b)
        return r

    @enforce_type_check
    def to_monic(self, polynomial: VectorInt) -> VectorModInt:
        r'''Reduces given polynomial to monic polynomial by multiplying it by scalar equal to modular multiplicative inverse of the highest power coefficient.

        Args:
            polynomial: .

        Returns:
            Polynomial with leading coefficient equal to 1.
        '''

        leading_coeff = polynomial[self.deg(polynomial)]

        return self.reduce(modinv(leading_coeff, self.modulus) * polynomial)


    @enforce_type_check
    def gcd(self, polynomial_a: VectorInt, polynomial_b: VectorInt) -> VectorModInt:
        r'''calculates $\gcd$ of polynomials $a$ and $b$ using euclidean algorithm.  
        It's worth noting that int the polynomial ring, $\gcd$ is not unique.

        Args:
            polynomial_a: Coefficients array of polynomial $a$.
            polynomial_b: Coefficients array of polynomial $b$.

        Returns:
            Polynomial with maximal degree that divides both $a$ and $b$.

        '''

        r0 = self.reduce(polynomial_a)
        r1 = self.reduce(polynomial_b)
        if poly.deg(r1) > poly.deg(r0):
            r0, r1 = r1, r0

        while not self.is_zero(r1):
            r0, r1 = r1, self.rem(r0, r1)

        return r0


    @enforce_type_check
    def coprime(self, polynomial_a: VectorInt, polynomial_b: VectorInt) -> bool:
        r'''checks whether two polynomials $a$ and $b$ are coprime in a ring.  
        Checks whether $\gcd(a,b)$ reduced to monic polynomial is equal to constant polynomial $p \equiv 1$.

        Args:
            polynomial_a: Coefficients array of polynomial $a$.
            polynomial_b: Coefficients array of polynomial $b$.

        Returns:
            `True` if $a$ and $b$ are coprime in the ring, `False` otherwise.

        '''
        return np.all(self.to_monic(self.gcd(polynomial_a, polynomial_b)) == poly.monomial(1, 0))


    @enforce_type_check
    def eea(self, polynomial_a: VectorInt, polynomial_b: VectorInt) -> Tuple[VectorModInt, VectorModInt, VectorModInt]:
        r'''Extended Euclidean algorithm for polynomials, e.i algorithm that calculates coefficients for **Bézout's identity**.

        Args:
            polynomial_a: Coefficients array of polynomial $a$.
            polynomial_b: Coefficients array of polynomial $b$.

        Returns:
            Tuple of polynomials $(d, s, t)$ that satisfies $\gcd(a,b) = d$ and $s \cdot a + t \cdot b = d$.

        '''

        f0, f1 = self.reduce(polynomial_a), self.reduce(polynomial_b)
        a0, a1 = poly.monomial(1, 0), poly.zero_poly()
        b0, b1 = poly.zero_poly(), poly.monomial(1, 0)

        while not self.is_zero(f1):
            q, r = self.euclidean_div(f0, f1)

            f0, f1 = f1, r

            a0, a1 = a1, self.sub(a0, self.mul(q, a1))
            b0, b1 = b1, self.sub(b0, self.mul(q, b1))

        return f0, a0, b0

__init__(modulus)

Constructs the ring object for a given modulus.

Parameters:

Name Type Description Default
modulus int

Ring modulus.

 required
Source code in src/lbpqc/primitives/polynomial/modpoly.py 
16
17
18
19
20
21
22
23
24
25
@enforce_type_check
def __init__(self, modulus: int) -> None:
    r'''
    Constructs the ring object for a given **modulus**.

    Args:
        modulus: Ring modulus.
    '''
    if modulus <= 1: raise ValueError("Modulus has to be greater than 1")
    self.modulus = modulus

add(polynomial_a, polynomial_b)

Adds polynomial \(a\) to polynomial \(b\).

Parameters:

Name Type Description Default
polynomial_a VectorInt

polynomial's \(a\) coefficients.

 required
polynomial_b VectorInt

polynomial's \(b\) coefficients.

 required

Returns:

Type Description
VectorModInt

Coefficients array of polynomial \(a + b\).
Source code in src/lbpqc/primitives/polynomial/modpoly.py 
71
72
73
74
75
76
77
78
79
80
81
82
83
@enforce_type_check
def add(self, polynomial_a: VectorInt, polynomial_b: VectorInt) -> VectorModInt:
    r'''Adds polynomial $a$ to polynomial $b$.

    Args:
        polynomial_a: polynomial's $a$ coefficients.
        polynomial_b: polynomial's $b$ coefficients.

    Returns:
        Coefficients array of polynomial $a + b$.
    '''

    return self.reduce(poly.add(polynomial_a, polynomial_b))

coprime(polynomial_a, polynomial_b)

checks whether two polynomials \(a\) and \(b\) are coprime in a ring.
Checks whether \(\gcd(a,b)\) reduced to monic polynomial is equal to constant polynomial \(p \equiv 1\).

Parameters:

Name Type Description Default
polynomial_a VectorInt

Coefficients array of polynomial \(a\).

 required
polynomial_b VectorInt

Coefficients array of polynomial \(b\).

 required

Returns:

Type Description
bool

True if \(a\) and \(b\) are coprime in the ring, False otherwise.
Source code in src/lbpqc/primitives/polynomial/modpoly.py 
201
202
203
204
205
206
207
208
209
210
211
212
213
214
@enforce_type_check
def coprime(self, polynomial_a: VectorInt, polynomial_b: VectorInt) -> bool:
    r'''checks whether two polynomials $a$ and $b$ are coprime in a ring.  
    Checks whether $\gcd(a,b)$ reduced to monic polynomial is equal to constant polynomial $p \equiv 1$.

    Args:
        polynomial_a: Coefficients array of polynomial $a$.
        polynomial_b: Coefficients array of polynomial $b$.

    Returns:
        `True` if $a$ and $b$ are coprime in the ring, `False` otherwise.

    '''
    return np.all(self.to_monic(self.gcd(polynomial_a, polynomial_b)) == poly.monomial(1, 0))

deg(polynomial)

Calculates degree of the given polynomial.

Parameters:

Name Type Description Default
polynomial VectorInt

polynomial's coefficients

 required

Returns:

Type Description
int

degree of the polynomial in the ring.
Source code in src/lbpqc/primitives/polynomial/modpoly.py 
57
58
59
60
61
62
63
64
65
66
67
68
@enforce_type_check
def deg(self, polynomial: VectorInt) -> int:
    r'''Calculates degree of the given polynomial.

    Args:
        polynomial: polynomial's coefficients

    Returns:
        degree of the polynomial in the ring.
    '''

    return poly.deg(self.reduce(polynomial))

eea(polynomial_a, polynomial_b)

Extended Euclidean algorithm for polynomials, e.i algorithm that calculates coefficients for Bézout's identity.

Parameters:

Name Type Description Default
polynomial_a VectorInt

Coefficients array of polynomial \(a\).

 required
polynomial_b VectorInt

Coefficients array of polynomial \(b\).

 required

Returns:

Type Description
Tuple[VectorModInt, VectorModInt, VectorModInt]

Tuple of polynomials \((d, s, t)\) that satisfies \(\gcd(a,b) = d\) and \(s \cdot a + t \cdot b = d\).
Source code in src/lbpqc/primitives/polynomial/modpoly.py 
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
@enforce_type_check
def eea(self, polynomial_a: VectorInt, polynomial_b: VectorInt) -> Tuple[VectorModInt, VectorModInt, VectorModInt]:
    r'''Extended Euclidean algorithm for polynomials, e.i algorithm that calculates coefficients for **Bézout's identity**.

    Args:
        polynomial_a: Coefficients array of polynomial $a$.
        polynomial_b: Coefficients array of polynomial $b$.

    Returns:
        Tuple of polynomials $(d, s, t)$ that satisfies $\gcd(a,b) = d$ and $s \cdot a + t \cdot b = d$.

    '''

    f0, f1 = self.reduce(polynomial_a), self.reduce(polynomial_b)
    a0, a1 = poly.monomial(1, 0), poly.zero_poly()
    b0, b1 = poly.zero_poly(), poly.monomial(1, 0)

    while not self.is_zero(f1):
        q, r = self.euclidean_div(f0, f1)

        f0, f1 = f1, r

        a0, a1 = a1, self.sub(a0, self.mul(q, a1))
        b0, b1 = b1, self.sub(b0, self.mul(q, b1))

    return f0, a0, b0

euclidean_div(polynomial_a, polynomial_b)

Euclidean division (long division) for polynomials in the ring.

Parameters:

Name Type Description Default
polynomial_a VectorInt

.

 required
polynomial_b VectorInt

.

 required

Returns:

Type Description
Tuple[VectorModInt, VectorModInt]

Quotient and Remainder polynomials.
Source code in src/lbpqc/primitives/polynomial/modpoly.py 
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
@enforce_type_check
def euclidean_div(self,  polynomial_a: VectorInt, polynomial_b: VectorInt) -> Tuple[VectorModInt, VectorModInt]:
    r'''Euclidean division (long division) for polynomials in the ring.

    Args:
        polynomial_a: .
        polynomial_b: .

    Returns:
        Quotient and Remainder polynomials.
    '''

    if self.is_zero(polynomial_b): raise ZeroDivisionError("Can't divide by zero polynomial")

    q = poly.zero_poly()
    r = self.reduce(polynomial_a)

    d = self.deg(polynomial_b)
    c = polynomial_b[d]
    while (dr := self.deg(r)) >= d:
        s = poly.monomial(r[dr] * modinv(c, self.modulus), dr - d)
        q = self.add(q, s)
        r = self.sub(r, self.mul(s, polynomial_b))

    return q, r

gcd(polynomial_a, polynomial_b)

calculates \(\gcd\) of polynomials \(a\) and \(b\) using euclidean algorithm.
It's worth noting that int the polynomial ring, \(\gcd\) is not unique.

Parameters:

Name Type Description Default
polynomial_a VectorInt

Coefficients array of polynomial \(a\).

 required
polynomial_b VectorInt

Coefficients array of polynomial \(b\).

 required

Returns:

Type Description
VectorModInt

Polynomial with maximal degree that divides both \(a\) and \(b\).
Source code in src/lbpqc/primitives/polynomial/modpoly.py 
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
@enforce_type_check
def gcd(self, polynomial_a: VectorInt, polynomial_b: VectorInt) -> VectorModInt:
    r'''calculates $\gcd$ of polynomials $a$ and $b$ using euclidean algorithm.  
    It's worth noting that int the polynomial ring, $\gcd$ is not unique.

    Args:
        polynomial_a: Coefficients array of polynomial $a$.
        polynomial_b: Coefficients array of polynomial $b$.

    Returns:
        Polynomial with maximal degree that divides both $a$ and $b$.

    '''

    r0 = self.reduce(polynomial_a)
    r1 = self.reduce(polynomial_b)
    if poly.deg(r1) > poly.deg(r0):
        r0, r1 = r1, r0

    while not self.is_zero(r1):
        r0, r1 = r1, self.rem(r0, r1)

    return r0

is_zero(polynomial)

Checks whether given polynomial is zero polynomial in the ring, so whether all it's coefficients are divisible by modulus.

Parameters:

Name Type Description Default
polynomial VectorInt

Coefficients array of polynomial to be checked.

 required

Returns:

Type Description
bool

True if polynomial is zero polynomial in the ring else False
Source code in src/lbpqc/primitives/polynomial/modpoly.py 
42
43
44
45
46
47
48
49
50
51
52
53
54
@enforce_type_check
def is_zero(self, polynomial: VectorInt) -> bool:
    r'''
    Checks whether given polynomial is zero polynomial in the ring,
    so whether all it's coefficients are divisible by **modulus**.

    Args:
        polynomial: Coefficients array of polynomial to be checked.

    Returns:
        `True` if polynomial is zero polynomial in the ring else `False`
    '''
    return poly.is_zero_poly(self.reduce(polynomial))

mul(polynomial_a, polynomial_b)

Multiplies polynomial \(a\) and polynomial \(b\).

Parameters:

Name Type Description Default
polynomial_a VectorInt

polynomial's \(a\) coefficients.

 required
polynomial_b VectorInt

polynomial's \(b\) coefficients.

 required

Returns:

Type Description
VectorModInt

Coefficients array of polynomial \(a \cdot b\).
Source code in src/lbpqc/primitives/polynomial/modpoly.py 
101
102
103
104
105
106
107
108
109
110
111
112
113
@enforce_type_check
def mul(self, polynomial_a: VectorInt, polynomial_b: VectorInt) -> VectorModInt:
    r'''Multiplies polynomial $a$ and polynomial $b$.

    Args:
        polynomial_a: polynomial's $a$ coefficients.
        polynomial_b: polynomial's $b$ coefficients.

    Returns:
        Coefficients array of polynomial $a \cdot b$.
    '''

    return self.reduce(poly.mul(polynomial_a, polynomial_b))

reduce(polynomial)

Reduces the given polynomial to it's cannonical equivalence class in the ring, i.e. reduces polynomials' coefficients modulo modulus.

Parameters:

Name Type Description Default
polynomial VectorInt

Polynomial's coefficients array.

 required

Returns:

Type Description
VectorModInt

Array of coefficients reduced modulo modulus.
Source code in src/lbpqc/primitives/polynomial/modpoly.py 
28
29
30
31
32
33
34
35
36
37
38
39
@enforce_type_check
def reduce(self, polynomial: VectorInt) -> VectorModInt:
    r'''
    Reduces the given polynomial to it's cannonical equivalence class in the ring, i.e. reduces polynomials' coefficients modulo **modulus**.

    Args:
        polynomial: Polynomial's coefficients array.

    Returns:
        Array of coefficients reduced modulo **modulus**.
    '''
    return poly.trim(polynomial % self.modulus)

rem(polynomial_a, polynomial_b)

Computes only remainder of the euclidean divions of two ring's polynomials.

Parameters:

Name Type Description Default
polynomial_a VectorInt

.

 required
polynomial_b VectorInt

.

 required

Returns:

Type Description
VectorModInt

Remainder of the euclidean division.
Source code in src/lbpqc/primitives/polynomial/modpoly.py 
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
@enforce_type_check
def rem(self, polynomial_a: VectorInt, polynomial_b: VectorInt) -> VectorModInt:
    r'''Computes only remainder of the euclidean divions of two ring's polynomials.

    Args:
        polynomial_a: .
        polynomial_b: .

    Returns:
        Remainder of the euclidean division.
    '''

    if self.is_zero(polynomial_b): raise ZeroDivisionError("Can't divide by zero polynomial")

    _, r = self.euclidean_div(polynomial_a, polynomial_b)
    return r

sub(polynomial_a, polynomial_b)

Subtract polynomial \(b\) from polynomial \(a\).

Parameters:

Name Type Description Default
polynomial_a VectorInt

polynomial's \(a\) coefficients.

 required
polynomial_b VectorInt

polynomial's \(b\) coefficients.

 required

Returns:

Type Description
VectorModInt

Coefficients array of polynomial \(a - b\).
Source code in src/lbpqc/primitives/polynomial/modpoly.py 
85
86
87
88
89
90
91
92
93
94
95
96
97
98
@enforce_type_check
def sub(self, polynomial_a: VectorInt, polynomial_b: VectorInt) -> VectorModInt:
    r'''Subtract polynomial $b$ from polynomial $a$.

    Args:
        polynomial_a: polynomial's $a$ coefficients.
        polynomial_b: polynomial's $b$ coefficients.

    Returns:
        Coefficients array of polynomial $a - b$.
    '''


    return self.reduce(poly.sub(polynomial_a, polynomial_b))

to_monic(polynomial)

Reduces given polynomial to monic polynomial by multiplying it by scalar equal to modular multiplicative inverse of the highest power coefficient.

Parameters:

Name Type Description Default
polynomial VectorInt

.

 required

Returns:

Type Description
VectorModInt

Polynomial with leading coefficient equal to 1.
Source code in src/lbpqc/primitives/polynomial/modpoly.py 
160
161
162
163
164
165
166
167
168
169
170
171
172
173
@enforce_type_check
def to_monic(self, polynomial: VectorInt) -> VectorModInt:
    r'''Reduces given polynomial to monic polynomial by multiplying it by scalar equal to modular multiplicative inverse of the highest power coefficient.

    Args:
        polynomial: .

    Returns:
        Polynomial with leading coefficient equal to 1.
    '''

    leading_coeff = polynomial[self.deg(polynomial)]

    return self.reduce(modinv(leading_coeff, self.modulus) * polynomial)

This class implements operations over polynomial quotient ring $$ \frac{\mathbb{Z}_p[X]}{q(X)} $$ for given positive integer \(p\) and polynomial \(q\).

It's important to note that polynomials are represented as numpy's arrays with entries corresponding to coefficients in order of increasing powers.
Instance of PolyQuotientRing class represents the polynomials ring.
It's methods implements operations in this rings, but polynomials in their inputs and outputs are still numpy's arrays.

Attributes:

Name Type Description
poly_modulus VectorInt

.
int_modulus int

.
Zm ModIntPolyRing

Object representing \(\mathbb{Z}_p\) ring.
Source code in src/lbpqc/primitives/polynomial/polyqring.py 
  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
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
class PolyQuotientRing:
    r'''This class implements operations over polynomial quotient ring
    $$
    \frac{\mathbb{Z}_p[X]}{q(X)}
    $$
    for given positive integer $p$ and polynomial $q$.

    It's important to note that polynomials are represented as numpy's arrays with entries corresponding to coefficients in order of increasing powers.  
    Instance of `PolyQuotientRing` class represents the polynomials ring.  
    It's methods implements operations in this rings, but polynomials in their inputs and outputs are still numpy's arrays.

    Attributes:
        poly_modulus (VectorInt): .
        int_modulus (int): .
        Zm (ModIntPolyRing): Object representing $\mathbb{Z}_p$ ring.
    '''
    @enforce_type_check
    def __init__(self, poly_modulus: VectorInt, int_modulus: int) -> None:
        r'''Constructs the ring object for a given polynomial modulus and integer modulus.

        Args:
            poly_modulus: Coefficients array of polynomial modulus fot the ring. The $q(X)$ in $\frac{\mathbb{Z}_p[X]}{q(X)}$.
            int_modulus: Integer modulus for the ring. The $p$ in $\frac{\mathbb{Z}_p[X]}{q(X)}$.
        '''
        self.poly_modulus = poly_modulus
        self.int_modulus = int_modulus
        self.Zm = modpoly.ModIntPolyRing(int_modulus)


    @property
    def quotient(self):
        return self.poly_modulus


    @enforce_type_check
    def reduce(self, polynomial: VectorInt) -> VectorModInt:
        r'''Reduces the given polynomial $u$ to it's cannonical equivalence class in the ring,
        i.e. takes, the remainder of division $\frac{u}{q}$, where $q$ is polynomial modulus for the ring.  
        The division is performed in $\mathbb{Z}_p[X]$ ring.

        Args:
            polynomial: Polynomial's coefficients array.

        Returns:
            Coefficients array of polynomial that is the remainder of the Euclidean division.
        '''
        return self.Zm.rem(polynomial, self.poly_modulus)


    @enforce_type_check
    def add(self, polynomial_a: VectorInt, polynomial_b: VectorInt) -> VectorModInt:
        r'''Adds polynomial $a$ to polynomial $b$.

        Args:
            polynomial_a: polynomial's $a$ coefficients.
            polynomial_b: polynomial's $b$ coefficients.

        Returns:
            Coefficients array of polynomial $a + b$.
        '''

        return self.reduce(self.Zm.add(polynomial_a, polynomial_b))


    @enforce_type_check
    def sub(self, polynomial_a: VectorInt, polynomial_b: VectorInt) -> VectorModInt:
        r'''Subtract polynomial $b$ from polynomial $a$.

        Args:
            polynomial_a: polynomial's $a$ coefficients.
            polynomial_b: polynomial's $b$ coefficients.

        Returns:
            Coefficients array of polynomial $a - b$.
        '''

        return self.reduce(self.Zm.sub(polynomial_a, polynomial_b))

    @enforce_type_check
    def mul(self, polynomial_a: VectorInt, polynomial_b: VectorInt) -> VectorModInt:
        r'''Multiplies polynomial $a$ and polynomial $b$.

        Args:
            polynomial_a: polynomial's $a$ coefficients.
            polynomial_b: polynomial's $b$ coefficients.

        Returns:
            Coefficients array of polynomial $a \cdot b$.
        '''

        return self.reduce(self.Zm.mul(polynomial_a, polynomial_b))

    @enforce_type_check
    def inv(self, polynomial: VectorInt) -> VectorModInt:
        r'''For a given polynomial $v$, calculates it's multiplicative inverse in a ring.

        Args:
            polynomial: Polynomial's coefficients array.

        Returns:
            Coefficients array of polynomial $u$, such that $u \cdot v \equiv 1$.

        Raises:
            ValueError: When given polynomial is not an unit in the ring (it's not coprime with ring's polynomial modulus).

        '''

        if not self.Zm.coprime(polynomial, self.poly_modulus): raise ValueError("Inverse does not exists")

        gcd, u, _ = self.Zm.eea(polynomial, self.poly_modulus)

        c = integer_ring.modinv(gcd, self.int_modulus)

        return self.reduce(u * c)

__init__(poly_modulus, int_modulus)

Constructs the ring object for a given polynomial modulus and integer modulus.

Parameters:

Name Type Description Default
poly_modulus VectorInt

Coefficients array of polynomial modulus fot the ring. The \(q(X)\) in \(\frac{\mathbb{Z}_p[X]}{q(X)}\).

 required
int_modulus int

Integer modulus for the ring. The \(p\) in \(\frac{\mathbb{Z}_p[X]}{q(X)}\).

 required
Source code in src/lbpqc/primitives/polynomial/polyqring.py 
23
24
25
26
27
28
29
30
31
32
33
@enforce_type_check
def __init__(self, poly_modulus: VectorInt, int_modulus: int) -> None:
    r'''Constructs the ring object for a given polynomial modulus and integer modulus.

    Args:
        poly_modulus: Coefficients array of polynomial modulus fot the ring. The $q(X)$ in $\frac{\mathbb{Z}_p[X]}{q(X)}$.
        int_modulus: Integer modulus for the ring. The $p$ in $\frac{\mathbb{Z}_p[X]}{q(X)}$.
    '''
    self.poly_modulus = poly_modulus
    self.int_modulus = int_modulus
    self.Zm = modpoly.ModIntPolyRing(int_modulus)

add(polynomial_a, polynomial_b)

Adds polynomial \(a\) to polynomial \(b\).

Parameters:

Name Type Description Default
polynomial_a VectorInt

polynomial's \(a\) coefficients.

 required
polynomial_b VectorInt

polynomial's \(b\) coefficients.

 required

Returns:

Type Description
VectorModInt

Coefficients array of polynomial \(a + b\).
Source code in src/lbpqc/primitives/polynomial/polyqring.py 
56
57
58
59
60
61
62
63
64
65
66
67
68
@enforce_type_check
def add(self, polynomial_a: VectorInt, polynomial_b: VectorInt) -> VectorModInt:
    r'''Adds polynomial $a$ to polynomial $b$.

    Args:
        polynomial_a: polynomial's $a$ coefficients.
        polynomial_b: polynomial's $b$ coefficients.

    Returns:
        Coefficients array of polynomial $a + b$.
    '''

    return self.reduce(self.Zm.add(polynomial_a, polynomial_b))

inv(polynomial)

For a given polynomial \(v\), calculates it's multiplicative inverse in a ring.

Parameters:

Name Type Description Default
polynomial VectorInt

Polynomial's coefficients array.

 required

Returns:

Type Description
VectorModInt

Coefficients array of polynomial \(u\), such that \(u \cdot v \equiv 1\).

Raises:

Type Description
ValueError

When given polynomial is not an unit in the ring (it's not coprime with ring's polynomial modulus).
Source code in src/lbpqc/primitives/polynomial/polyqring.py 
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
@enforce_type_check
def inv(self, polynomial: VectorInt) -> VectorModInt:
    r'''For a given polynomial $v$, calculates it's multiplicative inverse in a ring.

    Args:
        polynomial: Polynomial's coefficients array.

    Returns:
        Coefficients array of polynomial $u$, such that $u \cdot v \equiv 1$.

    Raises:
        ValueError: When given polynomial is not an unit in the ring (it's not coprime with ring's polynomial modulus).

    '''

    if not self.Zm.coprime(polynomial, self.poly_modulus): raise ValueError("Inverse does not exists")

    gcd, u, _ = self.Zm.eea(polynomial, self.poly_modulus)

    c = integer_ring.modinv(gcd, self.int_modulus)

    return self.reduce(u * c)

mul(polynomial_a, polynomial_b)

Multiplies polynomial \(a\) and polynomial \(b\).

Parameters:

Name Type Description Default
polynomial_a VectorInt

polynomial's \(a\) coefficients.

 required
polynomial_b VectorInt

polynomial's \(b\) coefficients.

 required

Returns:

Type Description
VectorModInt

Coefficients array of polynomial \(a \cdot b\).
Source code in src/lbpqc/primitives/polynomial/polyqring.py 
85
86
87
88
89
90
91
92
93
94
95
96
97
@enforce_type_check
def mul(self, polynomial_a: VectorInt, polynomial_b: VectorInt) -> VectorModInt:
    r'''Multiplies polynomial $a$ and polynomial $b$.

    Args:
        polynomial_a: polynomial's $a$ coefficients.
        polynomial_b: polynomial's $b$ coefficients.

    Returns:
        Coefficients array of polynomial $a \cdot b$.
    '''

    return self.reduce(self.Zm.mul(polynomial_a, polynomial_b))

reduce(polynomial)

Reduces the given polynomial \(u\) to it's cannonical equivalence class in the ring, i.e. takes, the remainder of division \(\frac{u}{q}\), where \(q\) is polynomial modulus for the ring.
The division is performed in \(\mathbb{Z}_p[X]\) ring.

Parameters:

Name Type Description Default
polynomial VectorInt

Polynomial's coefficients array.

 required

Returns:

Type Description
VectorModInt

Coefficients array of polynomial that is the remainder of the Euclidean division.
Source code in src/lbpqc/primitives/polynomial/polyqring.py 
41
42
43
44
45
46
47
48
49
50
51
52
53
@enforce_type_check
def reduce(self, polynomial: VectorInt) -> VectorModInt:
    r'''Reduces the given polynomial $u$ to it's cannonical equivalence class in the ring,
    i.e. takes, the remainder of division $\frac{u}{q}$, where $q$ is polynomial modulus for the ring.  
    The division is performed in $\mathbb{Z}_p[X]$ ring.

    Args:
        polynomial: Polynomial's coefficients array.

    Returns:
        Coefficients array of polynomial that is the remainder of the Euclidean division.
    '''
    return self.Zm.rem(polynomial, self.poly_modulus)

sub(polynomial_a, polynomial_b)

Subtract polynomial \(b\) from polynomial \(a\).

Parameters:

Name Type Description Default
polynomial_a VectorInt

polynomial's \(a\) coefficients.

 required
polynomial_b VectorInt

polynomial's \(b\) coefficients.

 required

Returns:

Type Description
VectorModInt

Coefficients array of polynomial \(a - b\).
Source code in src/lbpqc/primitives/polynomial/polyqring.py 
71
72
73
74
75
76
77
78
79
80
81
82
83
@enforce_type_check
def sub(self, polynomial_a: VectorInt, polynomial_b: VectorInt) -> VectorModInt:
    r'''Subtract polynomial $b$ from polynomial $a$.

    Args:
        polynomial_a: polynomial's $a$ coefficients.
        polynomial_b: polynomial's $b$ coefficients.

    Returns:
        Coefficients array of polynomial $a - b$.
    '''

    return self.reduce(self.Zm.sub(polynomial_a, polynomial_b))

Function for constructing commonly used quotient rings.

Possible optinos:
- "-" || "X^N - 1": represents \(X^N - 1\) polynomial family.
- "+" || "X^N + 1": represents \(X^N + 1\) polynomial family.
- "prime" || "X^N - x - 1": represents \(X^N - X - 1\) polynomial family.

Parameters:

Name Type Description Default
p str

string representation/symbol of ring's polynomial modulus.

 required
N int

Degree of the polynomial modulus of the ring.

 required
q int

Integer modulus of the ring.

 required

Returns:

Type Description
PolyQuotientRing | None

None if the parameters were invalid else ring object.
Source code in src/lbpqc/primitives/polynomial/polyqring.py 
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
def construct_ring(p: str, N: int, q: int) -> PolyQuotientRing|None:
    r'''Function for constructing commonly used quotient rings.

     Possible optinos:  
        - "-" || "X^N - 1": represents $X^N - 1$ polynomial family.  
        - "+" || "X^N + 1": represents $X^N + 1$ polynomial family.  
        - "prime" || "X^N - x - 1": represents $X^N - X - 1$ polynomial family.


    Args:
        p: string representation/symbol of ring's polynomial modulus.
        N: Degree of the polynomial modulus of the ring.
        q: Integer modulus of the ring.

    Returns:
        None if the parameters were invalid else ring object.
    '''
    g = poly.zero_poly(N)
    match p:
        case "-" | "X^N - 1":
            g[[0, N]] =-1, 1
            pass
        case "+" | "X^N + 1":
            g[[0, N]] = 1, 1
            pass
        case "prime" | "X^N - x - 1":
            g[[0, 1, N]] = -1, -1, 1
        case _:
            return None

    return PolyQuotientRing(g, q)