本节讨论模平方根的计算问题.设a是模n的二次剩余，根据模n分以下几种情况讨论计算a mod n的平方根.

设n是一个奇素数，$ a \in Z_n^ * $，且$\left( {\frac{a}{n}} \right) = 1 $.首先考虑特殊情况，当p≡3mod n时，$ \left( {\frac{{p + 1}}{4}} \right)$是整数

所以${a^{\frac{{p + 1}}{4}}} $是a模n的一个平方根.一般情况下，设$p - 1 = {2^h}m $，其中m为奇数，${\rm{ }}a \in {(Z_n^ * )^2}, \gamma \in Z_n^ * \backslash {(Z_n^ * )^2} $.对任意的$ \delta \in Z_n^ * , {\rm{ }}{\delta ^m}$的阶整除2^h；因为${a^{{2^{h - 1}}m}} = 1 $，所以a^m的阶整除2^h-1；而${\gamma ^{{2^{h - 1}}m}} = - 1 $，则γ^m的阶恰好为2^h.生成元为γ^m的群是$ Z_n^ * $阶为2^h的子群，则存在偶数x(0≤x＜n)，使得a^m=γ^mx.令$k = {\gamma ^{\frac{{mx}}{2}}} $，则k²=γ^mx=a^m.由于m为奇数，设m=2t+1，其中t为非负整数，而

即$ k{a^{ - t}}$为a mod n的一个平方根.

若已知n的素因子分解，则由下面的定理2，根据模为素数的情形分别求出模每个素因子的平方根，然后利用中国剩余定理求得模n的平方根.

定理2^[4]  设奇数n的因式分解为

其中p₁，…，p_l为不同的素数，且e_i为正整数.若gcd(a，n)=1，则当$\left( {\frac{a}{{{p_i}}}} \right) = 1 $对于所有的i∈{1，…，l}成立时，x²≡a mod n有2^l个解，其它情形没有解.

当模n为合数时，若n的素因子分解未知，则求模n的平方根是困难的^[1-3].实际上我们有：

定理3  求模n平方根的难度与分解n的难度是等价的，其中n是一个奇合数.

证  如果存在分解n素因子的多项式时间算法，那么根据定理2可以在多项式时间内计算出模n的平方根.现假设存在一个计算模n平方根的多项式时间算法.为了分解n，首先检验n不是完全幂数，然后随机选取一个整数y∈$ Z_n^ * $，令a=y² mod n，利用假定的模n平方根算法求得一个x∈$ Z_n^ * $，使得x²≡a mod n，即有x²≡y² mod n.显然，x和y的公因子是n的因子.假设x和y互素.如果p是n的一个因子，那么p整除x²-y²=(x+y)(x-y). p要么整除x+y或x-y；要么同时整除两个因子，即p整除2x和2y.由于y是随机的，则整除x²-y²的奇素数都有$ \frac{1}{2}$的概率整除x+y或x-y，且任意两个素数会有$ \frac{1}{2}$的概率整除不同的因子.在这样的情况下，gcd(x-y，n)可能是n的非平凡因子；若gcd(x-y，n)不是n的非平凡因子，则重新随机选取y.经过k次计算后，不能分解n的概率为2^-k，那么存在分解n素因子的多项式时间算法.因此，求模n平方根的难度与分解n的难度是等价的.

在以下的讨论中，我们假设模n是一个特殊的整数-Blum整数.

定义4   若p，q是不同的奇素数，且p≡q≡3mod4，则称n=pq为Blum整数.

由定理2，同余方程x²≡a mod n的解等价于同余方程组

