西南大学学报 (自然科学版)  2019, Vol. 41 Issue (1): 60-64.  DOI: 10.13718/j.cnki.xdzk.2019.01.009
0
Article Options
  • PDF
  • Abstract
  • Figures
  • References
  • 扩展功能
    Email Alert
    RSS
    本文作者相关文章
    蔡兆政
    瞿云云
    包小敏
    欢迎关注西南大学期刊社
     

  • 两种求二次剩余平方根算法的比较    [PDF全文]
    蔡兆政1, 瞿云云2, 包小敏1     
    1. 西南大学 数学与统计学院, 重庆 400715;
    2. 贵州师范大学 数学与计算机科学学院, 贵阳 550001
    摘要:在模是大合数的情况下,求二次剩余平方根是一个困难问题.目前已知的求二次剩余平方根的算法有两种,本文对Cocks和曹珍富的算法进行分析比较,结果表明由Cocks提出的算法效率更高,这对今后求二次剩余平方根时进行算法选择提供了帮助.
    关键词    二次剩余    平方根    中国剩余定理    

    二次剩余是数论中的一个基本术语,高斯在其著作《算术研究》中就曾对其进行过讨论,其定义如下:

    定义1  设$ a \in Z_n^ * $,其中$Z_n^ * = \{ r|1 \le {\rm{ }}r < n, {\rm{gcd}}\left( {r, n} \right) = 1\} $.若存在$ x \in Z_n^ * $使得$ {x^2} \equiv a\;\;{\rm{mod}}\;\;n$,则称a是模n的二次剩余.所有模n的二次剩余做成的集合记为$ QR\left( n \right) = \{ {x^2}\;{\rm{mod}}\;\;n|x \in Z_n^ * \} $.

    n是奇素数时,下面的定理给出了一个判别一个整数a是否是二次剩余的简单方法:

    定理1(欧拉准则)   设p是一个奇素数,则a是二次剩余当且仅当

    $ {{a}^{\frac{1}{2}}}\equiv 1\ \text{mod}\ ~p $

    n是合数时,若不知道n的素因子分解,则判断一个整数a是否是二次剩余是困难的[1-4];若知道n的素因子分解$ n = \mathop \prod \limits_{i = 1}^k p_i^{{e_i}}$,其中pi为不同的素数,ei为正整数,gcd(an)=1,则可以通过计算Jacobi符号$ \left( {\frac{a}{n}} \right)$来判断a是否是二次剩余的(当且仅当所有的Legendre符号$ \left( {\frac{a}{{{p_i}}}} \right) = 1$a是二次剩余的).

    定义2(Legendre符号)   对于奇素数m,若${x^2} \equiv a\;\;{\rm{mod}}\left\{ m \right\} $有解,则记$ \left( {\frac{a}{m}} \right) = 1$;若a|m,则记$ \left( {\frac{a}{m}} \right) = 0$;否则记$\left( {\frac{a}{m}} \right) = - 1 $.

    对于n=pq,其中pq是不同的奇素数,我们做如下标记:

    $ \left( \frac{x}{n} \right)=\left\{ \begin{align} &0\ \ \ \ \text{gcd}\left( x, n \right)>1 \\ &1\ \ \ \ \left( \frac{x}{p} \right)\left( \frac{x}{p} \right)=1\} \\ &-1\ \ \ \ \left( \frac{x}{p} \right)\left( \frac{x}{p} \right)=-1~ \\ \end{align} \right.\text{ } $

    显然,x是模n的二次剩余等价于$ \left( {\frac{x}{p}} \right) = \left( {\frac{x}{p}} \right) = 1$.

    定义3(Jacobi符号)  设n是一个奇正整数,n的素因数分解如下

    $ n = \mathop \prod \limits_{i = 1}^k p_i^{{e_i}} $

    对任意整数a定义Jacobi符号如下

    $ \left( {\frac{a}{n}} \right) = \mathop \prod \limits_{i = 1}^k {\left( {\frac{a}{{{p_i}}}} \right)^{{e_i}}} $

    其中$\left( {\frac{a}{{{p_i}}}} \right) $是Legendre符号. Jacobi符号是Legendre符号的推广,需要注意的是,如果gcd(an)>1,那么$\left( {\frac{a}{n}} \right) = 0 $;如果$ \left( {\frac{a}{n}} \right) = - 1$,那么a是二次非剩余;但是$ \left( {\frac{a}{n}} \right) = 1$时不能确定a是否为二次剩余,只有对于所有的$\left( {\frac{a}{{{p_i}}}} \right) = 1 $成立时,a是二次剩余.

    1 模平方根的计算

    本节讨论模平方根的计算问题.设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=a{{a}^{\frac{1}{2}}}={{a}^{\frac{p+1}{2}}}={{\left( {{a}^{\frac{p+1}{4}}} \right)}^{2}} $

    所以${a^{\frac{{p + 1}}{4}}} $an的一个平方根.一般情况下,设$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}$的阶整除2h;因为${a^{{2^{h - 1}}m}} = 1 $,所以am的阶整除2h-1;而${\gamma ^{{2^{h - 1}}m}} = - 1 $,则γm的阶恰好为2h.生成元为γm的群是$ Z_n^ * $阶为2h的子群,则存在偶数x(0≤xn),使得am=γmx.令$k = {\gamma ^{\frac{{mx}}{2}}} $,则k2=γmx=am.由于m为奇数,设m=2t+1,其中t为非负整数,而

    $ {(k{a^{ - t}})^2} = {k^2}{a^{ - 2t}} = {a^m}{a^{ - 2t}} = {a^{m - 2t}} = a $

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

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

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

    $ n = \mathop \prod \limits_{i = 1}^l p_i^{{e_i}} $

    其中p1,…,pl为不同的素数,且ei为正整数.若gcd(an)=1,则当$\left( {\frac{a}{{{p_i}}}} \right) = 1 $对于所有的i∈{1,…,l}成立时,x2a mod n有2l个解,其它情形没有解.

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

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

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

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

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

    由定理2,同余方程x2a mod n的解等价于同余方程组

    $ \left\{ \begin{align} &x\equiv a\ \text{mod}~\ p \\ &x\equiv a\ \text{mod}~\ q \\ \end{align} \right.~ $

    的解.首先考虑x2a mod p的解.如果x2a 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$x2a mod p的两个解.于是同余方程组有4个解.而在QR(n)中仅有一个为$ {a^{\frac{1}{2}}}^{\left( {\frac{{\phi \left( n \right)}}{4} + 1} \right)}{\rm{mod}}\;n$,称作a的主平方根[4],其中$\phi $ (·)表示欧拉函数.

    2 两种求二次剩余平方根的算法

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

    算法1[5]

    Input:大素数pq,整数l,以及sl+1

    Output:s0

    ${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:大素数pq,整数l,以及sl+1

    Output:s0

    $ 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 $中计算出s0,每个si-1si的主平方根.分析算法2,由前面的介绍可知sl+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$sl+1 mod nl+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}}} $,降低模指数运算的指数,然后计算得到sl+1 mod nl+1次主平方根s0.在算法1中,同样分别用模(p-1)和模(q-1)约化指数${\left( {\frac{{p + 1}}{4}} \right)^{l + 1}} $$ {\left( {\frac{{q + 1}}{4}} \right)^{l + 1}}$,首先计算sl+1p和模ql+1次主平方根,然后使用中国剩余定理来计算sl+1 mod nl+1次主平方根.在下一节中,将分析比较两种不同算法的运算次数,从理论层面分析比较这两种算法.

    3 两种算法的分析比较

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

    为了表述方便,令t=log2{(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{ }$次加法运算.第一、二步的计算近似.第三步,a1平均为m位,则需要$\left( m-1 \right)\left( \frac{9}{2}{{s}^{2}}+2s \right) $次乘法和$ \left( m-1 \right)(9{{s}^{2}}+15s+6)$次加法.第四步与第三步同理.第五步,首先要计算qZp*中的逆元pq-1pZq*中的逆元qp-1,再计算$({{q}_{p}}{{q}^{-1}}{{b}_{1}}+{{p}_{q}}{{p}^{-1}}{{b}_{2}})\text{mod}\ ~n $,现有的较好的模逆算法是Plus-minu扩展欧几里得算法[10],最多需要m2次加减法运算.可得算法1求解s0需要$ \left( t+m-1 \right)(9{{s}^{2}}+4s)$次乘法运算,$ \text{ }\left( t+m-1 \right)(18{{s}^{2}}+30s+12)+{{m}^{2}}$次加法运算.

    用同样的方法计算得到算法2求解s0需要$ \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计算s0,为了方便统计实验结果,我们在同一个运行环境下,分别统计两种算法在1万次相同的输入下的运行时间,结果表明算法1比算法2用时少,而且结果很明显.表 1是两种算法在相同输入下的运行时间统计表,其中l=100,T1T2分别表示算法1和算法2的运行时间.

    表 1 两种算法在相同输入下的运行时间统计表
    4 结束语

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

    参考文献
    [1] VICTOR S. A Computational Introduction to Number Theory and Algebra[M]. Cambridge: Cambridge University Press Cambridge, 2008.
    [2] BUHLER J, WAGON S. Basic Algorithms in Number Theory[J]. Algorithmic Number Theory, MSRILibrary, 2008: 44.
    [3] Cohen H. A Course in Computational Algebraic Number Theory[J]. Graduate Texts in Math, 2000, 26(2): 211-244.
    [4] STINSON D R. Cryptography:Theory and Practice[M]. Florida: Chemical Rubber Company Press, 1995.
    [5] COCKS C. An Identity Based Encryption Scheme Based on Quadratic Residues[J]. Cryptography and Coding, 2001, 2260: 360-363. DOI:10.1007/3-540-45325-3
    [6] CAO Z F, ZHU H J, LU R X. Provably Secure Robust Threshold Partial Blind Signature[J]. Science in China Series F, 2006, 49(5): 604-615.
    [7] 屈晓.基于公钥密码体制的模幂算法执行效率研究[D].天津: 天津大学, 2014. http://cdmd.cnki.com.cn/Article/CDMD-10056-1015019149.htm
    [8] 王金荣, 周赟, 王红霞. Montgomery模平方算法及其应用[J]. 计算机工程, 2007, 33(24): 155-157.
    [9] KAYA E, ACAR T, KALISK B S. Analyzing and Comparing Montgomery Multiplication Algorithms[J]. IEEE Microwave Magazine, 1996, 16(3): 26-33.
    [10] 蒋帅.模逆运算及其时间复杂度分析[D].济南: 山东大学, 2014. http://www.wanfangdata.com.cn/details/detail.do?_type=degree&id=Y2598312
    [11] BLUM L, BLUM M, SHUB M. A Simple Unpredictable Pseudo-Random Number Generator[J]. SIAM Journal on Computing, 1986, 15(2): 364-383. DOI:10.1137/0215025
    [12] BLUM M, GOLDWASSER S. An Efficient Probabilistic Public Key Encryption Scheme Which Hides All Partial Information[J]. Process of Cryptography, 1984: 289-302.
    [13] CHAI Z C, CAO Z F, DONG X L. Identity-Based Signature Scheme Based on Quadratic Residues[J]. Science in China Series F, 2007(3): 373-380.
    [14] 费如纯, 王丽娜, 于戈. 基于离散对数和二次剩余的门限数字签名体制[J]. 通信学报, 2002, 23(5): 65-69. DOI:10.3321/j.issn:1000-436X.2002.05.012
    [15] 王志伟, 张伟. 基于二次剩余的新型盲签名方案[J]. 计算机工程与科学, 2010, 32(9): 18-20. DOI:10.3969/j.issn.1007-130X.2010.09.005
    [16] 邱卫国, 陈克非, 白英彩. 新型Rabin签名方案[J]. 软件学报, 2000, 11(10): 1333-1337.
    Comparison of Two Algorithms for Finding the Quadratic Residue Square Root
    CAI Zhao-zheng1, QU Yun-yun2, BAO Xiao-min1     
    1. School of Mathematics and Statistics, Southwest University, Chongqing 400715, China;
    2. School of Mathematical Science, Guizhou Normal University, Guiyang, Guizhou 550001, China
    Abstract: In the case of a large composite number of modules, to find the quadratic residue root is a difficult problem. There are two kinds of algorithms that are known for finding the square root of quadratic residuals. In this paper, the two known algorithms are analyzed and compared, and the results show that the algorithm 1 proposed by Cocks is more efficient than the algorithm 2 proposed by Cao Zhenfu, et al.
    Key words: module    quadratic residue    square root    Chinese remainder theorem    
    X