《数论概论》读书笔记第23章二次剩余

刺骨的言语ヽ痛彻心扉 2022-06-08 20:40 222阅读 0赞

什么叫二次剩余，其实就是对于给定的p(p∈P)和n，如果有x满足x2≡n(modp)，那么n在模p意义下就是二次剩余。其实就是模意义下能否开根号。

我们先定义Fp，这是一个数域，其实就是0到p−1这p个数与模p意义下加减乘除运算构成的集合。

定理1：对于x2≡n(modp)，总共有p−12个的n能使该方程有解（将n=0情况除去，由于该情况显然有x=0）。  
证明：我们只用考虑所有x2。如果存在不同的两个数u、v，它们的平方在模p意义下同余，那么显然有p|(u2−v2)。由平方差公式p|(u\+v)(u−v)。显然p不可能整除u−v，因此p整除u\+v，因此u\+v≡0(modp)。这个结论反过来也是成立的，因此共有p−12种互不相同的平方，显然对应了所有有解的n，而且同一个n还一定存在两个互为相反数的解。

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\+ω)p\+1(a\+ω)p(a\+ω)(ap\+ωp)(a\+ω)(ap−1a\+ωp−1ω)(a\+ω)(a−ω)(a\+ω)a2−ω2a2−(a2−n)n(modp)

另一解为:  
             x2≡−x1(modp)

如何找到这个k<script type="math/tex" id="MathJax-Element-141">k</script>呢。因为非二次剩余的个数大约有一半，随机几次即可。

话不多说，可以参考资料：  
[ACdreamer 二次同余方程的解][ACdreamer]  
[二次剩余Cipolla算法学习小记][Cipolla]

[ACdreamer]: http://blog.csdn.net/acdreamers/article/details/10182281
[Cipolla]: http://blog.csdn.net/a_crazy_czy/article/details/51959546

发表评论取消回复

表情：

评论列表（有 0 条评论，222人围观）

还没有评论，来说两句吧...

相关阅读

相关《数论概论》读书笔记(第一章) 什么是数论？

数论是纯粹数学的分支之一，主要研究整数的性质。整数可以是方程式的解（丢番图方程）。有些解析函数（像黎曼ζ函数）中包括了一些整数、质数的性质，透过这些函数也可以了解

布满荆棘的人生/ 2022年09月30日 03:56/ 0 赞/ 269 阅读

相关数据库系统概论学习笔记第七章

数据库设计 ![Center][] ![Center 1][] ![Center 2][] ![Center 3][] ![Center 4][]

绝地灬酷狼/ 2022年07月15日 02:39/ 0 赞/ 221 阅读

相关《数论概论》读书笔记第三章勾股数组与单位圆

本章讲的是勾股数组与单位圆的关系，讲关于勾股数的公式可以通过几何形式来推出。定理3.1: 圆x2\+y2=1上的坐标是有理数的点都可以由公式： (x,y)=(1

我不是女神ヾ/ 2022年06月16日 05:09/ 0 赞/ 208 阅读

相关《数论概论》读书笔记（第二章）勾股数组

本章主要讨论的是本原勾股数组，也就是关于满足a2\+b2=c2的三元组(a,b,c)，且(a,b,c)互质的问题。这章中提到一个概念：本原勾股数组（PPT）是一个三元组(

￡神魔★判官ぃ/ 2022年06月16日 00:42/ 0 赞/ 368 阅读

相关《数论概论》读书笔记 (第四章) 高次幂之和与费马大定理

这章讲的东西就是费马大定理。很少的内容。在18和19世纪高斯和欧拉证明了指数为3的方程没有解，狄利克雷与勒让德证明了5次方程没有解。 n>=3时方程：an\+bn=cn

灰太狼/ 2022年06月15日 12:52/ 0 赞/ 245 阅读

相关《数论概论》读书笔记第6章线性方程与最大公约数

这章讲的就是欧几里得算法和exgcd。原式: ax\+by=gcd(a,b)(假设a≥b) 当 b=0 时有 gcd(a,b)=a,此时 x=1,y=0 当 b

- 日理万妓/ 2022年06月14日 05:20/ 0 赞/ 186 阅读

相关《数论概论》读书笔记第5章整除性与最大公因子数

这章就是讲最大公因子的一些概念和求gcd的方法。高中必修三，就已经知道可以有“辗转相除法”和“更相减损术”等方法能够更快的求出两个数的最大公因数讲述一些概念。

骑猪看日落/ 2022年06月13日 22:36/ 0 赞/ 271 阅读

相关《数论概论》读书笔记第23章二次剩余

什么叫二次剩余，其实就是对于给定的p(p∈P)和n，如果有x满足x2≡n(modp)，那么n在模p意义下就是二次剩余。其实就是模意义下能否开根号。我们先定义Fp，这是一个数

刺骨的言语ヽ痛彻心扉/ 2022年06月08日 20:40/ 0 赞/ 223 阅读

相关二次剩余入门

昨天训练的时候遇到一道题怎么也不会做，在网上搜了题解之后第一次听说了二次剩余，看了一天各种dalao的博客，在这里总结一下自己所理解的二次剩余及其用法。 1，什么是

雨点打透心脏的1/2处/ 2022年06月03日 09:56/ 0 赞/ 172 阅读

相关数论概论(英文版.第4版)

数论概论(英文版.第4版) 基本信息原书名：A Friendly Introduction to Number Theory Fourth Edition 作者：

蔚落/ 2022年03月29日 08:26/ 0 赞/ 252 阅读