algorithmpolynomial-mathinversentruencrypt# Algorithm for computing the inverse of a polynomial

I'm looking for an algorithm (or code) to help me compute the inverse a polynomial, I need it for implementing NTRUEncrypt. An algorithm that is easily understandable is what I prefer, there are pseudo-codes for doing this, but they are confusing and difficult to implement, furthermore I can not really understand the procedure from pseudo-code alone.

Any algorithms for computing the inverse of a polynomial with respect to a ring of truncated polynomials?

Solution

I work for Security Innovation, which owns NTRU, so I'm glad to see this interest.

The IEEE standard 1363.1-2008 specifies how to implement NTRUEncrypt with the most current parameter sets. It gives the following specifications to invert polynomials:

Division:

Inputs are a and b, two polynomials, where b is of degree N-1 and b_N is the leading coefficient of b. Outputs are q and r such that a = q*b + r and deg(r) < deg(b). r_d denotes the coefficient of r of degree d, i.e. the leading coefficient of r.

```
a) Set r := a and q := 0
b) Set u := (b_N)^–1 mod p
c) While deg r >= N do
1) Set d := deg r(X)
2) Set v := u × r_d × X^(d–N)
3) Set r := r – v × b
4) Set q := q + v
d) Return q, r
```

Here, r_d is the coefficient of r of degree d.

Extended Euclidean Algorithm:

```
a) If b = 0 then return (1, 0, a)
b) Set u := 1
c) Set d := a
d) Set v1 := 0
e) Set v3 := b
f) While v3 ≠ 0 do
1) Use the division algorithm (6.3.3.1) to write d = v3 × q + t3 with deg t3 < deg v3
2) Set t1 := u – q × v1
3) Set u := v1
4) Set d := v3
5) Set v1 := t1
6) Set v3 := t3
g) Set v := (d – a × u)/b [This division is exact, i.e., the remainder is 0]
h) Return (u, v, d)
```

Inverse in Z_p, p a prime:

```
a) Run the Extended Euclidean Algorithm with input a and (X^N – 1). Let (u, v, d) be the output, such that a × u + (X^N – 1) × v = d = GCD(a, (X^N – 1)).
b) If deg d = 0, return b = d^–1 (mod p) × u
c) Else return FALSE
```

Inverse in Z_p^e / (M(X), p a prime, M(X) a suitable polynomial such as X^N-1

```
a) Use the Inversion Algorithmto compute a polynomial b(X) ε R[X] that gives an inverse of a(X) in (R/pR)[X]/(M(X)). Return FALSE if the inverse does not exist. [The Inversion Algorithm may be applied here because R/pR is a field, and so (R/pR)[X] is a Euclidean ring.]
b) Set n = p
c) While n <= e do
1) b(X) = p × b(X) – a(X) × b(X)^2 (mod M(X)), with coefficients computed modulo p^n
2) Set n = p × n
d) Return b(X) mod M(X) with coefficients computed modulo p^e.
```

If you're doing a full implementation of NTRU you should see if you can get your institution to buy 1363.1, as raw NTRU encryption isn't secure against an active attacker and 1363.1 describes message processing techniques to fix that.

(Update 2013-04-18: Thanks to Sonel Sharam for spotting some errors in the previous version)

- Why is my python code so slow (leetcode)?
- Why is heap slower than sort for K Closest Points to Origin?
- Minimum Time to Perform One Task of Each Category (with Different Release Times)
- Worst case in Max-Heapify - How do you get 2n/3?
- How to check whether a matrix is a framed matrix?
- Identify connected subnetworks, constrained by edge attributes
- Is there a way to generate a random variate from a non-standard distribution without computing CDF?
- Most efficient way to calculate VWAP(VOLUME WEIGHTED AVERAGE PRICE) for trading algorithm
- How to find and replace all occurrences of a substring in a string?
- How to find kth smallest element in a BST when the tree may be modified frequently?
- Calculate distance between two latitude-longitude points? (Haversine formula)
- How does one make a Zip bomb?
- How to calculate the midpoints of each triangle edges of an icosahedron
- Calculate circular shift pairs in a list
- Uniformly randomly generate a vector of k unsigned ints that sums to N
- Bin packing with fixed number of bins of varying capacities and item-to-bin compatibility constraints
- Mapping elementwise Tuple Using Template Function
- Find the longest prefix for a table of tokenized strings
- Count Unguarded Cells in the Grid (recursion)
- Kalman Filter Prediction Implementation
- My ALV Tree balance factors calculate incorrectly
- Infix to postfix left one parentheses at the end when expression is fully enclosed
- C++ quick sort algorithm
- Merge Sort Function not working when size of vector is not 2^n
- Given an array a of n integers, and q queries, for each value from index l to index r, add x to the value
- Count mountain arrays
- Get the number of all possible combinations that give a certain product
- getting TLE in leetcode question 212- word search 2 using backtrcaking even after pruning, how do i optimize it more
- Maximizing the sum of Adjacent sum in an array
- Weighted random selection from array