初等数论–二次剩余与二次同余方程–二次互反律「建议收藏」

初等数论–二次剩余与二次同余方程–二次互反律「建议收藏」信息安全数学基础–二次剩余与二次同余方程–雅可比符号Jacobisymbol博主是初学信息安全数学基础(整除+同余+原根+群环域),本意是想整理一些较难理解的定理、算法,加深记忆也方便日后查找;如果有错,欢迎指正。…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

初等数论–二次剩余与二次同余方程–二次互反律

博主是初学初等数论(整除+同余+原根),本意是想整理一些较难理解的定理、算法,加深记忆也方便日后查找;如果有错,欢迎指正。
我整理成一个系列:初等数论,方便检索。

  • p , q p,q p,q是两个不同的奇素数,则 ( q p ) ( p q ) = ( − 1 ) ( p − 1 2 ) ⋅ ( q − 1 2 ) (\frac{q}{p})(\frac{p}{q})=(-1)^{(\frac{p-1}{2})·(\frac{q-1}{2})} (pq)(qp)=(1)(2p1)(2q1)

证明:高斯引理+巧妙发现规律
上一章证明了高斯引理 ( a p ) = ( − 1 ) m (\frac{a}{p})=(-1)^m (pa)=(1)m,同理,我们考虑 ( q p ) = ( − 1 ) m , (\frac{q}{p})=(-1)^m, (pq)=(1)m, p − 1 2 \frac{p-1}{2} 2p1个数 : q , 2 q , … … p − 1 2 q :q,2q,……\frac{p-1}{2}q :q,2q,2p1q中有 m m m个最小正因数 > p 2 , >\frac{p}{2}, >2p,我们假设这 m m m > p 2 >\frac{p}{2} >2p的最小正因数分别为: α 1 , α 2 , … … α m , < p 2 \alpha_1,\alpha_2,……\alpha_m,<\frac{p}{2} α1,α2,αm,<2p的最小正因数为: β 1 , β 2 , … … β n , \beta_1,\beta_2,……\beta_n, β1,β2,βn,上一章我们已经证过 p − α 1 , p − α 2 … … p − α m , β 1 , β 2 , … … β n , p-\alpha_1,p-\alpha_2……p-\alpha_m,\beta_1,\beta_2,……\beta_n, pα1,pα2pαm,β1,β2,βn, p − 1 2 \frac{p-1}{2} 2p1个数,大小在 1 ∼ p − 1 2 1\sim\frac{p-1}{2} 12p1之间,且两两模 p p p不同余。

  • 对于 p − 1 2 \frac{p-1}{2} 2p1个数 : q , 2 q , … … p − 1 2 q , :q,2q,……\frac{p-1}{2}q, :q,2q,2p1q,带余除法 k q = [ k q p ] ⋅ p + r k , 0 ≤ r k < p 。 kq=[\frac{kq}{p}]·p+r_k,0\le r_k<p。 kq=[pkq]p+rk,0rk<p(这里 [ ] [] []是取下整数的意思)

  • 计算 ∑ k = 1 p − 1 2 k \sum_{k=1}^{\frac{p-1}{2}}k k=12p1k(我个人觉得能想到计算这个是需要一定的数学基础的,还挺难的,我目前也不明白为什么会想到要计算这个,虽然后面可以通过这个找到m的某种表达形式,但是在这一步真的想不明白)

