# Finding $f^{-1}$ in the YASHE keygen algorithm

In the YASHE (Yet Another Somewhat Homomorphic Encryption) algorithm, the beggining of the key generation step specifies:

Sample $\ f',g ← χ_{key}$ and let $\ f = [tf' + 1]_q$.

If $\ f$ is not invertible modulo $q$, choose a new $\ f'$.

Compute the inverse $\ f^{−1} ∈ R$ of $\ f$ modulo $q$ and set $h = [t\ g\ f^{−1}]_q$.

The previous section of the algorithm descibres what each of these parameters are

Given the security parameter $λ$, fix a positive integer $d$ that determines $R$, moduli $q$ and $t$ with $1 < t < q$, distributions $χ_{key}$, $χ_{err}$ on $R$, and an integer base $w > 1$.

How can you tell if:

1. $f$ is invertible?

and if so

1. what $\ f^{-1}$ is?
• This might be more suited for math stack exchange, the context is crypto but the question itself is pure math i.e. how can I tell if a polynomial has an inverse in a field, and if it does how do I compute it. These answers may help. – puzzlepalace Jul 1 '16 at 23:11

To invert a polynomial in the quotient ring $F_q[X]/(\phi(X))$ there are two cases:

-> Either $\phi$ is irreducible modulo $q$, in which case every polynomial is inversible

-> Either $\phi$ is not irreducible, and one reasons with the Chinese remainder theorem.

In the first case, to find the inverse, just use Extended Euclides to find two polynomials $U,V$ such that

$$Uf+V\phi=1$$

(I'll let you deduce why $gcd(\phi,f)=1$) and therefore $Uf=1 \in R$.

For the YASHE parameters, $\phi$ is not irreducible, and therefore a quick answer to your question is

$\mbox{ if } gcd(f,\phi)\neq 1$ then $\phi$ is not invertible, if $gcd(f,\phi)= 1$ use Euclides as before.