Richardの小小杂货铺 - algorithm
type: channel
link: https://blog.domineto.top/tag/algorithm/
items: [素性探测] Miller-Rabin 算法
items: [字符串匹配] BM算法
items: [分组密码] DES算法学习记录

[素性探测] Miller-Rabin 算法
type: item
date: 2019-10-19T18:05:00+00:00
description: Miller-Rabin 素性检验是一种素数判定法则，利用随机化算法判断一个数是合数还是可能是素数。卡内基梅隆大学的计算机系教授Gary Lee Miller首先提出了基于广义黎曼猜想的确定性算法，由于广义黎曼猜想并没有被证明，其后由以色列耶路撒冷希伯来大学的Michael O. Rabin教授作出修改，提出了不依赖于该假设的随机化算法。算法原理费马小定理Miller-Rabin 算法的依据是费马小定理: 假如 $a$ 是一个整数，$p$ 是一个质数，那么 $a^p$ 是 $p$ 的倍数，可以表示为$$ a^{p-1} \equiv 1(mod \; p) $$证明过程去 Wiki 上面看吧。那是不是当一个数 $p$ 满足任意 $a$ ，使得 $a^{p-1} \equiv 1(mod \; p)$ 成立时，它就一定是素数呢？答案是否定的，因为有些合数也满足费马小定理，比如 卢卡斯-卡米切尔数。虽然说费马小定理有一定概率误判，但如果我们通过一些操作，将这个误判的概率降低至非常小呢？比如对于一个数，我们的算法可以保证 99.99999% 的概率做出正确的判断，那么这个算法不也是很优秀的吗？所以我们有了 Miller-Rabin 算法。二次探测定理Miller-Rabin 算法在费马小定理的基础上加了一个二次探测定理:若 $p$ 是一个奇素数，则由费马小定理可知: 对于任意 $0 < x < p$ ，有 $x^2 \equiv 1(mod \; p)$ 。由此可推出 $x \equiv \pm 1 (mod \; p)$ 。证明如下:$$ x^2 \equiv 1(mod \; p) $$$$ x^2 - 1 \equiv 0(mod \; p) $$$$ (x + 1) (x - 1) \equiv 0(mod \; p) $$由以上式子可知:$$ (x + 1) \equiv 0(mod \; p) 或 (x - 1) \equiv 0(mod \; p) $$即$$ x \equiv \pm 1(mod \; p) $$二次探测定理的前提是这个数满足费马小定理，所以它可以看作是对费马测试的一个补充，减少它误判概率的。同费马小定理，我们这里用的也是它的逆否命题，即不满足二次探测定理的数一定不是素数。算法步骤上面介绍了 Miller-Rabin 算法的两个重要的定理，下面我们来讨论一下它是怎么通过这两个定理来判断一个数是否为素数的。因为 2 是唯一一个偶数素数，所以它需要单独判断。下面所说的素数都是不包括 2 的。我们假设需要判断的数是 $p$ 。由于 $p$ 是一个奇数，所以 $p - 1$ 是一个偶数。那么它就可以被分解为 $2^u * r$ 的形式(其中 $u, r$ 都是整数且 $r$ 为奇数)。为什么要分解成这种形式呢？不急，我们先继续往下看。根据费马小定理，如果 $p$ 是素数，那么一定有 $a^{2^k * t} \equiv 1 (mod \; p)$ 。这时候是不是很明显了？回头看看刚才的二次探测定理，把 $a^{2^k * t}$ 提出一个平方，不就刚好是它的形式吗？所以我们随机选择一个数 $a$ ，计算出 $a^t (mod \; p)$ ，然后让其不断自乘，同时结合二次探测定理进行判断。如果我们自乘后的数模 $p$ 的结果为 1 ，而之前的数模 $p$ 不为 $\pm 1$ ，就表明数 $p$ 是个合数(不满足二次探测定理)如此循环 $k$ 次，最后得到的数就是 $a^{p-1}$ 。如果这个数模 $p$ 的结果不为 1 的话，就表明 $p$ 是合数(不满足费马小定理)至此，我们就完成了一次素性探测了。当然，一次探测的误判率还是很高。所以我们需要多判断几次。正确率网上找的资料显示: 经过独立 $k$ 轮的 Miller-Rabin 算法误判的概率大约为 $1 / 4^k$ 。代码实现素数判断时需要用到快速幂。这个比较简单，不懂的可以看我之前写的快速幂C++ 实现由于我是用 C++ 实现的，大整数类懒得写上去，所以使用的时候要注意越界问题。(其实写好大整数类后把数据类型改一下就行了)Miller-Rabin.h#pragma once typedef long long long_t; inline long_t multiply_mod(const long_t& factor_1, const long_t& factor_2, const long_t& m = 0); inline long_t quick_pow_mod(const long_t& _base, const long_t& _index, const long_t& m = 0); bool MillerRabin(const l…