∑ k = 1 p − 1 2 k = ∑ i = 1 m ( p − α i ) + ∑ j = 1 n β j = ∑ i = 1 m p − ∑ i = 1 m α i + ∑ j = 1 n β j = m p − 2 ∑ i = 1 m α i + ∑ i = 1 m α i + ∑ j = 1 n β j = m p − 2 ∑ i = 1 m a i + ∑ k = 1 p − 1 2 r k \sum_{k=1}^{\frac{p-1}{2}}k\\ =\sum_{i=1}^{m}(p-\alpha_i)+\sum_{j=1}^{n}\beta_j\\=\sum_{i=1}^{m}p-\sum_{i=1}^{m}\alpha_i+\sum_{j=1}^{n}\beta_j\\=mp-2\sum_{i=1}^{m}\alpha_i+\sum_{i=1}^{m}\alpha_i+\sum_{j=1}^{n}\beta_j\\=mp-2\sum_{i=1}^{m}a_i+\sum_{k=1}^{\frac{p-1}{2}}r_k k=12p1k=i=1m(pαi)+j=1nβj=i=1mpi=1mαi+j=1nβj=mp2i=1mαi+i=1mαi+j=1nβj=mp2i=1mai+k=12p1rk (1)

  • 乘以 q q q,计算带余除法 k q = [ k q p ] ⋅ p + r k , 0 ≤ r k < p 。 kq=[\frac{kq}{p}]·p+r_k,0\le r_k<p。 kq=[pkq]p+rk,0rk<p
    ∑ k = 1 p − 1 2 k ⋅ q = ∑ k = 1 p − 1 2 [ k q p ] ⋅ p + ∑ k = 1 p − 1 2 r k \sum_{k=1}^{\frac{p-1}{2}}k·q\\=\sum_{k=1}^{\frac{p-1}{2}}[\frac{kq}{p}]·p+\sum_{k=1}^{\frac{p-1}{2}}r_k k=12p1kq=k=12p1[pkq]p+k=12p1rk (2)

  • (2)-(1)
    ∑ k = 1 p − 1 2 k ⋅ ( q − 1 ) = ( ∑ k = 1 p − 1 2 [ k q p ] − m ) ⋅ p + 2 ∑ i = 1 m a i \sum_{k=1}^{\frac{p-1}{2}}k·(q-1)=(\sum_{k=1}^{\frac{p-1}{2}}[\frac{kq}{p}]-m)·p+2\sum_{i=1}^{m}a_i k=12p1k(q1)=(k=12p1[pkq]m)p+2i=1mai

  • 同时mod 2:(这一步也挺神奇的)
    m = ∑ k = 1 p − 1 2 [ k q p ] m=\sum_{k=1}^{\frac{p-1}{2}}[\frac{kq}{p}] m=k=12p1[pkq]

同理, n = ∑ l = 1 q − 1 2 [ l p q ] n=\sum_{l=1}^{\frac{q-1}{2}}[\frac{lp}{q}] n=l=12q1[qlp]

  • 我们要计算的 ( q p ) ( p q ) = ( − 1 ) m ⋅ ( − 1 ) n = ( − 1 ) m + n , (\frac{q}{p})(\frac{p}{q})=(-1)^m·(-1)^n=(-1)^{m+n}, (pq)(qp)=(1)m(1)n=(1)m+n,即我们现在要计算的是 m + n = ∑ k = 1 p − 1 2 [ k q p ] + ∑ l = 1 q − 1 2 [ l p q ] m+n=\sum_{k=1}^{\frac{p-1}{2}}[\frac{kq}{p}]+\sum_{l=1}^{\frac{q-1}{2}}[\frac{lp}{q}] m+n=k=12p1[pkq]+l=12q1[qlp]

这一步计算我觉得也有点难,用图形化来思考这个问题:在这里插入图片描述

  • 整体计算:这个矩形里的整数点共有 ( p − 1 2 ) ⋅ ( q − 1 2 ) (\frac{p-1}{2})·(\frac{q-1}{2}) (2p1)(2q1)
  • 分开上下三角形计算:把变化中的纵坐标 y y y L L L表示:
    上三角形: x L ≤ p q , 1 ≤ L ≤ q − 1 2 , \frac{x}{L}\le\frac{p}{q},1\le L\le \frac{q-1}{2}, Lxqp,1L2q1, x ≤ L p q , x\le\frac{Lp}{q}, xqLp,点个数一共有 ∑ l = 1 q − 1 2 [ L p q ] \sum_{l=1}^{\frac{q-1}{2}}[\frac{Lp}{q}] l=12q1[qLp]
    下三角形:同理,点个数一共有 ∑ k = 1 p − 1 2 [ k q p ] \sum_{k=1}^{\frac{p-1}{2}}[\frac{kq}{p}] k=12p1[pkq]
  • ( p − 1 2 ) ⋅ ( q − 1 2 ) = ∑ k = 1 p − 1 2 [ k q p ] + ∑ l = 1 q − 1 2 [ L p q ] (\frac{p-1}{2})·(\frac{q-1}{2})=\sum_{k=1}^{\frac{p-1}{2}}[\frac{kq}{p}]+\sum_{l=1}^{\frac{q-1}{2}}[\frac{Lp}{q}] (2p1)(2q1)=k=12p1[pkq]+l=12q1[qLp]