的解.首先考虑x²≡a mod p的解.如果x²≡a mod p有解，那么根据欧拉准则有${a^{\frac{1}{2}}} \equiv 1\;{\rm{mod}}\;p $，根据同余方程的性质，两边同乘以a得$ a\cdot{a^{\frac{1}{2}}} \equiv a\;{\rm{mod}}\;p$，即${a^{\frac{{p + 1}}{2}}} \equiv 1\;{\rm{mod}}\;p $，从而${a^{{{\left( {\frac{{p + 1}}{4}} \right)}^2}}} \equiv 1\;{\rm{mod}}\;p $，又因为p≡3mod4，则${\frac{{p + 1}}{4}} $是整数，所以$ x \equiv \pm {a^{\frac{{p + 1}}{4}}}{\rm{mod}}\;p$是x²≡a mod p的两个解.于是同余方程组有4个解.而在QR(n)中仅有一个为$ {a^{\frac{1}{2}}}^{\left( {\frac{{\phi \left( n \right)}}{4} + 1} \right)}{\rm{mod}}\;n$，称作a的主平方根^[4]，其中$\phi $ (·)表示欧拉函数.

文献[5-6]给出了两种求解二次剩余平方根的算法.

算法1^[5]

Input：大素数p，q，整数l，以及s_l+1

Output：s₀

${a_1} \leftarrow {\left( {\frac{{p + 1}}{4}} \right)^{l + 1}}{\rm{mod}}\left( {p - 1} \right) $；

${a_2} \leftarrow {\left( {\frac{{q + 1}}{4}} \right)^{l + 1}}{\rm{mod}}\left( {q - 1} \right) $；

${b_1} \leftarrow {s_{l + 1}}^{{a_1}}{\rm{mod}}~p $；

$ {b_2} \leftarrow {s_{l + 1}}^{{a_2}}{\rm{mod}}\;q$；

$_0 \leftarrow CRT({b_1}, {\rm{ }}{b_2}, {\rm{ }}p, q) $；//CRT表示利用中国剩余定理求解的函数

return $ \underline {{s_0}} $

算法2^[6]

Input：大素数p，q，整数l，以及s_l+1

Output： s₀

$ w \leftarrow {\left( {\frac{{\frac{{\phi \left( n \right)}}{4} + 1}}{2}} \right)^{l + 1}}{\rm{mod}}\;\phi \left( n \right)$

${s_0} \leftarrow s_{l + 1}^w{\rm{mod}}\left( {p \times q} \right) $；

return $ \underline {{s_0}} $

从表面上看，算法2的运算步骤简洁、直观；而算法1从表面上看起来不太直观，且运算比较繁杂，这是否说明算法2比算法1的效率高？接下来先对两种算法进行简单的介绍.两种算法都是从${s_{l + 1}} = s_0^{2^{l + 1}}{\rm{mod}}\;{\rm{}}n $中计算出s₀，每个s_i-1是s_i的主平方根.分析算法2，由前面的介绍可知s_l+1 mod n的主平方根为$ s_{l + 1}^{\frac{1}{2}\left( {\frac{{\phi \left( n \right)}}{4} + 1} \right)}{\rm{mod}}\;n$，则$ s_{l + 1}^{{{\left( {\frac{1}{2}\left( {\frac{{\phi \left( n \right)}}{4} + 1} \right)} \right)}^{l + 1}}}{\rm{mod}}\;{\rm{}}n$是s_l+1 mod n的l+1次主平方根.因为$ Z_n^ * $的阶为${\phi \left( n \right)} $，所以先模${\phi \left( n \right)} $约化指数${{{\left( {\frac{1}{2}\left( {\frac{{\phi \left( n \right)}}{4} + 1} \right)} \right)}^{l + 1}}} $，降低模指数运算的指数，然后计算得到s_l+1 mod n的l+1次主平方根s₀.在算法1中，同样分别用模(p-1)和模(q-1)约化指数${\left( {\frac{{p + 1}}{4}} \right)^{l + 1}} $和$ {\left( {\frac{{q + 1}}{4}} \right)^{l + 1}}$，首先计算s_l+1模p和模q的l+1次主平方根，然后使用中国剩余定理来计算s_l+1 mod n的l+1次主平方根.在下一节中，将分析比较两种不同算法的运算次数，从理论层面分析比较这两种算法.

