夜深人静写算法(三十二)- 费马小定理

文章目录

  • 一、前言
  • 二、费马小定理
    • 1、费马小定理定义
    • 2、费马小定理证明
  • 三、素数判定和伪素数
    • 1、素数判定
    • 2、伪素数
  • 四、费马小定理的应用
    • 1、二分快速幂降幂
    • 2、模 p 逆元
    • 3、Rabin-Miller 素数判定
  • 五、费马小定理相关题集整理

一、前言

  今天要讲的内容,是数论中一个非常著名的定理 —— 费马小定理。阅读之前请确保对 二分快速幂 和 欧拉函数 已经有了一定的了解。本文的内容较短,但是作为 R a b i n   M i l l e r Rabin \ Miller Rabin Miller 大素数判定 有着重要的意义,所以打算单独拿出一个章节来讲,内容较为简单,适合打算放弃学习数论的小伙伴重新找回学习的动力和勇气。
  数论不像其它一些有趣的算法,可能对你没有很强的学习动力,但是所有数论的内容都是成体系的,任何一个公式的推导,可能都需要很强的前置知识,那么我们就把这些前置知识都学完,相信到那时候,任何一个数论题在你面前都易如反掌。在这里插入图片描述

二、费马小定理

1、费马小定理定义

【定义1】对于任意素数 p p p,和正整数 a a a,且 a a a 不是 p p p 的倍数,则: a p − 1 ≡ 1 ( m o d   p ) a^{p-1} \equiv 1 (mod \ p) ap11(mod p)

2、费马小定理证明

  • 我们在学习欧拉函数的时候,已经知道了欧拉定理,如下:
  • a ϕ ( n ) ≡ 1 ( m o d   n ) a^{\phi(n)} \equiv 1 (mod \ n) aϕ(n)1(mod n)
  • n n n 为 素数 p p p 时,它的欧拉函数为 ϕ ( p ) = p − 1 \phi(p) = p-1 ϕ(p)=p1,将它带入欧拉定理,得到:
  • a p − 1 ≡ 1 ( m o d   p ) a^{p-1} \equiv 1 (mod \ p) ap11(mod p)
  • 费马小定理,得证。
  • 注:关于欧拉定理的详细证明过程,可以参考以下这一篇文章,有兴趣的读者建议本文阅读完毕再看:
  • 夜深人静写算法(三十一)- 欧拉函数

三、素数判定和伪素数

1、素数判定

  • 我们可以用费马小定理来做什么?
  • 一个比较直观的想法就是:可以随机找几个和 n n n 互素的 a a a,然后对它计算:
  • a n − 1   m o d   n a^{n-1} \ mod \ n an1 mod n
  • 如果结果都为 1,我们就可以认为 n n n 是一个素数。
  • 如果这个结论成立,那么素数判定的时间复杂度就变成了 O ( C l o g 2 n ) O(Clog_2n) O(Clog2n),其中 C C C 为常数,代表找 C C C a a a 来做判定试验, O ( l o g 2 n ) O(log_2n) O(log2n) 则为利用二分快速幂进行判定的时间复杂度。
  • 以上假设成立吗?
  • 答案是 否!

2、伪素数

  • 事实上,费马小定理给出的是关于素数判定的 必要非充分 条件。
  • 如果 p p p 是素数,则 a p − 1 ≡ 1 ( m o d   p ) a^{p-1} \equiv 1 (mod \ p) ap11(mod p);相反,如果 a p − 1 ≡ 1 ( m o d   p ) a^{p-1} \equiv 1 (mod \ p) ap11(mod p),则不能推导出 p p p 是素数。
  • 原因是存在一些数 q q q,对于所有和 q q q 互素的 a a a,都能满足 a q − 1 ≡ 1 ( m o d   q ) a^{q-1} \equiv 1 (mod \ q) aq11(mod q),这样的数,我们称它为伪素数。
  • 第一个伪素数是 341,由 萨鲁斯 在 1819 年提出。

四、费马小定理的应用

1、二分快速幂降幂

