# in NTRU, can g be recovered given f and h?

The NTRU key generation involves polynomials and their arithmetic in polynomial rings, which is a bit different from arithmetic in modular integers. In the NTRU cryptosystem, the public key $$h$$ is computed as:

$$h=g⋅F_q \bmod q \tag{1}\label{r1}$$

where $$g$$ is a chosen polynomial, $$F_q$$​ is the modular inverse of $$f$$ modulo $$q$$ in the ring of polynomials, and $$q$$ is a modulus, i.e.:

$$f^{-1} = F_q \bmod q \tag{2}\label{r2}$$

So, $$F_q​$$ is not simply the multiplicative inverse of $$f$$ in modular arithmetic but the modular inverse in the ring of polynomials modulo $$q$$. So, while

$$F_q ⋅ f \equiv 1 \bmod q \tag{3}$$

in the polynomial ring, deriving $$F_q$$​ from $$f$$ is not straightforward and involves polynomial arithmetic, not integer arithmetic. At least with NTRUEncrypt it works so that the $$F_q$$ factor in $$h$$ cancels out with $$f$$.

Regarding my question about deriving $$g$$ from $$h$$ and $$f$$, from (\ref{r1}) follows:

$$g \equiv h ⋅ F_q^{−1} \bmod q \tag{4}$$

And with (\ref{r2}), in theory, we could compute $$g$$ as

$$g \equiv h ⋅ f \bmod q \tag{5}\label{r5}$$

My initial question now boils down to the clarification if this $$g$$ (\ref{r5}) can actually be expected to be identical to the $$g$$ (\ref{r1}) initially used in the key-pair generation - or could it also be "somehow equivalent" or even "one of many solutions"?

Clearly, equation (5) in your question determines $$g$$ uniquely up to the possible addition of a multiple of $$q$$. But $$g$$ also has the property of having small coefficients (much smaller than $$q/2$$ in absolute value; depending on the version of NTRU you're looking at, possibly at most $$1$$ in absolute value). Both conditions together uniquely determine $$g$$: each coefficient is going to be equal to the unique integer of absolute value $$ congruent mod $$q$$ to the corresponding coefficient of $$h\cdot f$$.
• To clarify further: the size of the coefficients of $g$ depends on the specific version of NTRU, but the fact that they are small compared to $q/2$ is always satisfied, so the answer is always yes. Oct 14, 2023 at 13:59
• thanks for your hint to SageMath. I'll try it. in the meanwhile, I could test the Wikipedia example with Wolfram Mathematia:  f = -1 + x + x^2 - x^4 + x^6 +x^9 - x^10; g = -1 + x^2 +x^3 + x^5 -x^8 - x^10; h = 8 - 7x - 10x^2 - 12x^3 + 12x^4 - 8x^5 + 15x^6 - 13x^7 + 12x^8 - 13x^9 + 16x^10; fh = Expand[f*h]; fhModN = PolynomialMod[fh, {x^11-1}]; fhMod4 = PolynomialMod[fhModN, 4]; fhMod4CL = CoefficientList[fhMod4, x]; g2CL = Reverse[If[# != 0, # - 2, #] & /@ fhMod4CL]; g2 = Expand[FromDigits[g2CL, x]]; Print[Equivalent[ g2, g]];  -> True NumPy worked, too, btw. Oct 15, 2023 at 23:05