二次剩余问题 数论若同余式 x^2≡a(mod p),p=8m+1有解,并且已知N是模P的平方非剩余,试举出上述同余式的
来源:学生作业帮 编辑:神马作文网作业帮 分类:数学作业 时间:2024/09/27 21:22:54
二次剩余问题 数论
若同余式 x^2≡a(mod p),p=8m+1有解,并且已知N是模P的平方非剩余,试举出上述同余式的一个解法
若同余式 x^2≡a(mod p),p=8m+1有解,并且已知N是模P的平方非剩余,试举出上述同余式的一个解法
这通常是一个算法,没有确切的公式,但有一下确切的过程如下:
设s=4m
a^s=1(mod p) n^s=-1(mod p),以下求解过程中若出现-1,则用n^s代替之(这是关键)
一、
如果s是奇数,则a^(s+1)=a(mod p) 解得+-a^(s+1)/2
否则a^s/2=1或者n^s*a^s/2=1
二、
如果s/2是奇数,同前求出解
如果s/2是偶数,同前,继续往下使a的指数变为s/4,s/8,...直到a的指数是奇数,即可以求出解来.
设s=2^r*J,J是奇数则最后一定出现:
a^J *n^(2k)=1(mod p)
两边乘以a求得解的形式为:+-a^(J+1)/2 *n^k
这有点象辗转相除法,程序会很快到达J(s每次除以2)
再问: 如果s是奇数,则a^(s+1)=a(mod p) 解得+-a^(s+1)/2 后面那个+-什么意思
设s=4m
a^s=1(mod p) n^s=-1(mod p),以下求解过程中若出现-1,则用n^s代替之(这是关键)
一、
如果s是奇数,则a^(s+1)=a(mod p) 解得+-a^(s+1)/2
否则a^s/2=1或者n^s*a^s/2=1
二、
如果s/2是奇数,同前求出解
如果s/2是偶数,同前,继续往下使a的指数变为s/4,s/8,...直到a的指数是奇数,即可以求出解来.
设s=2^r*J,J是奇数则最后一定出现:
a^J *n^(2k)=1(mod p)
两边乘以a求得解的形式为:+-a^(J+1)/2 *n^k
这有点象辗转相除法,程序会很快到达J(s每次除以2)
再问: 如果s是奇数,则a^(s+1)=a(mod p) 解得+-a^(s+1)/2 后面那个+-什么意思
关于同余式的证明证明同余式(-4)^((p-1)/4) = 1 (mod p) ,其中p为模4余1的素数
证明:对任意素数p,同余式(x^2 - 2)(x^2 - 17)(x^2 - 34)≡0(mod p)有解
数论 x^2 ≡ -n (mod p)有整数解 证明:x^2 ≡ -4n (mod p)有整数解
解同余式组x≡-2(mod12)x≡6(mod 10) x≡1(mod 15)
一个简单的数论证明P是一个质数,求证 x^b=x mod p 有 gcd(p-1,b-1)个解?我一不小心开出了两个一样
初等数论证明:x^b=x mod p 解的个数
已知m,n,p都是整数,且|m-n|的三次方+(p-m)的二次方=1,则|p-m| +|m-n|+2|n-p|=
设n是正整数,p是素数,(n,p−1)=k,证明同余方程x^n≡1(mod p)有k个解.
初等数论同余问题p为质数,0<a<p,证明x≡b×(-1)∧(a-1)×(p-1)···(p-a+1)/a!(mod p
a ≡ a (mod m) 若a ²≡ a (mod m) ,用同余式相乘,得到a三次方 ≡ a ²
请教关于同余式定义的问题
DZ47LE-32 4P 32A 380V型号的剩余电流动作断路器中4P是啥意思与3P+N有区别吗