精华内容
下载资源
问答
  • 常用算法 RSA公钥密码的简介 数论核心: 欧拉函数 大整数素因子分解 提前了解~ 在数论,对正整数n,欧拉函数是小于或等于n的正整数中与n互质的数的数目(因此φ(1)=1) 欧拉函数计算通式: 个人理解:其实并不是很难...

    前言: 传统的对称加密非常容易破解,但目前对称加密还是非常安全的,主流是AES。非对称加密的主流是RSA。

    RSA
    虽稍后于MH背包公钥系统,但它是到目前为止应用最广的一
    种公钥密码。RSA的理论基础是数论的欧拉定理,它的安全
    性依赖于大整数的素因子分解的困难性。
    RSA可用于加密,签名等。

    但近代提出的量子计算机可能会打破这一稳定的格局~

    本文重点阐述 非对称算法RSA的实现~

    DES:Data Encrytion Standard(数据加密标准),对应算法是DEA

    1. 对称加密
    2. 同一个SK

    AES:Advanced Encrytion Standard(高级加密标准)

    1. 对称加密
    2. 一个SK扩展成多个子SK,轮加密

    RSA:RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用:

    1. 非对称加密,即:PK与SK不是同一个

    2. PK用于加密,SK用于解密

    3. PK决定SK,但是PK很难算出SK(数学原理:两个大质数相乘,积很难因式分解)

    4. 速度慢,只对少量数据加密

    公匙密码算法思想

    在这里插入图片描述

    常用算法

    在这里插入图片描述

    RSA公钥密码的简介

    在这里插入图片描述

    数论核心:

    欧拉函数

    大整数素因子分解

    提前了解~

    在数论,对正整数n,欧拉函数是小于或等于n的正整数中与n互质的数的数目(因此φ(1)=1)
    在这里插入图片描述
    欧拉函数计算通式:
    在这里插入图片描述
    个人理解:其实并不是很难理解,我们可以用概率论来讨论,给定一个数字x,我们给它拆成了几个质数p1,p2,p3…,pn相乘,每个质数的倍数,当然不是质数,每个质数的倍数出来的概率就是1/pi,1-1/pi就得到了满足该个pi的概率,连乘后就得到了同时满足所有这种情况的概率,因此得到欧拉数了~
    原始的欧拉函数公式也可以用我这个思想去推导,例如把24拆开拆成2^3*3,然后分别乘于概率就可以推导原公式了,千万不要死记硬背。


    在这里插入图片描述
    欧拉定理:
    在数论中,欧拉定理,(也称费马-欧拉定理)是一个关于同余的性质。欧拉定理表明,若n,a为正整数,且n,a互质,则:
    在这里插入图片描述
    举个例子:
    首先看一个基本的例子。令a = 3,n = 5,这两个数是互素的。比5小的正整数中与5互素的数有1、2、3和4,所以φ(5)=4。计算:a^{φ(n)} = 3^4 =81,而81= 80 + 1 Ξ 1 (mod 5)。与定理结果相符。
    这个定理可以用来简化幂的模运算。比如计算7^ 222 的个位数,实际是求7^ 222被10除的余数。7和10[[互素]],且φ(10)=4。由欧拉定理知7^ 4Ξ1(mod 10)。所以7^ 222=(7^ 4)^ 55*(7^ 2)Ξ1^ 55*7^2Ξ49Ξ9 (mod 10)。

    RSA的密钥对 生成算法

    对于重点进行解释
    第三和第四点
    这里取e非常有讲究,e得和n的欧拉数互质,不然如果e>=n的欧拉数,在加密中,mod后就为1了,如果e<n的欧拉数,则第四点不能成功找到满足条件的d了。
    在这里插入图片描述

    加解密过程

    在这里插入图片描述
    画个简单的例子:
    在这里插入图片描述

    推导过程:

    还有在大数的n次方求解问题中,很容易出现溢出情况,可以采用指数快速幂的方法。
    加密时首先将明文比特串分组,使得每个分组对应的十进制数小于n,即分组长度小于log2n。

    推导当m与n互素的情况

    在这里插入图片描述

    推导当m与n不互素的情况

    在这里插入图片描述

    实战应用


    在这里插入图片描述

    同态性普及

    1.RSA 算法对于乘法操作是同态的。
    2.Paillier 算法则是对加法同态的。
    3.Gentry算法则是全同态的。

    同态性可用于机器学习的隐私保护,则不用知道原始数据,通过处理后的数据就可以得到我们想要的结果,实现两个同态中的一个已经非常难得了,全同态是超级厉害的。
    全同态加密属于密码学领域。由于全同态加密支持无需解密,就能够对密文进行任意计算,因此可以立竿见影的解决数据隐私安全问题,有很大的应用需求。

    展开全文
  • C语言实现素因子分解

    2021-01-20 05:55:33
    给定某个正整数N,求其素因子分解结果,即给出其因式分解表达式 N = p1^k1 * p2^k2 *…*pm ^km。 输入格式说明: 输入long int范围内的正整数N。 输出格式说明: 按给定格式输出N的因式分解表达式,即 N = p1^...
  • 整数因子分解问题 算法设计思路: n=x1*x2*x3*…*xm,分治思想设计(分解过程): n=x1*(x2*x3*…*xm); n=x1*x2*(x3*…*xm); … n=x1*x2*x3*…*xm; 分治过程: void factor(int n){ int i; if(n==1)total++; else ...
  • 整数因子分解问题

    2015-09-20 01:31:10
    对于给定的正整数n,编程计算n共有多少种不同的分解式。由文件input.txt给出输入数据。第一行有1 个正整数n (1≤n≤2000000000)。将计算出的不同的分解式总数输出到文件output.txt。
  • PTA 整数素因子分解

    2020-05-14 11:05:18
    将正整数n分解为其素因子的乘积,其中n>=2并且在int范围内。Solution类的数据成员n代表需要分解的正整数,构造函数完成对数据成员n的初始化,声明了成员函数solve()实现对n的分解。请根据样例输出实现成员函数。...

    将正整数n分解为其素因子的乘积,其中n>=2并且在int范围内。Solution类的数据成员n代表需要分解的正整数,构造函数完成对数据成员n的初始化,声明了成员函数solve()实现对n的分解。请根据样例输出实现成员函数。注意输出时每行最后一个数字后面没有空格。

    裁判测试程序样例:

    #include <iostream>
    #include <cmath>
    using namespace std;
    
    class Solution {
    public:
        Solution(int num) {
            n = num;
        }
        void solve();//将n分解为素因子的乘积
    private:
        int n;
    };
    
    int main()
    {
        int n;
        while (cin >> n) {
            Solution obj(n);
            obj.solve();
        }
        return 0;
    }
    //你的代码将被嵌在这里
    

    输入样例:

    2
    3
    13
    24
    36
    1024
    65535

    输出样例:

    2=2
    3=3
    13=13
    24=2*2*2*3
    36=2*2*3*3
    1024=2*2*2*2*2*2*2*2*2*2
    65535=3*5*17*257

    AC代码:

    bool prime(int p)
    {
    	for (int div = 2; div<= sqrt(p); div++)
    		if (p % div == 0) return false;
    	return true;
    }
    void Solution::solve()
    {
    	cout << n << '=';
    	if (prime(n)) cout << n << endl;
    	else {
    		for (int div = 2, judge = 0;;) {
    			if (prime(div) && n % div == 0) {
    				if (judge) cout << '*';
    				cout << div;
    				n /= div;
    				judge = 1;
    				if (n == 1) break;
    			}
    			else {
    				if (judge) cout << '*';
    				judge = 0;
    				div++;
    			}
    		}
    		cout << endl;
    	}
    }
    
    展开全文
  • 大整数质因数分解(含模板)

    千次阅读 2019-04-07 21:18:05
    今天学习到了一个很强的模板----大整数质因数分解。 模板: const int MAXN = 1000005 ; int64_t mulEx(int64_t a , int64_t b , int64_t Mod) {///logn快速乘 if(!a) return 0 ; int64_t ans(0) ; while(b) ...

    今天学习到了一个很强的模板----大整数质因数分解。

    模板:

    const int MAXN = 1000005 ;
    
    int64_t mulEx(int64_t a , int64_t b , int64_t Mod) {///logn快速乘
        if(!a) return 0 ;
        int64_t ans(0) ;
        while(b)
        {
    		if(b & 1) ans = (ans + a) % Mod;
    		a <<= 1 ;
    		a %= Mod ;
    		b >>= 1 ;
        }
        return ans ;
    }
    
    int64_t powEx(int64_t base , int64_t n , int64_t Mod)
    {///快速幂
        int64_t ans(1) ;
        while(n)
        {
            if(n & 1) ans = mulEx(ans , base , Mod) ;
            base = mulEx(base , base , Mod) ;
            n >>= 1 ;
        }
        return ans ;
    }
    
    bool check(int64_t a , int64_t d , int64_t n)
    {
        if(n == a) return true ;
        while(~d & 1) d >>= 1 ;
        int64_t t = powEx(a , d , n) ;
        while(d < n - 1 && t != 1 && t != n - 1)
        {
            t = mulEx(t , t , n) ;
            d <<= 1 ;
        }
        return (d & 1) || t == n - 1 ;
    }
    
    bool isP(int64_t n)
    { ///判断大数是否是质数
        if(n == 2) return true ;
        if(n < 2 || 0 == (n & 1)) return false ;
        static int p[5] = {2 , 3 , 7 , 61 , 24251} ;
        for(int i = 0 ; i < 5 ; ++ i) if(!check(p[i] , n - 1 , n)) return false ;
        return true ;
    }
    
    int64_t gcd(int64_t a , int64_t b)
    {
        if(a < 0) return gcd(-a , b) ;
        return b ? gcd(b , a - b * (a / b)) : a ;
    }
    
    int64_t Pollard_rho(int64_t n , int64_t c)
    {///大数分解质因数
        int64_t i = 1 , k = 2 , x = rand() % n , y = x ;
        while(true)
        {
            x = (mulEx(x , x , n) + c) % n ;
            int64_t d = gcd(y - x , n) ;
            if(d != 1 && d != n) return d ;
            if(y == x) return n ;
            if(++ i == k)
            {
                y = x ;
                k <<= 1 ;
            }
        }
    }
    
    int64_t Fac[MAXN] , factCnt ;
    ///Fac存的是质因子,大小不一定按照顺序,有重复
    void factorization(int64_t n)
    {
        if(isP(n))
        {
            Fac[factCnt++] = n ;
            return ;
        }
        int64_t p(n) ;
        while(p >= n) p = Pollard_rho(p , rand() % (n - 1) + 1) ;
        factorization(p) ;
        factorization(n / p) ;
    }
    
    map<int64_t , int64_t> factMap ;
    ///遍历map的first表示因子,second表示次数
    
    void getFactor(int64_t x)
    {///不用判断是否是质数,但是比较费时间
     /**因此最好先判断一下是否是质数**/
    	srand(time(0)) ;
    	factCnt = 0 ;
    	factMap.clear() ;
    	factorization(x) ;
    	for(int i = 0; i < factCnt; ++i) ++ factMap[Fac[i]] ;
    }

    在这里面运用了Miller_Rabin定理和Pollard_rho算法,其中Miller_Rabin定理是进行判素数的,Pollard_rho算法是进行的分解,抱歉的是我暂时还不是很了解这两个定理和算法,有兴趣的可以取了解一下。后面有时间会将相关的给贴出来。

    注意:若对于1要进行特判。

    菜得不一样,菜出新高度。

    展开全文
  • 整数因子分解问题.zip

    2020-06-01 18:10:44
    利用C++实现整数因子分解问题,通过input.txt文件输入数据,最终的结果输出到output.txt文件中,对该过程有较好的理解
  • 包含两个代码,一个是分治法求格雷码,一个是分治法求整数因子分解问题 注释详细 实现很完美 用的python 直接pycharm打开就能用
  • 程序代码:/*E-mail: sunkai [at] msn [dot] com问题描述:大于1的正整数n可以分解为n=x1 * x2 * ... * xn例如n=12时12=1212=6*212=4*312=3*412=3*2*212=2*612=2*3*212=2*2*31<=n<=2000000000*//*分析:DP之...

    21c92f7342edc52acb5684b0b88bdcec.png程序代码:/*

    E-mail: sunkai [at] msn [dot] com

    问题描述:

    大于1的正整数n可以分解为n=x1 * x2 * ... * xn

    例如n=12时

    12=12

    12=6*2

    12=4*3

    12=3*4

    12=3*2*2

    12=2*6

    12=2*3*2

    12=2*2*3

    1<=n<=2000000000

    */

    /*

    分析:

    DP之记忆化搜索

    状态若用d[2000000000]则内存不足

    因此采用结构体记录状态

    经过简单数学推理,对于一个数N,它的因子数不超过N^(1/2)+1

    */

    #include

    #include

    struct DP

    {

    int num;

    int sum;

    } d[50000]={0};

    int max=0;

    void qsort(int low,int high,struct DP key[])

    {

    int i=low,j=high;

    struct DP tag=key[i];

    if(i

    {

    do

    {

    while(tag.num

    if(i

    {

    key[i]=key[j];

    i++;

    while(tag.num>=key[i].num && i

    if(i

    {

    key[j]=key[i];

    j--;

    }

    }

    }while(i

    key[i]=tag;

    qsort(low,j-1,key);

    qsort(i+1,high,key);

    }

    }

    int dfs(int left)

    {

    int i,p;

    int l,r,m;

    int count=0;

    l=0; r=max;

    while(l<=r)

    {

    m=(l+r)>>1;

    if(d[m].num

    }

    p=l; if(d[p].sum) return d[p].sum;

    for(i=1;i<=d[i].num;i++)

    {

    if(left%d[i].num==0) count+=dfs(left/d[i].num);

    }

    d[p].sum=count;

    return count;

    }

    int main(void)

    {

    int i,j,tmp;

    int n;

    scanf("%d",&n); tmp=sqrt(n);

    for(i=1;i<=tmp;i++)

    {

    if(n%i==0)

    {

    d[max].num=i; max++;

    d[max].num=n/i; max++;

    }

    } max--;

    qsort(0,max,d);

    d[0].sum=1;

    printf("%d\n",dfs(n));

    return 0;

    }

    [[it] 本帖最后由 卧龙孔明 于 2008-3-21 20:26 编辑 [/it]]

    展开全文
  • int i=2,n = 0; scanf("%d", &n); while (1) { for (i = 2; i <= n; i++)//能被i整除的数那么肯定能被i的倍数整除。...//每次因数分解完一个需除去该因子 break;//在...
  • 9718整数因子分解

    2013-10-19 19:26:52
    9718 整数因子分解 时间限制:1000MS 内存限制:1000K 提交次数:0 通过次数:0 题型: 编程题 语言: 无限制 Description 大于1的正整数 n 都可以分解为 n = x1 * x2 * ... * xm 例如:当n=12时,共有8种不同的分解...
  • 整数因子分解

    2019-04-15 11:32:40
    任意给定一个整数n,则n要么是一个素数,要么拥有一个不超过n\sqrt{n}n​的素因子。因此,当我们依次用不超过n\sqrt{n}n​的素数2,3,5…去除n的时候,要么,我们可以找到一个n的素因子p1p_1p1​,要么我们将得出结论...
  • 1.JAVA实现正整数素因子分解。 比如:60=2*2*3*5 。 代码块如下 import java.util.Scanner; /** * @kilimy */ public class Demo1 { public static void main(String[] args) { Scanner sc = new Scanner...
  • 整数因子分解问题(分治法\C++实现)

    热门讨论 2012-11-01 14:39:30
    Description 大于1的正整数 n 都可以分解为 n = x1 * x2 * ......递归实现整数因子分解的计数。 假设对正整数n的因子分解计数为solve(n)。 1)当n=1时,计数加1。 2)当n>1时,对每个因子i,计算solve(n/i)。
  • Python整数因子分解

    千次阅读 2019-10-04 22:24:30
    整数因子分解问题 问题描述: 大于1 的正整数n 可以分解为:n=X1 X 2 …Xm。 例如,当n= 12 时,共有8 种不同的分解式: 12= 12; 12=62; 12=43; 12=34; 12=322; 12=26; 12=232; 12=223。 编程...
  • 题目说明:给定某个正整数N,求其素因子分解结果,即给出其因式分解表达式 N = p1^k1* p2^k2*…*pm^km。输入格式说明:输入long int范围内的正整数N。输出格式说明:按给定格式输出N的因式分解表达式,即 N = p1^...
  • 素因子分解

    千次阅读 2020-11-11 19:54:32
    给定某个正整数 N,求其素因子分解结果,即给出其因式分解表达式 N=p​1​k1*p​2​k​2​​⋯p​m^​k​m,其中pi为因子并要求由小到输出,指数ki为pi的个数;当ki为1即因子pi只有一个时不输出ki。 输入格式: ...
  • python 递归实现整数因子分解问题

    千次阅读 2019-10-13 15:30:00
    python 递归实现整数因子分解问题 问题描述: 大于1 的正整数n 可以分解为几个因子的积,例如:12共有8 种不同的分解式: 12;62;43;34;322;26;232;223;对于给定正整数n,计算共有多少种不同的分解式。 ...
  • 整数因子分解问题(递归)

    千次阅读 2019-08-07 10:20:31
    对于给定的正整数n,计算n有多少种不同的分解式。 例如,当n=12时,有8种不同的分解式: 12=12; 12=6×2; 12=4×3; 12=3×4; 12=3×2×2; 12=2×6; 12=2×3×2; 12=2×2×3; 根据他的规律往下递归。 n的第一...
  • 给定某个正整数N,求其素因子分解结果,即给出其因式分解表达式N=p1​k1​⋅p2​k2​⋯pm​km​。 输入格式: 输入long int范围内的正整数 N。 输出格式: 按给定格式输出N的因式分解表达式,即N=p1^k1*p2^k2*...
  • PTA-素因子分解

    千次阅读 2020-12-22 14:46:14
    其中用了数组两个,第一个是用来存所有的因子,然后会有重复的。于是需要第二个数组,来整理。 总之,我相信还是有更简便的方法的,但是啊太忙了最近~~(其实是我这个人咸鱼)~~ 所以懒得继续优化了,不过小伙伴有...
  • 整数因子分解问题及其扩展问题的解答
  • 整数因子分解

    2016-04-05 12:00:51
    递归实现整数因子分解的计数。假设对正整数n的因子分解计数为solve(n)。 1)当n=1时,计数加1。 2)当n>1时,对n的每个因子i,计算solve(n/i)。 或者这样实现也可以: int solve2(int n) { int num=0; if(n==1) ...
  • C语言整数的素数因子分解

    千次阅读 2020-01-01 23:37:52
    给定某个正整数 N,求其素因子分解结果 输入格式: 输入long int范围内的正整数 N。 输出格式: 按给定格式输出N的因式分解表达式,即 N=p1^k1*p2^k2*…*pm^km 其中pi为因子并要求由小到输出, 指数...
  • 整数因子分解问题(分治)

    万次阅读 多人点赞 2019-04-10 20:15:26
    问题描述:将一个整数分解整数因子相乘,共有多少种不同的分解式? 问题分析:这个问题其实很简单,将一个数n从2到它本身依次求余,如果发现n求余后为0,证明这个被求余的数i是这个整数的因子,那么我们对n/i再...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 24,847
精华内容 9,938
关键字:

大整数素因子分解