$$ \text{求}\sqrt{a}\left( mod\,\,p \right) ,\text{其中}p\text{是奇素数。} \\ \text{令}p-1=2^s\times t,\text{其中}t\text{是奇数。} \\ \text{如果}s=\text{1，且}a\text{是模}p\text{的二次剩余,那么}\sqrt{a}=\sqrt{a^{\frac{p-1}{2}}\times a}=\sqrt{a^t\times a}=a^{\frac{t+1}{2}},\text{又因为}t\text{为奇数，所以可以直接计算得到}\sqrt{a} \\ \text{对于}s>\text{1,设}x_{s-1}=a^{\frac{t+1}{2}} \\ a^{\frac{p-1}{2}}=a^{2^{s-1}\times t}=\left( a^{-1}\times \left( a^{\frac{t+1}{2}} \right) ^2 \right) ^{2^{s-1}}=\left( a^{-1}\times x_{s-1}^{2} \right) ^{2^{s-1}}=1\left( a\text{是模}p\text{意义下的二次剩余} \right) \\ \text{所以}a^{-1}\times x_{s-1}^{2}\text{是模}p\text{意义下的}2^{s-1}\text{次单位根。} \\ \text{我们的目标是计算出模}p\text{意义下的}2^0\text{单位根，即计算出}a^{-1}\times x_{0}^{2}=\text{1,在这个同时我们也可以计算出}x_0,\text{进而得到方程解。} \\ \text{设}e_k\text{为模}p\text{意义下的}2^k\text{次单位根，则有} \\ e_{s-1}=a^{-1}\times x_{s-1}^{2} \\ \text{假设现在我们知道了}e_{s-k}\text{和}x_{s-k}\text{，如果} \\ e_{s-k}^{\begin{array}{c} 2^{s-k-1}\\ \end{array}}\equiv 1\left( mod\,\,p \right) ,\text{那么}e_{s-k-1}=e_{s-k},x_{s-k-1}=x_{s-k} \\ \text{否则，如果}e_{s-k}^{\begin{array}{c} 2^{s-k-1}\\ \end{array}}\equiv -1\left( mod\,\,p \right) \\ \text{即}\left( a^{-1}\times x_{s-k}^{2} \right) ^{2^{s-k-1}}\equiv -\text{1,那么我们显然需要求一个数}q,\text{使得} \\ \left( a^{-1}\times \left( qx_{s-k} \right) ^2 \right) ^{2^{s-k-1}}\equiv 1 \\ \text{整理后得}q^{2^{s-k}}\equiv -1 \\ \text{寻找一个模}p\text{意义下的非二次剩余}b,\text{则有}b^{\frac{p-1}{2}}\equiv -1 \\ b^{2^{s-1}t}\equiv -1 \\ b^{2^{k-1}t2^{s-k}}\equiv -1 \\ \left( b^{2^{k-1}t} \right) ^{2^{s-k}}\equiv -\text{1,故}q=b^{2^{k-1}t} \\ \text{所以}x_{s-k-1}=x_{s-k}\times q \\ \text{一直递推到}x_0\text{即可。} \\ $$

模数固定为998244353: