Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm going through Smart and Vercauteren's paper "Fully Homomorphic SIMD operations" and had a question about some notation used in the paper.

In section 2 of the above it is stated that for each monic polynomial $F(X) \in \mathbb{F}_2[X]$ of degree $N$ that splits into $r$ distinct irreducible factors of degree $d = N/r$ viz. $F(X)=\prod_{i = 1}^{r}F_i(X)$, the polynomial $F(X)$ defines the field $\mathbb{K} = \mathbb{Q}(\theta) = \mathbb{Q}[X]/(F)$ where $\theta$ is a fixed root in the algebraic closure of the base field.


  1. Should it not be stated that $\mathbb{Q}(\theta) \cong \mathbb{Q}[X]/(F)$ rather than $\mathbb{Q}(\theta) = \mathbb{Q}[X]/(F)$ ?

  2. I assume that $\theta$ is just a root of $F(X)$ in the extension $\mathbb{Q}/\mathbb{F}_2$?

  3. In the expression $\mathbb{Q}[X]/(F)$, is what is being referred to the
    quotient of $\mathbb{Q}[X]$ by the ideal generated by $F(X)$, i.e. $\mathbb{Q}[X]/(F(X))$?

share|improve this question
Regarding question (2), I would restate it as: Is what is meant by $\mathbb{Q}(\theta) = \mathbb{Q}[X]/(F)$ the field $\mathbb{Q}(\theta)$ created by adjoining $\theta$, a root of $F(X)$ in the algebraic closure of $\mathbb{F}_2$, to $\mathbb{Q}$? – Rohit Khera Apr 4 '14 at 22:37
up vote 5 down vote accepted
  1. Yes, technically this is an isomorphism, so $\cong$ should be used. The isomorphism is question identifies $\theta$ with $X$.

  2. Not quite (for the original question or your restatement). The notation $\mathbb{Q}(\theta)$ means adjoining $\theta$, a root of $F(X)$ in the algebraic closure of $\mathbb{Q}$ (namely, $\mathbb{C}$), to $\mathbb{Q}$. The finite field $\mathbb{F}_2$ has nothing to do with it. (And I think $\mathbb{Q}/\mathbb{F}_2$ is meaningless, since there is no field embedding of $\mathbb{F}_2$ into $\mathbb{Q}$.)

  3. Yes. Such a structure is more commonly known as a number field (i.e., a finite dimensional field extension of the rationals).

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.