草庐IT

密码学简单数论笔记(1):素数和模运算

xiaoyeah 2023-03-28 原文

  
参考资料:
1.https://www.bilibili.com/video/BV1x3411s7Sy/?spm_id_from=333.788&vd_source=e66dd25b0246f28e772d75f11c80f03c
2.余红兵:《数学奥林匹克小丛书(第二版)高中卷10————数论》

素数

  

素数的定义:
除了1和它本身以外不再有其他因数的自然数。亦即,除了1和n以外,并无其他正整数整除n的正整数.
1既不是素数,也不是合数。
n为合数,则有n=ab;n>a>1,n>b>1.

我们可以视正整数为3类数。1为单独一类数,其二素数,其三合数.
素数(prime number)的表示常用字母p。

引理2-1:任何大于1的整数必有素因子。

  
证明使用反证法。插播一句,带有“必有”字样的定理都可尝试反证法,正难则反。

我们设集合S包含所有大于1且没有素因子的整数,只需证明S为空集即可。假设S不为空集,m∈S是S中最小的整数(m>1且没有素因子)。
情况分为2种:
(1)m不可能为素数,因为任何素数都有素因子(它本身);
(2)m若为合数,则有m=ab(合数定义),则1<a<m,1<b<m;
既然a<m,必有a∉S.a必有素因子,设为p,因为p|a,且a|m,也即m必有素因子p,与m∈S矛盾,得证.

定理2-1 任何合数都至少有一个不超过n*1/2的素因子。(n>1是合数,则存在素数p,使得p<=n*1/2)

  
证明:
设任一合数n,根据定义有n=ab;
假设a>n*1/2,b>n*1/2,易证这种情况不存在,因为ab>n*1/2*n*1/2,矛盾于n=ab。同理,亦不可能有a,b<n*1/2.那么先得出结论,a,b其一必定不超过n*1/2.
假设此其一为a,根据引理2-1得出a必有素因子p,p|a。而a|n,所以p|n,满足p<=n*1/2.

判断n为素数的方法:如果所有素数p<=n*1/2,都不能整除n,则n是素数.

定理2-2(算术基本定理):任何非零整数n可以表示出如下乘积形式:n=±p1e1...prer。其中,p1...pr是互不相同的素数,e1...er是正整数.

  
1.该表示形式是唯一的(不计顺序)
2.认为±1可以表示成零个素数相乘的结果作为1.

接下来的文章中会证明该定理,此处暂时超纲.

欧几里得定理:素数有无穷多个.

  
其实它最好叫做欧几里得素数定理.
证明会使用算术基本定理。
假设素数仅有限个,设其为p1,...,pk;设M为这k个数的乘积,表示为M=p1...pk,设N=M+1.
显然,N>=2.
那么N也可以表示为一系列素数乘积的形式,则存在一个素数p,满足p|N.
且有p≠p1...pk(否则p|M,导致p|(N-M),有p|1,不可能)
所以,p不在p1...pk之中,这与假设相矛盾.

模运算

  
a mod b:设a,b∈Z且b>0,如果q,r∈Z满足a=qb+r,且0<=r<b,则定义:a mod b:=r.
在C,C++语言中mod表示为%.

对于负整数的模运算,则与正整数正好相反,
设a<0,b>0.a mod b可理解为a不断地加上b直至得数d>0(d<b)。
但事实上,还存在这种争议结果:求出的d只需满足0<|d|<|b|,也就是说假设-5%3,得数可以是1,也可以是-2.

现如今大多数人认可的是这个模运算定义:

若a,b为整数,c≠0,那么余数d满足a=kb+c(k∈Z).
且,0<=|r|<=|d|.

  
在MSVC2021和Python 3.8中,对于-5%3,前者输出了-2,后者输出了1.这表示不同的语言、编译器都会有不同的理解。
  

(重要)模运算的性质

  

  1. b|a即a mod b=0
  2. (a+b) mod n= (a mod n + b mod n)mod n
  3. (a-b) mod n= (a mod n - b mod n)mod n
  4. (axb) mod n= (a mod n x b mod n)mod n

模运算的性质第一条显而易见,除此之外模运算没有类似的除法性质(本身就包含了一重除法).

为什么说重要呢?因为运用该性质C++不容易发生算术溢出。预先设置一个模数,对每个因数取模再总体取模,这样不容易发生long long悲剧.

