# Is inverse polynomial in a finite field NP hard?

In ECC we have: if we know $$G$$ and $$P=kG$$, it is very difficult to find $$k$$. I wonder whether or not in NTRUEncrypt: if we know $$h$$ and $$P=rh$$, it is difficult to find $$r$$?

• Aren't inverses in a field trivial since the order is known? $a^{-1} = a^{q-1}$, which you can compute in $\log(q)$ time Jan 7 at 17:27
• @bmm6o: you are right in a field of known order. I think the extended GCD allows to perform that in a field of unknown order. But as far as I understand (which is, not much), NTRUEncrypt does not operate in a field. If I'm right, that makes the title of the question wrong. Also: is the question to find $r$, or to find an $r$, or the/an $r$ with coefficient all in the set $\{-1,0,1\}$ (which I think is what breaks NTRUEncrypt)?
– fgrieu
Jan 7 at 17:45
• Since you know the maths angle please edit the question stating the mathematical question precisely for everyone's benefit. NTRU is not exactly the best known cryptosystem out there. Jan 7 at 20:03
• NTRUEncrypt works modulo a polynomial over GF(q) (typically $x^n\pm1$). As @fgrieu said, polynomial GCD allows to invert elements easily. There can be non-invertible elements though, but it's rather rare (but non-negligible). There is definitely no hardness here. Jan 7 at 20:04