Prove correctness of algorithm in §3.3

[defeo]

Page 18, 3.3: High degree prime power: Given the claim that the algorithm in this section was not published elsewhere, proof of correctness should be given. 1) Explain why k(zeta)/k is of degree s. 2) Explain why the v^d-th roots of eta exist in k(zeta) (write explicitly that q^s=1 \pmod{v^t} imply q^{s*v^d}=1 \pmod{v^{t+d}}) 3) It is not sufficient for eta to be a non v-th power. for theta to belong to the subgroup of order v^{d+t}. Instead it must be requested that eta be of order exactly v^t, which can be achieved by taking the u power of a non v-th power. 4) It should be explained why k(zeta)=Fq(theta). 5) It should be explained why the conjugacy class of theta is unique, and thus why alpha -> beta is an isomorphism.

[defeo]

@javad-doliskani, your fix in aab2b9a8594899ede67ad6f0ece641a102e83314 says

we obtain a random generator η of the unique subgroup of order v^t in F_q(ζ)* by finding a non v-th power and raising it to the power of u.

However there is not such raising to the power u in Algorithm 4 (and that would add a sM(s)log q to the complexity, I believe). Which is true?

[defeo]

Also, shouldn't the case v=2 be handled slightly differently?

[jake-doliskani]

I forgot to remove the "raising it to the power of u" part, because we don't necessarily need a generator of the subgroup. We just need a non-v-th power.

[defeo]

That's what I thought. Can you fix it, please?

[jake-doliskani]

Sure. For the case v = 2, by handling differently you mean in taking roots, i.e., square roots?

[defeo]

Looking at Shoup's paper, I'm just guessing that some 2 become 4 then. Didn't really check the details, but I guess we can just say that when v=2 the generalization is straightforward, cf. Shoup. It'd be good to at least be sure that's really straightforward.

[jake-doliskani]

Which paper? 1993?

[defeo]

1990, the one you cite to justify that the trace generates the field. ​​

[jake-doliskani]

I added the 1993 as well right now. In Algorithm 13 it references the 1990 paper for the proof. He talks about r = 2 separately but I don't think we need to do the same. Take a look!

[defeo]

Have you pushed?

[jake-doliskani]

No. I'll push when I go back to my desktop at IQC.

[defeo]

So, this sentence is false when v=2:

It follows from q^s = 1 mod v^t that q^rs - 1 = ũv^(t+d) where gcd(ũ, v) = 1.

Take q = 7, d = 2. However, I don't think you need gcd(ũ, v) = 1 for the algorithm to run, so the fix is easy.

Or, more generally, p = -1 mod 4, d=whatever.

Can you double check?

[defeo]

Also, is this sentence really needed?

Then θ₁ is a non-v-th power in k(ζ)*.

It feels dangling, and I don't see what use we have for it. In particular, this is false when v=2.

[jake-doliskani]

Correct, the appropriate sentence would be: It follows from v^t | q^s - 1 that v^{t + d} | q^{rs} - 1.

[defeo]

Yup, that should address exactly what the reviewer asked for:

Explain why the v^d-th roots of eta exist in k(zeta) (write explicitly that q^s=1 \pmod{v^t} imply q^{s*v^d}=1 \pmod{v^{t+d}})

[jake-doliskani]

Done.