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 &lt; t &lt; q$, distributions $χ_{key}$, $χ_{err}$ on
$R$, and an integer base $w &gt; 1$.

How can you tell if:

$f$ is invertible?

and if so

what $\ f^{-1}$ is?
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.