证毕。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/215559.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • feign原理详解_vip视频解析是什么原理

    feign原理详解_vip视频解析是什么原理Feign原理解析基本原理现在已经了解了Ribbon的负载均衡原理,我们可以来猜想下,Feign的原理,仅仅通过一个注解@FeignClient+一个接口,就可以服务之间的调用。通过@FeignClient在注解中的name,确定服务名,然后RibbonClient使用服务名去获取负载均衡器loadBalancer,再通过负载均衡算法获取到ip:port,然后构建的请求为http://nacos-component-provider/test/{id},当id=1

  • qt的内存映射

    qt的内存映射uchar*QFileDevice::map(qint64offset,qint64size,QFileDevice::MemoryMapFlagsflags=NoOptions)从偏移量开始将文件的大小字节映射到内存中。应该打开一个文件以使映射成功,但在映射内存之后,该文件不需要保持打开状态。当QFile被销毁或用这个对象打开一个新文件时,任何未被映射的映射都将被自动取消映射。映射将具有与文件相同的打开模式(读和/或写),除非使用maprivateOption,在这种情况下,始终可以

  • 水果篮一般装几种水果_one step closer水果篮子

    水果篮一般装几种水果_one step closer水果篮子904.水果成篮题目描述题目链接:904水果成蓝你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组fruits表示,其中fruits[i]是第i棵树上的水果种类。你想要尽可能多地收集水果。然而,农场的主人设定了一些严格的规矩,你必须按照要求采摘水果:你只有两个篮子,并且每个篮子只能装单一类型的水果。每个篮子能够装的水果总量没有限制。你可以选择任意一棵树开始采摘,你必须从每棵树(包括开始采摘的树)上恰好摘一个水果。采摘的水果应当符合篮子中的水果类型。

  • 常用电平转换电路的方法有_双击电平转换单级电路

    常用电平转换电路的方法有_双击电平转换单级电路电平转换在电路应用中屡见不鲜,方案设计也是五花八门,本文中整理了一些常见的电平转换电路,区别于成本功耗等因素的不同适用于不同的应用场景,读者可以用作参考,根据实际项目需求加以更改。1、上拉电阻加二极管方案(低成本)本方案适用于输入信号电平大于输出信号电平的转换电路上2、适用于输入信号大于输出信号的电平转换电路上,三极管选型要求:PNP三极管的饱和压降尽可能小,否则可能导致转换异常3、适用于大部分应用场景。属于典型应用。很多模块设计上都会采用这样的方案,成本低,而且转换的可靠性好4、2级反相

  • idea查看激活码(在线激活)

    idea查看激活码(在线激活),https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • kafka删除topic消息的四种方式[通俗易懂]

    kafka删除topic消息的四种方式[通俗易懂]方法一:快速配置删除法(简单粗暴,如果这个主题有程序还在消费都,此时KAFKA就gameover)1.kafka启动之前,在server.properties配置delete.topic.enable=true2.执行命令bin/kafka-topics.sh–delete–topictest–zookeeperzk:2181或者使用kafka-manager集群管理工具删除注意:如果kafka启动之前没有配置delete.topic.enable=true,topic只会标记

    2022年10月16日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号