论文标题
寻找平方根模量P的算法
An algorithm for finding square root modulo p
论文作者
论文摘要
我们提出了一种新型算法，用于查找方形模量p。尽管存在一个直接公式来计算元素模量素数的平方根（3 mod 4），但是计算平方根模元（1 mod 4）的平方根是无琐的。 Tonelli-shanks算法仍然是最广泛使用的，并且在所有素数上平均最快[19]。本文提出了一种用于查找Square Roots Modulo的新算法，这些算法都是所有奇数的，该算法在实践中显示了对现有方法的改进，尽管渐近地给出了与Tonelli-Shanks相同的运行时间。除了实际上有效的计算时间外，所提出的方法不一定需要非放弃的可用性，并且也可以与“相对非遗留”一起使用。这种“相对非放弃”更容易找到（概率为2/3）与非沉闷（概率1/2）相比。
We propose a novel algorithm for finding square roots modulo p. Although there exists a direct formula to calculate square root of an element modulo prime (3 mod 4), but calculating square root modulo prime (1 mod 4) is non trivial. Tonelli-Shanks algorithm remains the most widely used and probably the fastest when averaged over all primes [19]. This paper proposes a new algorithm for finding square roots modulo all odd primes, which shows improvement over existing method in practical terms although asymptotically gives the same run time as Tonelli-Shanks. Apart from practically efficient computation time, the proposed method does not necessarily require availability of non-residue and can work with `relative non-residue' also. Such `relative non-residues' are much easier to find ( probability 2/3) compared to non-residues ( probability 1/2).