不难发现算法1与算法2主要进行了模整数的指数运算，由于$ p, q, n, \phi \left( n \right)$都很大，必须用多精度算术来执行Z_n上的运算，所需的时间将依赖于它们的二进制表示数位.因为是选取差别很小的p和q，所以设p和q是$ m=\left\lfloor \text{lo}{{\text{g}}_{2}}p \right\rfloor +1$位的大素数，则n和$ \phi \left( n \right)$约为2m位的整数.对于模指数运算x^cmod n平均需要运行l-1次模平方运算和$ \frac{3}{2}\left( l-1 \right)$模乘运算，l为c的二进制表示长度^[7].假设计算机的计算位长为w，则某个整数r在基W=2^w表示下的长度s满足r=2^ws.那么在一次模平方运算中需要运行$\frac{3}{2}{{s}^{2}}+\frac{1}{2}s $次乘法和3s²+9s+3次加法；在一次模乘法运算中要运行2s²+s次乘法和4s²+4s+2次加法，其中s为模在基W=2^w表示下的长度^[8-9].下面我们利用这些结论分别计算算法1和算法2的运行次数.

为了表述方便，令t=log₂{(l+1)}-1.在算法1中，第一步，p-1为m位，则需要t次模平方运算和$ \frac{3}{2}t$次模乘运算，即$t\left( \frac{9}{2}{{s}^{2}}+2s \right) $次乘法运算，$ t(9{{s}^{2}}+15s+6)\text{ }$次加法运算.第一、二步的计算近似.第三步，a₁平均为m位，则需要$\left( m-1 \right)\left( \frac{9}{2}{{s}^{2}}+2s \right) $次乘法和$ \left( m-1 \right)(9{{s}^{2}}+15s+6)$次加法.第四步与第三步同理.第五步，首先要计算q在Z_p^*中的逆元_pq^-1和p在Z_q^*中的逆元_qp^-1，再计算$({{q}_{p}}{{q}^{-1}}{{b}_{1}}+{{p}_{q}}{{p}^{-1}}{{b}_{2}})\text{mod}\ ~n $，现有的较好的模逆算法是Plus-minu扩展欧几里得算法^[10]，最多需要m²次加减法运算.可得算法1求解s₀需要$ \left( t+m-1 \right)(9{{s}^{2}}+4s)$次乘法运算，$ \text{ }\left( t+m-1 \right)(18{{s}^{2}}+30s+12)+{{m}^{2}}$次加法运算.

用同样的方法计算得到算法2求解s₀需要$ \left( t+2m-1 \right)\left( \frac{9}{2}{{{\dot{s}}}^{2}}+4\dot{s} \right)$次乘法运算，$ \text{ }\left( t+2m-1 \right)(9{{{\dot{s}}}^{2}}+15\dot{s}+6)$次加法运算.由于模n的长度是模p与模q的两倍，所以$ \dot{s}=2s$.则算法2总共运行$\left( t+2m-1 \right)(18{{s}^{2}}+4s) $次乘法运算，$ \left( t+2m-1 \right)\left( 36s+30s+6 \right)$次加法运算.

从上面的分析可以得到算法2的运算次数明显比算法1的多.最后，我们用Mathematic仿真实验，分别用算法1和算法2计算s₀，为了方便统计实验结果，我们在同一个运行环境下，分别统计两种算法在1万次相同的输入下的运行时间，结果表明算法1比算法2用时少，而且结果很明显.表 1是两种算法在相同输入下的运行时间统计表，其中l=100，T₁，T₂分别表示算法1和算法2的运行时间.

二次剩余在密码学中有广泛应用^[12-16].本文通过分析比较两种计算二次剩余平方根的算法，找到了相对较优的算法，这对今后求二次剩余平方根时进行算法选择提供了帮助，并且得到在计算模n的平方根时，将模n分解为两个二进制表示长度相等的模，再利用中国剩余定理进行求解，可以提高求模n二次剩余平方根的效率.而近些年基于二次剩余构造密码方案是密码界研究的热点，无疑我们为后面学者对此热点的研究提供了方便.