URAL1132 Square Root

The number x is called a square root of a modulo n (root( a, n)) if x* x = a (mod n). Write the program to find the square root of number a by given modulo n.
### Input
One number K in the first line is an amount of tests ( K ≤ 100000). Each next line represents separate test, which contains integers a and n (1 ≤ a, n ≤ 32767, n is prime, a and n are relatively prime).
### Output
For each input test the program must evaluate all possible values root( a, n) in the range from 1 to n − 1 and output them in increasing order in one separate line using spaces. If there is no square root for current test, the program must print in separate line: ‘No root’.
### Example
input
5
4 17
3 7
2 7
14 31
10007 20011

output
2 15
No root
3 4
13 18
5382 14629

求解二次剩余的模板题。

这里详细的推导一下$p$为奇质数下的二次剩余。

首先我们要知道一个数$a$存在二次剩余的充要条件：
    $$a^{\frac{p-1}{2}}=1(mod\ p)$$
由费马小定理对于任意正整数$n$，$n^{p-1}=1(mod\ p)$
我们把$x^2=a$带入，那么$x^{p-1}=1(mod\ p)$
否则若不满足，那么$x^{p-1}\neq 1(mod\ p)$，不符合现实，故不存在$x$。

那么若$a$有了二次剩余怎么求解呢？
这里有一个很暴力的方法。
模仿复数，我们构造模意义下的复数。

考虑找一个$c$使得$c^2-a$为非二次剩余。
通常情况下，直接随机期望$2$次即可获得$c$。
这之后我们便有了虚数单位$i=\sqrt{c^2-a}$。
这和平常的复数计算基本一致，只是不再是$i^2=-1$而是$i^2=c^2-a$

通过构造，$a$的二次剩余中的一个数就是$(c+i)^{\frac{p+1}{2}}$

为什么呢，证明如下：

$$a^2 = (c+i)^{{p+1}}$$
$$=(c+i)(c+i)^p$$
$$=(c+i)(c^p+i^p)$$

为什么呢，发现对于组合数$\binom p k,p\in Prime,k\in [1,n-1]$，一定是$p$的倍数，因为质数在分子上约不掉。

$$=(c+i)(c-i)$$
$$=c^2-i^2=a$$

得证。

于是我们就可以类似复数类的做运算了。
拉格朗日中值定理可以证明虚部一定为$0$。

代码如下

```
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<ctime>
#define LL long long
using namespace std;

int a, w2, n, p;
inline int Add(const int &a, const int &b) {
	return (a + b) % p;
}
inline int Minus(const int &a, const int &b) {
	return (a - b + p) % p;
}
inline int Mul(const int &a, const int &b) {
	return 1ll * a * b % p;
}
int Rand() {
	return (rand() << 15) + rand();
}
struct NE {
	int r, i;
	NE operator + (const NE &A) const {
		return (NE) {Add(r, A.r), Add(i, A.i)};
	}
	NE operator * (const NE &A) const {
		return (NE) {Add(Mul(r, A.r), Mul(Mul(i, A.i), w2)), 
					 Add(Mul(r, A.i), Mul(i, A.r))};
	}
};

LL fpow(LL a, int b) {
	LL ans = 1;
	while(b) {
		if(b & 1) ans = ans * a % p;
		a = a * a % p, b >>= 1;
	}
	return ans;
}

NE fpow(NE a, int b) {
	NE ans = (NE) {1, 0};
	while(b) {
		if(b & 1) ans = ans * a;
		a = a * a, b >>= 1;
	}
	return ans;
}

int Sqroot(int n) {
	if(fpow(n, p - 1 >> 1) != 1)
		return -1;
	do {
		a = Rand() % p;
		w2 = Minus(Mul(a, a), n);
	} while(fpow(w2, p - 1 >> 1) == 1);
	int ans = fpow((NE) {a, 1}, (p + 1) / 2).r;
	return min(ans, p - ans);
}

int main() {
	srand(20020327);
	int t, ans;
	scanf("%d", &t);
	while(t--) {
		scanf("%d%d", &n, &p);
		n %= p;
		if(p == 2) {
			printf("1\n");
			continue;
		}
		ans = Sqroot(n);
		if(ans == -1) printf("No root\n");
		else printf("%d %d\n", ans, p - ans);
	}
	return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链