RSA加密算法

wang 发表于 算法模板 分类,标签:
RSA的安全性依赖于大数分解,但是否等同于大数分解一直未能得到理论上的证明,因为没有证明破解RSA就一定需要作大数分解。假设存在一种无须分解大数的算法,那它肯定可以修改成为大数分解算法。RSA的一些变种算法已被证明等价于大数分解。不管怎样,分解n是最显然的攻击方法。人们已能分解多个十进制位的大素数。因此,模数n必须选大一些,因具体适用情况而定。python代码实现:# -*- coding: utf-8 -*-__author__ = "hql"'''python实现RSA加密算法:1,随意选择两个大的质数p和q,p不等于q,计算N=pq。2,根据欧拉函数,不大于N且与N互质的整数个数为(p-1)(q-1)3,选择一个整数e与(p-1)(q...

扩展欧几里德实现

发表于 算法模板 分类,标签:
 对于不完全为0的非负整数a,b.  gcd(a,b)表示a,b 的最大公约数。那么存在整数x, y使得 gcd(a,b)=a*x+b*y;不妨设a>b① ,当b=0 时,gcd(a,b)=a, 此时 x=1,y=0;② ,当 a*b<>0 时, 设 a*x+b*y=gcd(a,b);   (1)    b*x0+(a%b)*y0=gcd(b,a%b);   (2)由朴素的欧几里德公式;gcd(a,b)=gcd(b...

欧拉函数及其应用

发表于 算法模板 分类,标签:
 一.互质的概念:1、定义    互质(relativelyprimeì)又叫互素。若N个整数的最大公因数是1,则称这N个整数互质。  例如8,10的最大公因数是2,不是1,因此不是整数互质。  7,10,13的最大公因数是1,因此这是整数互质。  5和5不互质,因为5和5的公因数有1、5。  1和任何数都成倍数关系,但和任何数都互质。因为1的因数只有1,而互质数的原则是:只要两数的公因数只有1时,就说两数是互质数。1只有一个因数(所以1既不是质数(素数),也不是合数),无法再找到1和其他数的别的公因数了,所以1和任何数都互质(除0外)。  互质数的写法:如c与m互质,则写作(c,m)=1。  小学数学教材对互质数是这样定义的:“公约数只有1的两个数,叫做互质数。”  这里所说的“两个数”是指自然数。  “公约数只有1”,不能误说成“没...

费马小定理(可求乘法逆元)

发表于 算法模板 分类,标签:
 内容为:假如p是质数,且gcd(a,p)=1,那么a^(p-1)≡1(modp)。即:假如a是整数,p是质数,且a,p互质(即两者只有一个公约数1),那么a的(p-1)次方除以p的余数恒等于1。 使用:如果需要求得(a/b)%M的值。 由费马小定理得到如果b与M互质,则有b^(M-1) ≡1(modM) ,所以有b*b^(M-2) ≡1(modM)。那么b关于模M的乘法逆元为b^(M-2)。所以(a/b)modM=((a/b)modM)*((b*b^(M-2))modM)=(a/b)*(b*b^(M-2))modM =(a*(b^(M-2)))modM。然后利用快速幂快速得到b^(M-2)的值就可以了。 ...

从头到尾彻底理解KMP(转)

发表于 算法模板 分类,标签:
转自:http://blog.csdn.net/v_july_v/article/details/7041827作者:July时间:最初写于2011年12月,2014年7月21日晚10点全部删除重写成此文,随后的半个多月不断反复改进。后收录于新书《编程之法:面试和算法心得》第4.4节中。 1.引言  本KMP原文最初写于2年多前的2011年12月,因当时初次接触KMP,思路混乱导致写也写得混乱。所以一直想找机会重新写下KMP,但苦于一直以来对KMP的理解始终不够,故才迟迟没有修改本文。  然近期因开了个算法班,班上专门讲解数据结构、面试、算法,才再次仔细回顾了这个KMP,在综合了一些网友的理解、以及算法班的两位讲师朋友曹博、邹博的理解之后,写了9张PPT,发在微博上。随后,一不做二不休,索性将PPT上的内容整理到了本文之中(后来...

sort排序 c++

发表于 算法模板 分类,标签:
 c++的sort排序默认是进行升序,也可以自定义cmp()排序函数,根据需要进行排序。排序函数的形式为:boolcmp(inta,intb){    .........}a,b是需要排序的数组中的值,a在数组中的位置比b小,即a的下标比b小。如果返回true,则a,b的值不进行交换,若返回false,则交换a,b的值。从大到小排序的cmp()boolcmp(inta,intb){    returna>b;}vector也能用sort进行排序,一般调用sort的方法为:sort(s,s+n,cmp);s是一个int型数组,n为数组的大小,cmp为排序规则。用sort对vector进行排序是:sort(vc.begin(),vc.end(),cmp)vc是一个vector数组。...

协同过滤算法(转)

发表于 算法模板 分类,标签:
 原文:https://segmentfault.com/a/1190000004022134协作型过滤协同过滤是利用集体智慧的一个典型方法。要理解什么是协同过滤(CollaborativeFiltering,简称CF),首先想一个简单的问题,如果你现在想看个电影,但你不知道具体看哪部,你会怎么做?大部分的人会问问周围的朋友,看看最近有什么好看的电影推荐,而我们一般更倾向于从口味比较类似的朋友那里得到推荐。这就是协同过滤的核心思想。协同过滤一般是在海量的用户中发掘出一小部分和你品位比较类似的,在协同过滤中,这些用户成为邻居,然后根据他们喜欢的其他东西组织成一个排序的目录推荐给你。要实现协同过滤,需要以下几个步骤:搜集偏好寻找相近用户推荐物品搜集偏好首先,我们要寻找一种表达不同人及其偏好的方法。这里我们用python的嵌套字典来实现。在本章中所用的数据,是从国外的网站grou...

组合数取模

发表于 算法模板 分类,标签:
 1.利用整数唯一分解定理,求(n+1-m)*(n+m)! / (m!*(n+1)! )任何正整数都有且只有一种方法写出其素因子幂相乘的形式。比如18=2*3^2A=(p1^k1)*(p2^k2)*(p3^k3)*(p4^k4)*......*(pn^kn)  pi为素数还有把阶层看作一个数,比m!怎样求m!里面素数2的指数呢?cnt=0;  while(m) { m/=2;cnt+=m;} 就可以了,为什么呢?考虑m=4,则m!= 4*3*2*1,第一次m/=2,是计算m!里面有多少个数能整除2的(有4,2),所以cnt+=2,有两个数贡献了两个素数2,接下来第二次m/=2,是计算m!里面有多少个数能整除4的,有1个数又贡献了一...

acm(c语言)基础知识

发表于 算法模板 分类,标签:
 1. 数据表示范围 unsigned  int  0~4294967295  int  2147483648~2147483647unsignedlong0~4294967295long  2147483648~2147483647longlong的最大值:9223372036854775807longlong的最小值:-9223372036854775808unsignedlonglong的最大值:18446744073709551615__int64的最大值:9223372036854775807__int64的最小值:-9223372036854775808unsigned__int64的最大值:18446744073709551615&...

最长递增子序列 (Longest Increasing Subsequence)

发表于 算法模板 分类,标签:
 1.复杂度为O(n^2)const int maxn=100020;const int inf=0x3f3f3f3f;int dp[maxn];//以a[i]为结尾的最长自增子序列长度int a[maxn];int n;int LIS(int a[],int n)//最长上升子序列{    int m;    dp[0]=1;    for(int i=1;i<n;i++)    {      ...