模指数运算&素性测试

模指数运算与素性测试是密码学中经常要用到的学法，掌握一些基本的实现原理有助于后续的学习。

模指数运算

法1

计算a^e mod m , 底数a , 指数e , 模数m

常应用于RSA密码

例：计算2⁹⁰ mod 13

可用pow(base , exponent) , 但结果容易溢出

法2

循环指数次，每次都乘底数再%m , 边乘边模

复杂度O（e）

法3

分 - 治 - 归并

分：2⁹⁰ = 2⁵⁰*2⁴⁰
治：2⁵⁰ mod 13 = 3 ， 2⁴⁰ mod 13 = 4
归并: 2⁹⁰ mod 13 = 3*4 mod 13 = 12

上例只分了一次，其实还可以往下分的，那么就需要制定一个分拆的规则

以二进制方式分拆指数：e = 1010100...（e对应的二进制） = D_n-1+D_n-2+....+D₀

而a^{D_n-1+D_n-2+....+D₀} =a^Dn-1 * a^Dn-2 * ..... * a^D0

举个栗子：计算5¹¹⁷ mod 19

分拆指数：117 = 1 + 4 + 16 + 32 + 64
分治计算：5¹ mod 19 = 5
5² mod 19 = 6
5⁴ mod 19 = 17
5⁸ mod 19 = 4
5¹⁶ mod 19 = 16
5³² mod 19 = 9
5⁶⁴ mod 19 = 5
归并：分拆指数对应的结果相乘再mod19（边乘边模
= 5 * 17 * 16 * 9 * 5 mod 19 = 1

复杂度O（log₂e）

代码实现

size_t mod_exp(size_t a, size_t e, size_t m)
{
	// TODO: return the answer of a^e mod m";
	size_t res = 1;

	//遍历e的二进制
    while(e != 0){
        if(e%2 == 1){
            res = (res*a)%m;
        }
        a = (a*a)%m;
        e >> 1;
        
    }
	return res;
}

素性测试

给定一个数n 判断其是否为素数。

数学应用：所有合数都可由素数的乘积表示，且这些素因子按大小排列后是唯一的。

检测方法

法1

根据定义，遍历2 - n看是否有数整除n

法2

遍历2 - n^1/2即可

因为如果存在j > n^1/2 是 n 的因子的话，那么一定会有i 也是n的因子且 i < n^1/2

所以只需要跑2 - 根n就行了

法3

找出2 - n^1/2中的素数，遍历这些素数是否整除n即可

因为任意合数都可以表示为素数的乘积，判断合数就重复判断了。

基于法3我们可以写出大致检测的步骤：

确定待筛集合{2，3，4.........，n^1/2}
基于{2，3，4.........，n^1/2}的Eratosthenos筛选
筛选后的元素与n整除判定

Eratosthenos筛选法：

产生2 - N范围内的所有素数，不适用于产生某个特定范围内的全部素数。

大致过程：

取第一个素数2，删掉{2...,N}中除2以为所有的2的倍数
认定2的下一个数（未被删掉）为素数（这里为3），在后面的整数中删掉该数的倍数
重复第二步。直到后面没有数可以删了。

举个栗子：判断2543是否为素数

2543^1/2 ≈ 50 ，确定待筛集合{2,3,4,5...50}
使用Eratosthenos筛选法在该集合中筛选出所有素数：2,3,5,7,11,13,17....,47
整除判定，2543整除这15个素数，结果都不是整数，那么2543一定为素数

代码实现：

bool prime_test(unsigned int a)
{
	//TODO: return true when "a" is a prime | False when "a" is not a prime";
	size_t sqr = (size_t)sqrt((double)a);
	
	//0、1、2比较特殊 需要特判下
	if (a == 1 || a ==0)	return false;
	if (a == 2)				return true;

	//取2 - sqr个空间
	//并初始化为0
	int* num;
	num = new int[sqr + 10];
	memset(num, 0, sqr + 10);


	//遍历2 - sqr个空间
	//若发现没有筛过则假定其为素数
	//再遍历其后的数并将能整除该数的数标记为1
	for (int i = 2; i <= sqr; i++)
	{
		if (num[i] == 0)
		{
			for (int j = i * i; j <= sqr; j++)
			{
				if (j % i == 0) num[j] = 1;
			}

		}
	}

	//标记为0的数为筛出的素数
	bool flag = true;
	for (int i = 2; i <= sqr; i++)
	{
		if (num[i] == 0 && a % i == 0)
		{
			flag = false; 
			break;
		}
	}
    
	delete []num;
	return flag;
}

Gridea