[字符串匹配] BM算法
type: item
date: 2019-10-14T05:24:00+00:00
description: BM 算法全称 Boyer-Moore 算法。它是一种非常高效的字符串匹配算法，有实验统计，它的性能是著名的KMP 算法的 3 到 4 倍。下面我们来讨论一下它是如何实现这么高的效率的。BM 算法核心思想我们把模式串和主串的匹配过程，看作模式串在主串中不停地往后滑动。当遇到不匹配的字符时，BF 算法和 RK 算法的做法是，模式串往后滑动一位，然后从模式串的第一个字符开始重新匹配。举个例子:主串: a b c d s a b d f n 模式串: a b d 滑动后: a b d在这个例子里，主串中的 'c'，在模式串中是不存在的，所以，模式串向后滑动的时候，只要 'c' 与模式串有重合，肯定无法匹配。所以，我们可以一次性把模式串往后多滑动几位，把模式串移动到 'c' 的后面:主串: a b c d s a b d f n 模式串: a b d 滑动后: a b d根据这个例子，很容易想到: 如果我们有办法找出一种规律，每次让模式串多向后滑动几位，那么匹配的效率不久大幅提升了吗？本篇文章所探讨的 BM 算法，本质上其实就是在寻找这种规律。借助这种规律，在模式串与主串匹配的过程中，当模式串和主串某个字符不匹配的时候，能够跳过一些肯定不会匹配的情况，将模式串往后多滑动几位。BM 算法原理分析BM 算法包含两部分，分别是坏字符规则（bad character rule）和好后缀规则（good suffix shift）。我们下面依次来探讨一下，这两个规则都是怎么工作的。坏字符规则之前学习的 BF 算法和 RK 算法在匹配的过程中，都是按模式串的下标从小到大的顺序，依次与主串中的字符进行匹配的。这种匹配顺序比较符合我们的思维习惯，而 BM 算法的匹配顺序比较特别，它是按照模式串下标从大到小的顺序，倒着匹配的:主串: a b c d s a b d f n 模式串: a b d 匹配顺序: 1 2 3我们从模式串的末尾往前倒着匹配，直到我们发现某个字符没法匹配的时候。我们把这个没有匹配的字符叫作坏字符（主串中的字符）。主串: a b c d s a b d f n 模式串: a b d这里面主串中的 'c' 就是坏字符。我们拿坏字符 'c' 在模式串中查找，发现模式串中并不存在这个字符，也就是说，字符 'c' 与模式串中的任何字符都不可能匹配。这个时候，我们可以将模式串直接往后滑动三位，将模式串滑动到 'c' 后面的位置，再从模式串的末尾字符开始比较。主串: a b c d s a b d f n 模式串: a b d 滑动后: a b d这是我们发现：模式串的最后一位 'd' 还是与主串中的字符 'a' 不匹配。那么我们还能向后滑动三位吗？答案是不行。我们很容易看出：坏字符 a 在模式串中是存在的，模式串中下标是 0 的位置也是字符 a。这种情况下，我们可以将模式串往后滑动两位，让两个 a 上下对齐，然后再从模式串的末尾字符开始，重新匹配。主串: a b c d s a b d f n 模式串: a b d 滑动后: a b d那么新的问题来了：第一次出现坏字符的时候，我们向后滑动了三位; 第二次出现坏字符的时候我们却只向后滑动了两位。那么这其中有没有什么规律呢？当发生不匹配的时候，我们把坏字符对应的模式串中的字符下标记作 si。如果坏字符在模式串中存在，我们把这个坏字符在模式串中的下标记作 xi。如果不存在，我们把 xi 记作 -1。那模式串往后移动的位数就等于 si-xi。!> 这里说的下标，都是字符在模式串的下标主串: a b c d s a b d f n 模式串: a b d xi=0 si=2这里需要说明一下：如果坏字符在模式串里多处出现，那我们在计算 xi 的时候，选择最靠后的那个，因为这样不会让模式串滑动过多，导致本来可能匹配的情况被滑动略过。利用坏字符规则，BM 算法在最好情况下的时间复杂度非常低，是 O(n/m)。比如，主串是 aaabaaabaaabaaab，模式串是 aaaa。每次比对，模式串都可以直接后移四位，所以，匹配具有类似特点的模式串和主串的时候，BM 算法非常高效。不过，单纯使用坏字符规则还是不够的。因为根据 si-xi 计算出来的移动位数，有可能是负数，比如主串是 aaaaaaaaaaaaaaaa，模式串是 baaa。不但不会向后滑动模式串，还有可能倒退。所以，BM 算法还需要用到“好后缀规则”。好后缀规则好后缀规则和坏字符规则思路很相似。举个例子:主串: a b c d s a d b b c c a b d c d 模式串: a b c d a b c 可以看到：模式串和主串有 2 个字符是匹配的，倒数第 3 个字符发生了不匹配的情况。这个时候该如何滑动模式串呢？当然，我们还可以利用坏字符规则来计…