【例题1】 给出一个大整数 n ( 1 ≤ n ≤ 1 0 100000 ) n(1 \le n \le 10^{100000}) n(1n10100000),求: 2 n   m o d   1000000007 2^n \ mod \ 1000000007 2n mod 1000000007

  • 任何一个正整数都就可以表示成 n = k x + m n = kx + m n=kx+m 的形式,其中 x x x 为除数, k k k 为商, m m m 为余数,并且 0 ≤ m < x 0 \le m \lt x 0m<x;其中除数 x x x 可以是任意非零整数。
  • 为了公式看起来整洁,我们用 p p p 来代替素数 1000000007 1000000007 1000000007,并且令 x = p − 1 x=p-1 x=p1 那么根据费马小定理,有:
  • 2 p − 1   m o d   p = 1 2^{p-1} \ mod \ p = 1 2p1 mod p=1
  • 原式就可以表示成:
  • 2 n   m o d   p = 2 k x + m   m o d   p = 2 k ( p − 1 ) + m   m o d   p = ( 2 k ( p − 1 )   m o d   p ) ∗ ( 2 m   m o d   p )   m o d   p = 2 m   m o d   p \begin{aligned}2^n \ mod \ p &= 2^{kx+m} \ mod \ p \\ &= 2^{k(p-1)+m} \ mod \ p \\ &= (2^{k(p-1)} \ mod \ p) * (2^{m} \ mod \ p) \ mod \ p \\ &= 2^m \ mod \ p \end{aligned} 2n mod p=2kx+m mod p=2k(p1)+m mod p=(2k(p1) mod p)(2m mod p) mod p=2m mod p
  • 这里的 m = n   m o d   ( p − 1 ) m = n \ mod \ (p-1) m=n mod (p1),可以利用大数取余求解。求得的 m ∈ [ 0 , p − 1 ) m \in [0, p-1) m[0,p1),再利用二分快速幂求解上面的式子即可。

2、模 p 逆元

【例题2】给定素数 p p p 和 正整数 a a a,求满足 a x ≡ 1 ( m o d   p ) ax \equiv 1 (mod \ p) ax1(mod p) 的最小正整数 x,如果不存在返回 -1。

  • 这个问题实际上是求正整数 a a a 在 模 p p p 域上的逆元。
  • 首先,当 a a a p p p 的倍数时, a x ≡ 0 ( m o d   p ) ax \equiv 0 (mod \ p) ax0(mod p),所以一定不存在,直接返回 -1;
  • 否则,根据费马小定理,我们可以知道:
  • a p − 1 ≡ 1 ( m o d   p ) a^{p-1} \equiv 1 (mod \ p) ap11(mod p)
  • 则可以得到:
  • a × a p − 2 ≡ 1 ( m o d   p ) a \times a^{p-2} \equiv 1 (mod \ p) a×ap21(mod p)
  • 对比原式,就可以得到:
  • x = a p − 2   m o d   p x = a^{p-2} \ mod \ p x=ap2 mod p

3、Rabin-Miller 素数判定

  • 对于一个很大的数 n n n(例如十进制表示有 100 100 100 位),如果还是采用试除法进行判定,时间复杂度必定难以承受,目前比较稳定的大素数判定法是 拉宾-米勒( R a b i n   M i l l e r Rabin \ Miller Rabin Miller)素数判定。
  • 判定过程用到了费马小定理,具体算法的推导和应用过程将在后续章节再进行展开讲解。

  • 关于 费马小定理 的内容到这里就暂时结束了,主要还是运用这个定理,对模数是素数的幂式进行降幂操作,如果还有不懂的问题可以留言告诉作者或者添加作者的微信公众号。

  • 本文所有示例代码均可在以下 github 上找到:github.com/WhereIsHeroFrom/Code_Templates

五、费马小定理相关题集整理

