Hi, thanks for the great questions! Not bothering at all, just happy that you are interested in our work!

**1. I can see that θ acts as multiplication by √−q as θ^2 = [-q], but I don’t see how τ acts as 1/√−q?**

It acts as 1/\sqrt{-q} **on the Weierstrass differential**. See Chapter III.5 in Silverman for more info on this (especially Corollary III.5.6).

**2. If I undestand correctly, SQISign uses only factors l and exponents e such that E[l^e] is in E(F_p^2)?**

Almost, but to be pedantic, SQISign uses only factors \ell and e such that either E[\ell^e] \subseteq E(\mathbb{F}_{p^2}), or \tilde{E}[\ell^e] \subseteq \tilde{E}(\mathbb{F}_{p^2}) for \tilde{E}, a quadratic twist of E over \mathbb{F}_{p^2}. This means that all computation can happen over \mathbb{F}_{p^2} though, because of the x-only arithmetic.

**3. Your approach enables to use pairs (l, e) where E[l^e] is in E(F_p^{2k}). This is beneficial primarily because then shorter isogeny chains can be used?**

Unfortunately, the length of the isogenies are still the same (they are decided by the size of the KLPT output. The reason to go to higher characteristic, is that when we are not allowed to choose the prime beforehand, E(\mathbb{F}_{p^2}), might be horrible to work with (e.g. almost prime order). So when working in general characteristic, forcing everything over \mathbb{F}_{p^2} is probably not feasible.

**4. I am not sure why k can be computed as: k = Mod(p, le).multiplicative_order()? This seems to guarantee that E[l^e] is in E(F_p^{2k})?**

Its actually also sometimes k = Mod(p, le).multiplicative_order()/2. The reason for this is as follows:

First of all, see Theorem 2. in the paper, which says that for the curves we are working with, we have

E(\mathbb{F}_{p^{2k}}) \simeq (\mathbb{Z}/(p^k \pm 1)\mathbb{Z})^2 and \tilde{E}(\mathbb{F}_{p^{2k}}) \simeq (\mathbb{Z}/(p^k \mp 1)\mathbb{Z})^2. This means we have E[\ell^e] \subseteq E(\mathbb{F}_{p^{2k}}) (or potentially over a twist), if and only if we have \ell^e \mid p^k \pm 1 \Leftrightarrow p^k \equiv \pm 1 \pmod{\ell^e}. From here, you can see that k = Mod(p, le).multiplicative_order() gives a sufficiently large k, and that sometimes we can get by with half of this too (for \ell \neq 2 its really just k = ceil(Mod(p, le).multiplicative_order()/2)).

**5. For Figure 1, it is mentioned that the intensity of the color corresponds to the probability of obtaining degree k. At first I thought this means for different p? So, for most p, we will get k = (l-1)/2? But probably not, as the description says it’s the number of units m such that k is minimal with m^k. What does minimal means in this context?**

Indeed, it is the probability of obtaining a degree k, for a “random” p, assuming that p behaves like a random unit mod \ell^e. Minimal refers to the answer in the previous section, the minimal k satisfying either p^{k} \equiv 1 \pmod{\ell^e}, or p^{k} \equiv -1 \pmod{\ell^e} (which again corresponds to working either over the curve or over a twist).

Hope these answers were okay