[分组密码] DES算法学习记录
type: item
date: 2019-09-16T01:16:00+00:00
description: 这学期选了一门课: 计算机安全导论。据说主讲密码学，所以就先学习一下相关的知识啦~ 这几天学的是 DES算法。初学只写了 ECB 模式下的 DES。其他的等以后再说吧 XD1. 算法原理1.1 什么是 DES ?数据加密标准（英语：Data Encryption Standard，缩写为 DES）是一种对称密钥加密块密码算法，1976年被美国联邦政府的国家标准局确定为联邦资料处理标准（FIPS），随后在国际上广泛流传开来。它基于使用56位密钥的对称算法。这个算法因为包含一些机密设计元素，相对短的密钥长度以及怀疑内含美国国家安全局（NSA）的后门而在开始时有争议，DES因此受到了强烈的学院派式的审查，并以此推动了现代的块密码及其密码分析的发展。——Wikipedia1.2 算法流程DES 是一个分组加密算法，典型的 DES 以64位为分组对数据加密，加密和解密用的是同一个算法。其大致加密流程如下图:下面我来慢慢分析这些都是什么意思吧~2. 算法实现2.1 IP置换IP置换目的是将输入的64位数据块按位重新组合，并把输出分为L0、R0两部分，每部分各长32位。置换规则如下表所示：// 初始置换表 const int IP[64] = { 58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4, 62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8, 57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, 11, 3, 61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7 }; 表中的数字代表新数据中此位置的数据在原数据中的位置，即原数据块的第58位放到新数据的第1位，第50位放到第2位，……依此类推。置换后的数据分为 L0 和 R0 两部分， L0 为新数据的左32位，R0 为新数据的右32位。!> 要注意一点，位数是从左边开始数的，即最0x0000 0080 0000 0002最左边的位为1，最右边的位为64。2.2 生成子密钥从流程图中可以看出，我们在进行下一步加密的时候需要一个密钥 K，且之后的每一轮都需要密钥。我们知道 DES 需要输入一个64位的密钥，那剩余的密钥就肯定是从这个密钥变化来的。下面就讨论一下这些子密钥是怎么来的。2.2.1 去除奇偶校验位不考虑每个字节的第8位，将 DES 的密钥由64位减至56位，每个字节的第8位作为奇偶校验位。产生的56位密钥由下表生成（注意表中没有8,16,24，32,40,48,56和64这8位）： // 密钥置换表，将64位密钥变成56位 const int PC_1[56] = { 57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18, 10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36, 63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22, 14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4 };2.2.2 循环左移在DES的每一轮中，从56位密钥产生出不同的48位子密钥，确定这些子密钥的方式如下：将56位的密钥分成两部分，每部分28位。根据轮数，这两部分分别循环左移1位或2位。每轮移动的位数如下表：// 每轮左移的位数 const int shiftBits[16] = { 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1 };2.2.3 压缩置换移动后，从56位中选出48位。这个过程中，既置换了每位的顺序，又选择了子密钥，因此称为压缩置换。压缩置换规则如下表（注意表中没有9，18，22，25，35，38，43和54这8位）：// 压缩置换，将56位密钥压缩成48位子密钥 const int PC_2[48] = { 14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10, 23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2, 41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48, 44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32 };至此，新的密钥就已经计算出来了。按照这个方法进行16轮，就可以得到16个子密钥。2.3 加密处…