# Revision history [back]

### q-polynomial and Rank Decoding Problem

Dear all,

For the Rank Decoding (RD) problem: Given $y=mG+e$ , random row full-rank matrix $G = (g_{ij})\in GF({q^m})^{k \times n}$, one solves $m$ and $e$.

Here $m=(m_1,m_2,...,m_k)\in GF({q^m})^{k}$, $y = (y_1,y_2,\ldots,y_n)$, all coordinates of $e=(e_1,e_2,...,e_n)\in GF({q^m})^{n}$ of weight $r$ lie in a subspace of $GF({q^m})$ over $GF({q})$ of dimension $r$.

Since all coordinates of $e=(e_1,e_2,...,e_n)$ of weight $r$ lie in a subspace of $GF({q^m})$ over $GF({q})$ of dimension $r$, then there exists a unique monic $q$-polynomial $P(x) = \sum_{l=0}^{r}p_lx^{q^l}$ of $q$-degree $r$ such that

$\forall \ j \in {1...n}, \qquad P\left(y_j-\sum_{i=1}^{k}m_ig_{ij}\right)= \sum_{l=0}^{r}\left(p_ly_j^{q^l}- \sum_{i=1}^{k}p_lm_i^{q^l}g_{ij}^{q^l}\right)= P\left(e_j\right) = 0$.

This gives a equations system with $n$ equations and unknowns $p_l$ and $m_i$.

To solve the RD problem, one needs to solve $p_l$ or $m_i$. For this purpose, one views $(r+1)(k+1)-1$ monomials in $p_l$ and $m_i$ as unknowns:

1. $kr$ terms of the form: $p_l m_i^{q^l}$;
2. $k$ terms of the form: $m_i^{q^r}$ due to $p_r$ = 1;
3. $r$ terms of the form: $p_j$.

I want to know how to construct this equations system with $n$ equations and $(r+1)(k+1)-1$ unknowns (monomials) by constructing a q-polynomial?

Thanks for the idea of all!

### q-polynomial and Rank Decoding Problem

Dear all,

For the Rank Decoding (RD) problem: Given $y=mG+e$ , random row full-rank matrix $G = (g_{ij})\in GF({q^m})^{k \times n}$, one solves $m$ and $e$.

Here $m=(m_1,m_2,...,m_k)\in GF({q^m})^{k}$, $y = (y_1,y_2,\ldots,y_n)$, (y_1,y_2,\ldots,y_n)\in GF({q^m})^{n}$, all coordinates of$e=(e_1,e_2,...,e_n)\in GF({q^m})^{n}$of weight$r$lie in a subspace of$GF({q^m})$over$GF({q})$of dimension$r$. Since all coordinates of$ e=(e_1,e_2,...,e_n)$of weight$r$lie in a subspace of$GF({q^m})$over$GF({q})$of dimension$r$, then there exists a unique monic$q$-polynomial$P(x) = \sum_{l=0}^{r}p_lx^{q^l}$of$q$-degree$r$such that$ \forall \ j \in {1...n}, \qquad P\left(y_j-\sum_{i=1}^{k}m_ig_{ij}\right)= \sum_{l=0}^{r}\left(p_ly_j^{q^l}- \sum_{i=1}^{k}p_lm_i^{q^l}g_{ij}^{q^l}\right)= P\left(e_j\right) = 0$. This gives a equations system with$n$equations and unknowns$p_l$and$m_i$. To solve the RD problem, one needs to solve$p_l$or$m_i$. For this purpose, one views$(r+1)(k+1)-1$monomials in$p_l$and$m_i$as unknowns: 1.$kr$terms of the form:$p_l m_i^{q^l}$; 2.$k$terms of the form:$m_i^{q^r}$due to$p_r$= 1; 3.$r$terms of the form:$p_j$. I want to know how to construct this equations system with$n$equations and$(r+1)(k+1)-1\$ unknowns (monomials) by constructing a q-polynomial?

Thanks for the idea of all!