Suppose $p$ is an odd prime and $a$ is a quadratic residue modulo $p$. Cipolla's algorithm shows that $b:=x^{(p+1)/2}\bmod{(x^2-tx+a)}$ such that $b^2=a$ for some irreducible polynomial $x^2-tx+a\in\mathbb{F}_p[x]$.↵
↵
I don't know how to prove this properly. If there are any mistakes or typos, please let me know, thanks! Let $\alpha$ be a zero of $x^2-tx+a$, $\mathbb{F}_p(\alpha):=\lbrace a_0+a_1\alpha :a_0,a_1\in\mathbb{F}_p\rbrace$, and let $\beta$ be a zero of $x^2-(t^2-4a)$, $\mathbb{F}_p(\beta):=\lbrace a_0+a_1\beta :a_0,a_1\in\mathbb{F}_p\rbrace$. We may easily find homomorphisms between $\mathbb{F}_p(\alpha)$ and $\mathbb{F}_p(\beta)$. So I think we just need to show that $((t+\beta )/2)^{p+1}=a$.↵
↵
A lot of blogs show that $(t+\beta)^p=t-\beta$ according to binomial theorem and Fermat's little theorem, so↵
↵
$$↵
\begin{aligned}↵
((t+\beta)/2)^{p+1}&=(t+\beta)(t-\beta)/4\\↵
&=(t^2-\beta^2)/4\\↵
&=a↵
\end{aligned}↵
$$↵
↵
Bostan and Mori's [paper](https://arxiv.org/abs/2008.08822) shows that the computation of $x^n$ modulo a monic polynomial sometimes is equivalent to the computation of one term of a rational function $P(x)/Q(x)$ where $P,Q$ are both polynomials and $\deg(P(x))\lt \deg(Q(x))$.↵
↵
We have↵
↵
$$↵
b=\left[x^{(p+1)/2}\right]\dfrac{1-tx}{1-tx+ax^2}↵
$$↵
↵
and↵
↵
$$↵
\left[x^n\right]\dfrac{k_0+k_1x}{1+k_2x+k_3x^2}=↵
\begin{cases}↵
\left[x^{(n-1)/2}\right]\dfrac{k_1-k_0k_2+k_1k_3x}{1+(2k_3-k_2^2)x+k_3^2x^2}&\text{if }n\bmod 2=1\\↵
\left[x^{n/2}\right]\dfrac{k_0+(k_0k_3-k_1k_2)x}{1+(2k_3-k_2^2)x+k_3^2x^2}&\text{otherwise}↵
\end{cases}↵
$$↵
↵
This may save some multiplications.↵
↵
[submission(Library Checker)](https://judge.yosupo.jp/submission/73636)↵
↵
Actually, the initial value of $k_1$ does no matter to the result. So we could mainly focus on the computation of one term of the inverse of formal power series. I don't know if we could do better.
↵
I don't know how to prove this properly. If there are any mistakes or typos, please let me know, thanks! Let $\alpha$ be a zero of $x^2-tx+a$, $\mathbb{F}_p(\alpha):=\lbrace a_0+a_1\alpha :a_0,a_1\in\mathbb{F}_p\rbrace$, and let $\beta$ be a zero of $x^2-(t^2-4a)$, $\mathbb{F}_p(\beta):=\lbrace a_0+a_1\beta :a_0,a_1\in\mathbb{F}_p\rbrace$. We may easily find homomorphisms between $\mathbb{F}_p(\alpha)$ and $\mathbb{F}_p(\beta)$. So I think we just need to show that $((t+\beta )/2)^{p+1}=a$.↵
↵
A lot of blogs show that $(t+\beta)^p=t-\beta$ according to binomial theorem and Fermat's little theorem, so↵
↵
$$↵
\begin{aligned}↵
((t+\beta)/2)^{p+1}&=(t+\beta)(t-\beta)/4\\↵
&=(t^2-\beta^2)/4\\↵
&=a↵
\end{aligned}↵
$$↵
↵
Bostan and Mori's [paper](https://arxiv.org/abs/2008.08822) shows that the computation of $x^n$ modulo a monic polynomial sometimes is equivalent to the computation of one term of a rational function $P(x)/Q(x)$ where $P,Q$ are both polynomials and $\deg(P(x))\lt \deg(Q(x))$.↵
↵
We have↵
↵
$$↵
b=\left[x^{(p+1)/2}\right]\dfrac{1-tx}{1-tx+ax^2}↵
$$↵
↵
and↵
↵
$$↵
\left[x^n\right]\dfrac{k_0+k_1x}{1+k_2x+k_3x^2}=↵
\begin{cases}↵
\left[x^{(n-1)/2}\right]\dfrac{k_1-k_0k_2+k_1k_3x}{1+(2k_3-k_2^2)x+k_3^2x^2}&\text{if }n\bmod 2=1\\↵
\left[x^{n/2}\right]\dfrac{k_0+(k_0k_3-k_1k_2)x}{1+(2k_3-k_2^2)x+k_3^2x^2}&\text{otherwise}↵
\end{cases}↵
$$↵
↵
This may save some multiplications.↵
↵
[submission(Library Checker)](https://judge.yosupo.jp/submission/73636)↵
↵
Actually, the initial value of $k_1$ does no matter to the result. So we could mainly focus on the computation of one term of the inverse of formal power series. I don't know if we could do better.