题目链接难度解析
HDU 1395 2^x mod n = 1★☆☆☆☆费马小定理 简化版
HDU 4704 Sum★☆☆☆☆【例题1】杨辉三角 + 费马小定理降幂
PKU 3641 Pseudoprime numbers★☆☆☆☆素数判定 + 费马小定理降幂
PKU 1845 Sumdiv★★☆☆☆因子和 + 逆元 + 费马小定理降幂
HDU 4869 Turn the pokers ★★★☆☆组合计数+ 费马小定理
HDU 3307 Description has only two Sentences★★★☆☆公式推导 + 费马小定理
HDU 6755 Fibonacci Sum★★★★☆逆元 + 组合公式 + 费马小定理 + 二分快速幂
HDU 4959 Poor Akagi★★★★★费马小定理 + 卢卡斯数通项公式 + 矩阵二分快速幂

热门文章

暂无图片
编程学习 ·

C语言二分查找详解

二分查找是一种知名度很高的查找算法&#xff0c;在对有序数列进行查找时效率远高于传统的顺序查找。 下面这张动图对比了二者的效率差距。 二分查找的基本思想就是通过把目标数和当前数列的中间数进行比较&#xff0c;从而确定目标数是在中间数的左边还是右边&#xff0c;将查…
暂无图片
编程学习 ·

GMX 命令分类列表

建模和计算操作命令&#xff1a; 1.1 . 创建拓扑与坐标文件 gmx editconf - 编辑模拟盒子以及写入子组(subgroups) gmx protonate - 结构质子化 gmx x2top - 根据坐标生成原始拓扑文件 gmx solvate - 体系溶剂化 gmx insert-molecules - 将分子插入已有空位 gmx genconf - 增加…
暂无图片
编程学习 ·

一文高效回顾研究生课程《数值分析》重点

数值分析这门课的本质就是用离散的已知点去估计整体&#xff0c;就是由黑盒子产生的结果去估计这个黑盒子。在数学里这个黑盒子就是一个函数嘛&#xff0c;这门课会介绍许多方法去利用离散点最大化地逼近这个函数&#xff0c;甚至它的导数、积分&#xff0c;甚至微分方程的解。…
暂无图片
编程学习 ·

在职阿里5年,一个28岁女软测工程师的心声

简单的先说一下&#xff0c;坐标杭州&#xff0c;14届本科毕业&#xff0c;算上年前在阿里巴巴的面试&#xff0c;一共有面试了有6家公司&#xff08;因为不想请假&#xff0c;因此只是每个晚上去其他公司面试&#xff0c;所以面试的公司比较少&#xff09; ​ 编辑切换为居中…
暂无图片
编程学习 ·

字符串左旋c语言

目录 题目&#xff1a; 解题思路&#xff1a; 第一步&#xff1a; 第二步&#xff1a; 第三步&#xff1a; 总代码&#xff1a; 题目&#xff1a; 实现一个函数&#xff0c;可以左旋字符串中的k个字符。 例如&#xff1a; ABCD左旋一个字符得到BCDA ABCD左旋两个字符…
暂无图片
编程学习 ·

设计模式--观察者模式笔记

模式的定义与特点 观察者&#xff08;Observer&#xff09;模式的定义&#xff1a;指多个对象间存在一对多的依赖关系&#xff0c;当一个对象的状态发生改变时&#xff0c;所有依赖于它的对象都得到通知并被自动更新。这种模式有时又称作发布-订阅模式、模型-视图模式&#xf…
暂无图片
编程学习 ·

睡觉突然身体动不了,什么是睡眠痽痪症

很多朋友可能有这样的体验&#xff0c;睡觉过程中突然意识清醒&#xff0c;身体却动弹不了。这时候感觉非常恐怖&#xff0c;希望旁边有一个人推自己一下。阳光以前也经常会碰到这样的情况&#xff0c;一年有一百多次&#xff0c;那时候很害怕晚上到来&#xff0c;睡觉了就会出…
暂无图片
编程学习 ·

深入理解C++智能指针——浅析MSVC源码

