精华内容
下载资源
问答
  • 蒙哥马利幂模运算

    千次阅读 2013-04-20 17:21:15
    蒙哥马利(Montgomery)幂模运算是快速计算a^b%k的一种算法,是RSA加密算法的核心之一。 特点及原理 蒙哥马利模乘的优点在于减少了取模的次数(在大数的条件下)以及简化了除法的复杂度(在2的k次幂的进制下除法仅...

    蒙哥马利幂模运算

    简介

    蒙哥马利(Montgomery)幂模运算是快速计算a^b%k的一种算法,是RSA加密算法 的核心之一。

    特点及原理

    蒙哥马利模乘的优点在于减少了取模的次数(在大数的条件下)以及简化了除法的复杂度(在2的k次幂的进制下除法仅需要进行左移操作)。模幂运算是RSA 的核心算法,最直接地决定了RSA 算法的性能。
    针对快速模幂运算这一课题,西方现代数学家提出了大量的解决方案,通常都是先将幂模运算转化为乘模运算。
    例如求D=C^15%N
    由于:a*b % n = (a % n)*(b % n) % n
    所以令:
    C1 =C*C % N =C^2 % N
    C2 =C1*C % N =C^3 % N
    C3 =C2*C2 % N =C^6 % N
    C4 =C3*C % N =C^7 % N
    C5 =C4*C4 % N =C^14 % N
    C6 =C5*C % N =C^15 % N
    即:对于E=15的幂模运算可分解为6 个乘模运算,归纳分析以上方法可以发现:
    对于任意指数E,都可采用以下算法计算D=C**E % N:
    D=1
    WHILE E>=1
    IF E%2=0
      C=C*C % N
      E=E/2
    ELSE
      D=D*C % N
      E=E-1
    RETURN D
    展开全文
  • 幂模运算

    千次阅读 2014-11-02 09:57:34
    在众多的加密算法中都需要进行幂的取模运算,比如在RSA算法中需要计算ne mod N,我们称之为幂模算法。 我

    在众多的加密算法中都需要进行幂的取模运算,比如在RSA算法中需要计算ne mod N,我们称之为幂模算法。

    我经常第一个想到的算法就是用pow(),最后发现根本得不到想要的结果,测试才方向是因为溢出。

    当指数很大时我们采用两种方法。

    方法一

    利用性质:a*b%m=a*(b%m)%m
    a^b%m=(a%m)^b%m
    int mod(int a,int b,int m){
        int result = 1;
        for(int i=0;i<b;i++) {
            result = (result*a) %m;
        }
        return result;
    }
    但当b很大时这个方法循环的次数还是相对太大,不是很理想。

    方法二

    进一步研究指数b的二进制表示发现,对任意的整数b都可表示为:


    • n表示b的实际二进制位数
    • bi表示该位是0或1

    因此,ab可表示为:

    即用b的每一位表示a的每一项,而对任意相邻的两项存在平方关系,即:

    因此我们构造下面的算法:

    • 把b转换为二进制表示,并从右至左扫描其每一位(从低到高)
    • 当扫描到第i位时,根据计算a的第i项的模,这里先是假设多有的bi都是1,记录下来,当真正的bi为1时供result使用

      base变量表示第i-1位时计算出的模。
    • 如果第i位为1,即bi=1,则表示该位需要参与模运算,计算结果 result = (result*base) mod m;其中result为前i-1次的计算结果。
    int mod(int a,int b,int m){
        int result = 1;
        int base = a;
        while(b>0){
             if(b & 1==1){//与1按位与
                result = (result*base) % m;
             }
             base = (base*base) %m;//难点在这
             b>>=1;//相当于除2
        }
        return result;
    }
    把时间复杂度降到了lgb,大大优于方法一。



    其实还需要考虑m为负数的情况

    leetcode   50. Pow(x, n)
    Implement pow(xn).

    为什么new要用unsigned long long?因为n可能是INT_MIN
    class Solution {
    public:
    	double myPow(double x, int n) {
    		double res = 1;
    		unsigned int newn = n;
    		if (n < 0) {
    			x = 1 / x;
    			newn = -n;
    		}
    		while (newn){
    			if (newn & 1){
    				res *= x;
    			}
    			x *= x;
    			newn >>= 1;
    		}
    
    		return res;
    	}
    };






    展开全文
  • 蒙哥马利幂模运算 - 简介    ...蒙哥马利(Montgomery)幂模运算是快速计算a^b%k的一种算法,是RSA加密算法的核心之一。 蒙哥马利幂模运算 - 特点及原理         &nbs...

    蒙哥马利幂模运算 - 简介

               蒙哥马利(Montgomery)幂模运算是快速计算a^b%k的一种算法,是RSA加密算法的核心之一。

    蒙哥马利幂模运算 - 特点及原理

              蒙哥马利模乘的优点在于减少了取模的次数(在大数的条件下)以及简化了除法的复杂度(在2的k次幂的进制下除法仅需要进行左移操作)。

    模幂运算是RSA 的核心算法,gh最直接地决定了RSA 算法的性能。 针对快速模幂运算这一课题,西方现代数学家提出了大量的解决方案,通常都是

    先将幂模运算转化为乘模运算。 

    例如求D=C^15%N
    由于:a*b % n = (a % n)*(b % n) % n
    所以令:
      C1 =C*C % N =C^2 % N
      C2 =C1*C % N =C^3 % N
      C3 =C2*C2 % N =C^6 % N
      C4 =C3*C % N =C^7 % N
      C5 =C4*C4 % N =C^14 % N
      C6 =C5*C % N =C^15 % N
    即:对于E=15的幂模运算可分解为6 个乘模运算,归纳分析以上方法可以发现:
    对于任意指数E,都可采用以下算法计算D=C**E % N:
      D=1
      WHILE E>=0
      IF E%2=0
      C=C*C % N
      E=E/2
      ELSE
      D=D*C % N
      E=E-1
      RETURN D
      继续分析会发现,要知道E 何时能整除 2,并不需要反复进行减一或除二的操作,只需验证E 的二进制各位是0 还是1 就可以了,从左至右或从右至左验证都可以,从左至右会更简洁,
      设E=Sum[i=0 to n](E*2**i),0<=E<=1
      则:
      D=1
      FOR i=n TO 0
      D=D*D % N
      IF E=1
      D=D*C % N

     

      RETURN D

     

    这样,模幂运算就转化成了一系列的模乘运算。

    蒙哥马利幂模运算 - C++实现

    
     
    1. /*例如求D=C^15%N
    2. 由于:C*k % n = (C % n)*(k % n) % n
    3. 所以令:
    4. C1 = C*C % N =C^2 % N 1 15
    5. C2 = C1*C % N =C^3 % N 3 7
    6. C3 = C2*C2 % N =C^6 % N
    7. C4 = C3*C % N =C^7 % N 7 3
    8. C5 = C4*C4 % N =C^14 % N
    9. C6 = C5*C % N =C^15 % N 15 1
    10. 蒙哥马利算法*/
    11. #include <iostream>
    12. using namespace std;
    13. //base 底数,exponential 指数,mod 模
    14. __int64 base, exp,mod; //base^exp % mod
    15. __ int64 Montgomery()
    16. {
    17. __int64 res = 1;
    18. while( exp)
    19. {
    20. if ( exp& 1 )
    21. res = (res*base) % mod;
    22. exp >>= 1;
    23. base = (base*base) % mod;
    24. }
    25. return res;
    26. }
    27. int main()
    28. {
    29. int T;
    30. cin >> T;
    31. while(T--)
    32. {
    33. cin >> base >> exp >> mod;
    34. cout << Montgomery() << endl;
    35. }
    36. return 0;
    37. }

     

     

     

    本文转自https://blog.csdn.net/leolinsheng/article/details/17490769
    展开全文
  • 大数幂模运算

    千次阅读 2017-05-25 12:05:27
    我们知道对于像 7%2,3%5这样的题,计算机很容易算出它们的结果,但是如果我们需要计算 7^123456789%65536这样的值呢,这时普通的计算方式可能就要花费很久的时间了,有没有简单的方法可以算出来这类大数的呢?

    大数幂的模运算

    题目

      我们知道对于像 7%2,3%5 这样的题,计算机很容易算出它们的结果,但是如果我们需要计算 7123456789%65536 这样的值呢,这时普通的计算方式可能就要花费很久的时间了,有没有简单的方法可以算出来这类大数的模呢?

    分析

    假设我们有整数a, b与除数m ,那么假设
    a % m = j , b % m = t , 有整数 i , s , 使

    a=im+jb=sm+t

    所以有
    ab=(im+j)(sm+t)=ism2+jsm+itm+jt

    推出
    (ab)modm=(ism2+jsm+itm+jt)modm=jtmodm=((amodm)(bmodm))modm

    所以
    对于像 7123456789%65536 这样的大数幂模运算,我们可以把大数幂m拆分成形如 m=m1+m2+...+mn 这样的形式,那么 nm=nm1+m2+...+mn=nm1nm2...nmn ,这样通过上面的公式我们就可以很容易算出大数幂了.
    因为
    abcmodm=((ab)c)modm=(((ab)modm)(cmodm))modm=(((amodm)(bmodm)modm)(cmodm))modm

    依次类推既可.

    我们再考虑大数幂m要如何分解成形如 m=m1+m2+...+mn 的形式.
    观察 211=21+2+8=21×20+1×21+0×22+1×23 .
    所以
    可以把大数幂m写成二进制,然后只取值为1的位,和这一位在二进制中从右到左的位数(从0开始计算),就可以得到这个大数幂的分解式了.

    代码

    // m为底数,pow为指数,n为除数
    int getMod(int m, int pow, int n)
    {
        int x = 1;
        int power = m % n;
        int mask = 1;
        for(int i = 0; i < 32; i++) {
            if((pow & mask) != 0) {
                x = (x * power) % n;
            }
            power = (power * power) % n;
            mask = mask << 1;
        }
        return x;
    }

    ps

    如果计算 ammodp 时发现p是素数而且a与p互质,使用费马小定理可以更快算出结果,因为这时 ap11(modp) 这个可以自己去了解一下.

    展开全文
  • https://blog.csdn.net/chen77716/article/details/7093600
  • 蒙哥马利(Montgomery)幂模运算是快速计算a^b%k的一种算法,是RSA加密算法的核心之一。 蒙哥马利模乘的优点在于减少了取模的次数(在大数的条件下)以及简化了除法的复杂度(在2的k次幂的进制下除法仅需要进行左移...
  • 有朋友问我的博文《素性测试》中的Miller-Rabin算法的大数模幂运算快速算法怎么理解,由于在《素性测试》中没有讲解算法原理,所以在此单独一个篇文章详细讲这个算法。这是一个在密码学中比较重要的算法,在我的...
  • 相关数学知识二:快速幂运算 以求a的b次方为例,由于要乘b次a,此时的时间复杂度为O(b);如果要求a的的平方的b/2次,只需要乘b/2次(如果b是奇数,要再乘一个a),时间复杂度减半,以此类推,直到b=1时,此时的...
  • 模运算

    2014-04-20 10:39:42
    模运算在数论和程序设计中都有着广泛的应用,从奇偶数的判别到素数的判别,从模运算到最大公约数的求法,从孙子问题到凯撒密码问题,无不充斥着模运算的身影。  例如11 Mod 2,值为1   上述模运算多用于程序...
  • 模幂运算的几种解决方法

    千次阅读 2010-10-28 23:59:00
    模幂运算是RSA的核心算法,最直接地决定了RSA算法的性能。针对快速模幂运算这一课题,西方现代数学家提出了大量的解决方案,通常都是先将模幂运算转化为运算
  • ​ 加密算法中,模运算(包括模乘、模运算)是难以避免的,如何高效地进行模运算,是提高算法效率的一个关键。 直观的想法 ​ 在数学上,模运算相当于是取余数的过程。以 x÷n=c⋯⋯dx \div n = c \cdots\cdots dx...
  • 点击上方蓝字设为星标东哥带你搞定算法~今天来聊一道与数学运算有关的算法题目,LeetCode 372 题 Super Pow,让你进行巨大的幂运算,然后求余数。intsuperPow(...
  • 什么是运算

    2019-12-19 11:28:34
    什么是运算
  • 模运算 时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte 总提交:759 测试通过:139 描述 给定整数a,b,n,要求计算(a^b)mod n 输入 多组数据,每组数据一行,为三个用空格隔开的整数a,b,n 1 输出...
  • 模运算总结

    2016-10-26 19:32:51
    模运算在数论和程序设计中都有着广泛的应用,从奇偶数的判别到素数的判别,从模运算到最大公约数的求法,从孙子问题到凯撒密码问题,无不充斥着模运算的身影。  例如11 Mod 2,值为1  上述模运算多用于程序...
  • 基础数学总结 关于模运算 1

    千次阅读 2015-09-18 20:23:27
    1.模运算基本公式 和 几点注意 /* (a + b) mod n = ((a mod n) + (b mod n)) mod n (a - b) mod n = ((a mod n) - (b mod n) + n) mod n (a * b) mod n = ((a mod n) * (b mod n)) mod n 对于除法没有类似公式,...
  • 3二、求,求余百度百科: 取模运算(“Modulo Operation”)和取余运算(“Remainder Operation”)两个概念有重叠的部分但又不完全一致。主要的区别在于对负整数进行除法运算时操作不同。取模主要是用于计算机...
  • 模运算公式整理

    千次阅读 2021-02-09 22:33:39
    整理ACM中常用的模运算公式,包括加减乘除、运算。
  • 牛牛的幂运算 链接:https://ac.nowcoder.com/acm/problem/21578 来源:牛客网 题目描述 牛牛在做一道数学题,他发现自己不怎么会做,请你帮帮他 求有多少a,b,c,d满足ab = cd, 1<=a,b,c,d<=n, 109+7 输入...
  • 快速取模运算精讲

    2016-02-10 22:23:17
    所谓的快速,实际上是快速取模的缩写,简单的说,就是快速的求一个式的(余)。在程序设计过程中,经常要去求一些大数对于某个数的余数,为了得到更快、计算范围更大的算法,产生了快速取模算法。[有读者...
  • 运算,基础常见考题。大家先在草稿本上认真地做一遍,然后再看后面的视频。期待您在评论区留言。欢迎大家,分别添加,同时关注,方老师的这三个微信公众号。(方老师数学课堂矩阵公众号,注重基础常考题,全部...
  • 模运算性质及应用

    千次阅读 2016-01-30 10:15:36
    数学表达式表示模幂运算就是: C=AB%n C=A^B\;\%\;n 无论是乘方还是除法求余数的计算量都非常大,除此之外,乘方计算的中间结果 ABA^B 将是一个非常大的数,大数必须支持非常多的位才能保存这个中间结果。
  • 模运算及其应用

    2010-11-01 12:17:00
    模运算及其应用转自 ...关键词:模运算程序设计应用 模运算在数论和程序设计中都有着广泛的应用,从奇偶数的判别到素数的判别,从模运算到最大公约数的求法,从孙子问题到凯撒密码问题,无
  • 注意一点,最后函数计算的结果要再次取余。因为 0次方取余1这个测试点。 代码: #include<bits/stdc++.h> using namespace std; long long a,b,c;//a的b次方,取余c long long f(long long t) { if(t==0) ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,208
精华内容 5,283
关键字:

幂模运算的数学计算