请输入您要查询的字词:

 

单词 ShanksTonelliAlgorithm
释义

Shanks-Tonelli algorithm


The Shanks-Tonelli algorithm is a procedure for solving a congruenceMathworldPlanetmathPlanetmath of the form x2n(modp), where p is an odd prime and n is a quadratic residueMathworldPlanetmath of p. In other words, it can be used to compute modular square roots.

First find positive integers Q and S such that p-1=2SQ, where Q is odd. Then find a quadratic nonresidue W of p and compute VWQ(modp). Then find an integer n that is the multiplicative inverse of n(modp) (i.e., nn1(modp)).

Compute

RnQ+12(modp)

and find the smallest integer i0 that satisfies

(R2n)2i1(modp)

If i=0, then x=R, and the algorithm stops. Otherwise, compute

RRV2(S-i-1)(modp)

and repeat the procedure for R=R.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 21:07:25