How to find irreducible polynomial for Barreto-Naehrig curves?

As described in this paper(section 3) to implement pairing on Barreto-Naehrig curves. The prime in their case is $p=82434016654300679721217353503190038836571781811386228921167322412819029493183$ and to implement the pairing it is important to find an irreducible polynomial of the form $W^6-\xi$ in $\mathbb{F}_{P^{2}}$ where $\xi \in \mathbb{F}_{P^{2}}$. However, I can not understand how to find such $\xi$. I have written some scripts in Magma to find such $\xi$ but not successful.Also in that paper they have mentioned that there are some properties of the prime $p$ which is useful in finding such $\xi$ but I can't understand how to use them? Can someone please tell me how to find such irreducible polynomials?

• Select first a element $\beta \in F_p$ which is not a Quadratic Residue. By construction $X^2+\beta$ is irreducible. Then look at table 1 which give the tower construction. – Robert NACIRI Oct 6 '16 at 18:13
• @RobertNACIRI Are you sure that isn't an answer? – Maarten Bodewes Oct 6 '16 at 21:10
• @MaartenBodewes in $F_p$ there are $\frac{p-1}{2}$ quadratic Residues and $\frac{p-1}{2}$ Non-quadratic Residues. Depending on p you can caracterize them easily. If $\beta \in QNR(p)$ then $X^2-\beta$ is irreducible in $F_p$. Then follow the construction indicated in table 1 of the article. (I've evaluated this system in 2012 for limited ressources systems such Smart Cards). And it's run. Hope it's more clear.How to select such primes. Look for criterias for which $-2 \in NQR(p)$ – Robert NACIRI Oct 6 '16 at 21:26
• @MaartenBodewes Look here for instance en.wikipedia.org/wiki/Quadratic_residue ... if p=1, 3 mod 8 then $p \in QR(p)$ and converselly if not then ... Conclude – Robert NACIRI Oct 6 '16 at 21:33
• @RobertNACIRI I wasn't asking for a clarification :) I just had the idea that you were close to answering in the comments and I was hoping to trigger you to write an answer instead. Note that I'm not the original asker. – Maarten Bodewes Oct 6 '16 at 21:36

I am using Pari/GP as a calculator. In order to keep the presentation small, I will not use the $p$ you mentioned, but a toy value $p=31$, which fulfils all requirements from the paper.

First lets define p:

p= 31


Then we have to define the finite field $GF(p^2)$ via the defining (irreducible) polynomial $y^2- \beta$, i.e. $y^2+2$:

GFp2 = Mod (y^2+2, p)


Now we define $\xi$:

xi = -1 - y


( Please note that $\sqrt \beta = y$ by the defining polynomial of $GF(p^2)$ )

Now let Pari check that $x^6- \xi$ is irreducible in $GF(p^2)$:

lift(factorff (x^6-xi, p, GFp2))


Pari responds as

[Mod(1, 31)*x^6 + (Mod(1, 31)*y + Mod(1, 31)) 1]


This says that the polynomial is irreducible.

(The "lift" call is only used to make the output more readable )

As a final test, show that $x^6 - \xi^2$ factors:

lift(factorff (x^6-(xi*xi), p, GFp2))


Pari responds as:

[  Mod(1, 31)*x^3 + (Mod(1, 31)*y + Mod(1, 31)) 1]

[Mod(1, 31)*x^3 + (Mod(30, 31)*y + Mod(30, 31)) 1]


Mathematically, this means: $$x^6- \xi^2 = (x^3+ \sqrt \beta+1)(x^3-\sqrt\beta-1)$$

• Thank you very much for your help. However, if I want to check the irreducibility in the field how can I do it? I tried > GFp6=Mod(1,GFp2)*x^3-xi, xip=x; lift(factoroff(z^2-xip)); but it does not work this way. – Rick Oct 10 '16 at 9:00