#信息安全的数学基础
##目录
信息安全的数学基础
扩展欧几里得算法extent_gcd()
/********************
@function int extend_gcd(int a, int b, int &x, int &y)
@author ZXLiao
@data 2017-3-2 17:55:32
@param a coefficient_a
@param b coefficient_b
@param x solution_x
@param y solution_y
@return gcd(a, b) x y
********************/
int extend_gcd(int a, int b, int &x, int &y){
/*
大前提保证:
①ax + by = gcd(a, b)一定有整数解。
②bx + (a%b)y = gcd(b, a%b) 与①有相同解
如果b==0;那么方程就是ax=gcd(a, b) = a;
即x = 1;另取y = 0(也可以取其他值);
*/
if(b == 0){
x = 1;
y = 0;
return a;
}
int gcd = expand_gcd(b, a%b, x, y);
int t = x - a/b*y; // 表达式中有x,避免x改变;
x = y;
y = t;
return gcd; //返回的是gcd(a, b);
}
乘法逆元mod_inverse()
/******************
@function int mod_inverse(int a, int m)
@author ZXLiao
@data 2017-3-2 18:59:30
@param a
@param m mod
@return
if without the mod_inverse return -1
else return the inverse of a under modulo m
******************/
int mod_inverse(int a, int m){
if(gcd(a, m) != 1){
return -1;
}
int x, y;
extend_gcd(a, m, x, y);
return ((x % m + m) % m);
}
素数筛法求素数is_Prime()
/********************
@function bool is_Prime(int a)
@author ZXLiao
@data 2017-3-2 22:37:02
@param a integer
@return
if a is a Prime return true
else return false
********************/
#define __MAX 10000
bool Prime[__MAX];
void get_Prime(){
memset(Prime, true, sizeof(Prime));
Prime[0] = false;
for(int i = 1; i <= __MAX; i++){
if(Prime[i]){
int item = 2 * i + 1;
for(int j = item * item; j <= __MAX; j += (2 * item)){
Prime[j >> 1] = false;
}
}
}
}
bool is_Prime(int a){
if(a == 2) return true;
if(a & 1) return Prime[a >> 1];
else return false;
}
快速幂取模quick_pow()
/********************
@function int quick_pow(int a, int n, int __MOD)
@author ZXLiao
@data 2017-3-2 22:53:17
@param a
@param n
@param __MOD modulo
@return (a^n)%__MOD
********************/
int quick_pow(int a, int n, int __MOD){
if(n == 0) return 1;
if(n & 1) return a * quick_pow(a, n - 1, __MOD) % __MOD;
int t = quick_pow(a, n >> 1, __MOD);
return t * t % __MOD;
}
欧拉函数
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 1000005
#define M 78500 //预先算出1000000内的素数个数是78499
using namespace std;
bool is_Prime[N]; //用于素数筛法
int Prime[M]; //存放素数
long long int oula[N]; //存放欧拉函数
int p;
void Get_Prime(){ //首先筛法筛出1000000以内的素数
memset(is_Prime, 1, sizeof(is_Prime));
is_Prime[0] = is_Prime[1] = 0;
for(long long int i = 2; i < N; i++){
if(is_Prime[i]){
for(long long int j = i * i; j < N; j += i){
is_Prime[j] = 0;
}
}
}
}
void Init(){
p = 0;
for(int i = 0; i < N; i++){
if(is_Prime[i]){
Prime[p++] = i;
oula[i] = i - 1;
}
}
}
int main ()
{
Get_Prime();
//根据布尔数组的值,把素数存在数组内,并且对素数的欧拉函数进行赋值
Init();
/*
欧拉函数递推关系的推导:
对于oula[x]:
oula[x] = x *(p1 - 1)/p1 *(p2 - 1)/ p2 *(p3 - 1)/ p3*……*(pn - 1)/pn ①
此时,考虑oula[x/p1]的函数值
一:倘若x/p1此时还有一个素因子p1,那么:
oula[x/p1] = x/p1 *(p1 - 1)/p1 *(p2 - 1)/ p2 *(p3 - 1)/ p3*……*(pn - 1)/pn ②
对比①②两式可以得到oula[x] = oula[x/p1] * p1
二:倘若x/p1此时没有素因子p1,那么:
oula[x/p1] = x/p1 *(p2 - 1)/ p2 *(p3 - 1)/ p3*……*(pn - 1)/pn ③
对比①③两式可以得到oula[x] = oula[x/p1] * (p1 - 1)
*/
oula[0] = oula[1] = 1; //递推初始化
for(int i = 2; i < N; i++){
if(!oula[i]){ //对合数进行欧拉函数求解
for(int j = 0; j < p; j++){ //寻找一个素因子
if(i%Prime[j] == 0){ //找到一个素因子
int k = i/Prime[j]; //记录下i%Prime[j]
if(k%Prime[j] == 0){ //对i%Prime[j]再次进行判断,发现可再次整除
oula[i] = oula[k] * Prime[j]; //递推关系
}
else{ //递推关系
oula[i] = oula[k] * (Prime[j] - 1);
}
break;
}
}
}
}
return 0;
}
中国剩余定理
/*******************
@function int chinese_remaining_theory(struct data _data[])
@author ZXLiao
@data 2017-3-6 09:36:14
@param struct data _data: Congruence equations
@return x
*******************/
struct data{
int b;
int m;
};
int chinese_remaining_theory(struct data _data[]){
bool mark = 1;
for(int i = 0; i < N; i++){
for(int j = i + 1; j < N; j++){
if(gcd(_data[i].m, _data[j].m) != 1){
mark = 0;
break;
}
}
}
if(mark == 0){
return -1;
}
int M = 1;
int Mi[N];
int inv[N];
int X = 0;
for(int i = 0; i < N; i++){
M *= _data[i].m;
}
for(int i = 0; i < N; i++){
Mi[i] = M / _data[i].m;
}
for(int i = 0; i < N; i++){
inv[i] = mod_inverse(Mi[i], _data[i].m);
}
for(int i = 0; i < N; i++){
X += _data[i].b * inv[i] * Mi[i];
}
return X % M;
}
费马定理优化快速冥取模
/*******************
@function int Format_pow(int a, int n, int __MOD)
@author ZXLiao
@data 2017-3-6 09:48:44
@param a
@param n
@param __MOD modulo
@return a^n % __MOD
*******************/
int Format_pow(int a, int n, int __MOD){
if(gcd(a, __MOD) == 1){
return quick_pow(a, n % (__MOD - 1), __MOD);
}
return quick_pow(a, n, __MOD);
}