有关密码学简单数论笔记(1):素数和模运算的更多相关文章

  1. ruby - 触发器 ruby​​ 中 3 点范围运算符和 2 点范围运算符的区别 - 2

    请帮助我理解范围运算符...和..之间的区别,作为Ruby中使用的“触发器”。这是PragmaticProgrammersguidetoRuby中的一个示例:a=(11..20).collect{|i|(i%4==0)..(i%3==0)?i:nil}返回:[nil,12,nil,nil,nil,16,17,18,nil,20]还有:a=(11..20).collect{|i|(i%4==0)...(i%3==0)?i:nil}返回:[nil,12,13,14,15,16,17,18,nil,20] 最佳答案 触发器(又名f/f)是

  2. ruby - 简单获取法拉第超时 - 2

    有没有办法在这个简单的get方法中添加超时选项?我正在使用法拉第3.3。Faraday.get(url)四处寻找,我只能先发起连接后应用超时选项,然后应用超时选项。或者有什么简单的方法?这就是我现在正在做的:conn=Faraday.newresponse=conn.getdo|req|req.urlurlreq.options.timeout=2#2secondsend 最佳答案 试试这个:conn=Faraday.newdo|conn|conn.options.timeout=20endresponse=conn.get(url

  3. ruby - 用 Ruby 编写一个简单的网络服务器 - 2

    我想在Ruby中创建一个用于开发目的的极其简单的Web服务器(不,不想使用现成的解决方案)。代码如下:#!/usr/bin/rubyrequire'socket'server=TCPServer.new('127.0.0.1',8080)whileconnection=server.acceptheaders=[]length=0whileline=connection.getsheaders想法是从命令行运行这个脚本,提供另一个脚本,它将在其标准输入上获取请求,并在其标准输出上返回完整的响应。到目前为止一切顺利,但事实证明这真的很脆弱,因为它在第二个请求上中断并出现错误:/usr/b

  4. ruby-on-rails - 简单的 Ruby on Rails 问题——如何将评论附加到用户和文章? - 2

    我意识到这可能是一个非常基本的问题,但我现在已经花了几天时间回过头来解决这个问题,但出于某种原因,Google就是没有帮助我。(我认为部分问题在于我是一个初学者,我不知道该问什么......)我也看过O'Reilly的RubyCookbook和RailsAPI,但我仍然停留在这个问题上.我找到了一些关于多态关系的信息,但它似乎不是我需要的(尽管如果我错了请告诉我)。我正在尝试调整MichaelHartl'stutorial创建一个包含用户、文章和评论的博客应用程序(不使用脚手架)。我希望评论既属于用户又属于文章。我的主要问题是:我不知道如何将当前文章的ID放入评论Controller。

  5. ruby - 使用 Ruby 通过 Outlook 发送消息的最简单方法是什么? - 2

    我的工作要求我为某些测试自动生成电子邮件。我一直在四处寻找,但未能找到可以快速实现的合理解决方案。它需要在outlook而不是其他邮件服务器中,因为我们有一些奇怪的身份验证规则,我们需要保存草稿而不是仅仅发送邮件的选项。显然win32ole可以做到这一点,但我找不到任何相当简单的例子。 最佳答案 假设存储了Outlook凭据并且您设置为自动登录到Outlook,WIN32OLE可以很好地完成此操作:require'win32ole'outlook=WIN32OLE.new('Outlook.Application')message=

  6. postman——集合——执行集合——测试脚本——pm对象简单示例02 - 2

    //1.验证返回状态码是否是200pm.test("Statuscodeis200",function(){pm.response.to.have.status(200);});//2.验证返回body内是否含有某个值pm.test("Bodymatchesstring",function(){pm.expect(pm.response.text()).to.include("string_you_want_to_search");});//3.验证某个返回值是否是100pm.test("Yourtestname",function(){varjsonData=pm.response.json

  7. Qt Designer的简单使用 - 2

    在前面两节的例子中,主界面窗口的尺寸和标签控件显示的矩形区域等,都是用C++代码编写的。窗口和控件的尺寸都是预估的,控件如果多起来,那就不好估计每个控件合适的位置和大小了。用C++代码编写图形界面的问题就是不直观,因此Qt项目开发了专门的可视化图形界面编辑器——QtDesigner(Qt设计师)。通过QtDesigner就可以很方便地创建图形界面文件*.ui,然后将ui文件应用到源代码里面,做到“所见即所得”,大大方便了图形界面的设计。本节就演示一下QtDesigner的简单使用,学习拖拽控件和设置控件属性,并将ui文件应用到Qt程序代码里。使用QtDesigner设计界面在开始菜单中找到「Q

  8. LC滤波器设计学习笔记(一)滤波电路入门 - 2

    目录前言滤波电路科普主要分类实际情况单位的概念常用评价参数函数型滤波器简单分析滤波电路构成低通滤波器RC低通滤波器RL低通滤波器高通滤波器RC高通滤波器RL高通滤波器部分摘自《LC滤波器设计与制作》,侵权删。前言最近需要学习放大电路和滤波电路,但是由于只在之前做音乐频谱分析仪的时候简单了解过一点点运放,所以也是相当从零开始学习了。滤波电路科普主要分类滤波器:主要是从不同频率的成分中提取出特定频率的信号。有源滤波器:由RC元件与运算放大器组成的滤波器。可滤除某一次或多次谐波,最普通易于采用的无源滤波器结构是将电感与电容串联,可对主要次谐波(3、5、7)构成低阻抗旁路。无源滤波器:无源滤波器,又称

  9. ruby - 带括号和 splat 运算符的并行赋值 - 2

    我明白了:x,(y,z)=1,*[2,3]x#=>1y#=>2z#=>nil我想知道为什么z的值为nil。 最佳答案 x,(y,z)=1,*[2,3]右侧的splat*是内联扩展的,所以它等同于:x,(y,z)=1,2,3左边带括号的列表被视为嵌套赋值,所以它等价于:x=1y,z=23被丢弃,而z被分配给nil。 关于ruby-带括号和splat运算符的并行赋值,我们在StackOverflow上找到一个类似的问题: https://stackoverflow

  10. ruby - 使用 Ruby,计算 n x m 数组的每一列中有多少个 true 的简单方法是什么? - 2

    给定一个nxmbool数组:[[true,true,false],[false,true,true],[false,true,true]]有什么简单的方法可以返回“该列中有多少个true?”结果应该是[1,3,2] 最佳答案 使用转置得到一个数组,其中每个子数组代表一列,然后将每一列映射到其中的true数:arr.transpose.map{|subarr|subarr.count(true)}这是一个带有inject的版本,应该在1.8.6上运行,没有任何依赖:arr.transpose.map{|subarr|subarr.in

随机推荐