[二次剩余]求解二次剩余

2019-04-13 15:59发布

站内文章 / 模拟电子
11178 0 1497

Description

求解x2≡n(modp)。p是一个奇质数。

Solution

由费马小定理np−1≡1(modp)所以np−12≡±1(modp)由欧拉准则(np)≡np−12(modp)其中(np)为勒让德符号。因为x≡n12(modp)，所以有xp−1≡np−12≡1(modp)。即(np)=⎧⎩⎨⎪⎪1−10n在模p意义下是二次剩余n在模p意义下不是二次剩余n≡0(modp)设k=a2−n,ω=k√则该方程的解为x≡(a+ω)p+12(modp)证明：若k是该模意义下的非二次剩余，则wp−1=np−12=−1同时:(a+b)p≡ap+bp(modp)则x21≡≡≡≡≡≡≡≡(a+ω

热门文章