ifx^2=a(modn),wecandifinethatxisasquarerootofamodulon.NowIwantyoutofindthesquarerootoftwogivennumberaandn.aandnarerelativelyprime.就是求X的值,X的范围是1到n-1,但是不能穷搜,因为n太大了,a,narenatur

Question

ifx^2=a(mod n),we can difine that x is a square root of a modulo n.Now I want you to find the square root of two given number a and n.a and n are relatively prime.
就是求X的值,X的范围是1到n-1,但是不能穷搜,因为n太大了,a,n are natural,1

Answer 1

求一个模的二次剩余,是个难题,如果不允许穷搜,看来要对二次互反律作巧妙的处理.我只是提议一下.另外请参考：