First, thanks for the really great talk yesterday!
One question - you mention in the paper that the algorithm to construct supersingular elliptic curves over Fp together with explicitly known effective endomorphism ring (for any p) was previously known, but you optimized one crucial subroutine - can you point me to this subroutine?
Hi, thanks for the question and the kind words 
The optimized part is related to finding the explicit endomorphism corresponding to the quaternion i. The details can be found in Section 3.1, page 10 (the paragraph beginning with “as q is tiny, one can find…”).
The corresponding code can be found at deuring/broker.py at main · friends-of-quaternions/deuring · GitHub (the function “starting_curve(F)”. 
Thank you very much!
I actually have some further questions. I don’t want to bother you too much, so I would be grateful even if you can just refer to some literature that cover the questions.
I can see that θ acts as multiplication by √−q as θ^2 = [-q], but I don’t see how τ acts as 1/√−q?
If I undestand correctly, SQISign uses only factors l and exponents e such that E[l^e] is in E(F_p^2)?
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?
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})?
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?
Sorry for that many questions 
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
Wonderful! Thank you very much!
No problem at all