文章目录unique_ptrshared_ptr 与 weak_ptrstd::bad_weak_ptr 异常std::enable_shared_from_thisunique_ptr unique_ptr 是一个只移型别&#xff08;move-only type&#xff0c;只移型别还有std::mutex等&#xff09;。 结合一下工厂模式&#xff0c;看看其基本用法&#xff…
暂无图片
编程学习 ·

@TableField(exist = false)

TableField(exist false) //申明此字段不在数据库存在&#xff0c;但代码中需要用到它&#xff0c;通知Mybatis-plus在做写库操作是忽略它。,.
暂无图片
编程学习 ·

Java Web day15

第十二章文件上传和下载 一、如何实现文件上传 要实现Web开发中的文件上传功能&#xff0c;通常需要完成两步操作&#xff1a;一.是在Web页面中添加上传输入项&#xff1b;二是在Servlet中读取上传文件的数据&#xff0c;并保存到本地硬盘中。 需要使用一个Apache组织提供一个…
暂无图片
编程学习 ·

【51nod 2478】【单调栈】【前缀和】小b接水

小b接水题目解题思路Code51nod 2478 小b接水 题目 输入样例 12 0 1 0 2 1 0 1 3 2 1 2 1输出样例 6解题思路 可以发现最后能拦住水的都是向两边递减高度&#xff08;&#xff1f;&#xff09; 不管两个高积木之间的的积木是怎样乱七八糟的高度&#xff0c;最后能用来装水的…
暂无图片
编程学习 ·

花了大半天写了一个UVC扩展单元调试工具

基于DIRECTSHOW 实现的&#xff0c;用的是MFC VS2019. 详见&#xff1a;http://www.usbzh.com/article/detail-761.html 获取方法 加QQ群:952873936&#xff0c;然后在群文件\USB调试工具&测试软件\UVCXU-V1.0(UVC扩展单元调试工具-USB中文网官方版).exe USB中文网 USB中文…
暂无图片
编程学习 ·

贪心(一):区间问题、Huffman树

区间问题 例题一&#xff1a;区间选点 给定 N 个闭区间 [ai,bi]请你在数轴上选择尽量少的点&#xff0c;使得每个区间内至少包含一个选出的点。 输出选择的点的最小数量。 位于区间端点上的点也算作区间内。 输入格式 第一行包含整数 N&#xff0c;表示区间数。 接下来 …
暂无图片
编程学习 ·

C语言练习实例——费氏数列

目录 题目 解法 输出结果 题目 Fibonacci为1200年代的欧洲数学家&#xff0c;在他的着作中曾经提到&#xff1a;「若有一只免子每个月生一只小免子&#xff0c;一个月后小免子也开始生产。起初只有一只免子&#xff0c;一个月后就有两只免子&#xff0c;二个月后有三只免子…
暂无图片
编程学习 ·

Android开发(2): Android 资源

个人笔记整理 Android 资源 Android中的资源&#xff0c;一般分为两类&#xff1a; 系统内置资源&#xff1a;Android SDK中所提供的已经定义好的资源&#xff0c;用户可以直接拿来使用。 用户自定义资源&#xff1a;用户自己定义或引入的&#xff0c;只适用于当前应用的资源…
暂无图片
编程学习 ·

零基础如何在短时间内拿到算法offer

​算法工程师是利用算法处理事物的职业 算法&#xff08;Algorithm&#xff09;是一系列解决问题的清晰指令&#xff0c;也就是说&#xff0c;能够对一定规范的输入&#xff0c;在有限时间内获得所要求的输出。 如果一个算法有缺陷&#xff0c;或不适合于某个问题&#xff0c;执…
暂无图片
编程学习 ·

人工智能:知识图谱实战总结

人工智能python&#xff0c;NLP&#xff0c;知识图谱&#xff0c;机器学习&#xff0c;深度学习人工智能&#xff1a;知识图谱实战前言一、实体建模工具Protegepython&#xff0c;NLP&#xff0c;知识图谱&#xff0c;机器学习&#xff0c;深度学习 人工智能&#xff1a;知识图…
暂无图片
编程学习 ·

【无标题】

这里写自定义目录标题欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题&#xff0c;有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注…