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

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

    蒙哥马利幂模运算

    简介

    蒙哥马利(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
    展开全文
  • 点击上方蓝字设为星标东哥带你搞定算法~今天来聊一道与数学运算有关算法题目,LeetCode 372 题 Super Pow,让你进行巨大的幂运算,然后求余数。intsuperPow(inta,vector<int>&b);要求你算法返回幂运算...

    点击上方蓝字设为星标8c16eb24daffc71150db7dffdea27ce4.png

    东哥带你搞定算法~

    bf17deefefee62acc179079869450543.png

    今天来聊一道与数学运算有关的算法题目,LeetCode 372 题 Super Pow,让你进行巨大的幂运算,然后求余数。

    int superPow(int a, vector<int>& b);

    要求你的算法返回幂运算a^b的计算结果与 1337 取模(mod,也就是余数)后的结果。就是你先得计算幂a^b,但是这个b会非常大,所以b是用数组的形式表示的。

    这个算法其实就是广泛应用于离散数学的模幂算法,至于为什么要对 1337 求模我们不管,单就这道题可以有三个难点:

    一是如何处理用数组表示的指数,现在b是一个数组,也就是说b可以非常大,没办法直接转成整型,否则可能溢出。你怎么把这个数组作为指数,进行运算呢?

    二是如何得到求模之后的结果?按道理,起码应该先把幂运算结果算出来,然后做% 1337这个运算。但问题是,指数运算你懂得,真实结果肯定会大得吓人,也就是说,算出来真实结果也没办法表示,早都溢出报错了。

    三是如何高效进行幂运算,进行幂运算也是有算法技巧的,如果你不了解这个算法,后文会讲解。

    那么对于这几个问题,我们分开思考,逐个击破。

    如何处理数组指数

    首先明确问题:现在b是一个数组,不能表示成整型,而且数组的特点是随机访问,删除最后一个元素比较高效。

    不考虑求模的要求,以b = [1,5,6,4]来举例,结合指数运算的法则,我们可以发现这样的一个规律:

    981d8e7cf9451f673d382ed78207fb60.png

    看到这,我们的老读者肯定已经敏感地意识到了,这就是递归的标志呀!因为问题的规模缩小了:

        superPow(a, [1,5,6,4])
    =>  superPow(a, [1,5,6])

    那么,发现了这个规律,我们可以先简单翻译出代码框架:

    // 计算 a 的 k 次方的结果
    // 后文我们会手动实现
    int mypow(int a, int k);

    int superPow(int a, vector<int>& b) {
        // 递归的 base case
        if (b.empty()) return 1;
        // 取出最后一个数
        int last = b.back();
        b.pop_back();
        // 将原问题化简,缩小规模递归求解
        int part1 = mypow(a, last);
        int part2 = mypow(superPow(a, b), 10);
        // 合并出结果
        return part1 * part2;
    }

    到这里,应该都不难理解吧!我们已经解决了b是一个数组的问题,现在来看看如何处理 mod,避免结果太大而导致的整型溢出。

    如何处理 mod 运算

    首先明确问题:由于计算机的编码方式,形如(a * b) % base这样的运算,乘法的结果可能导致溢出,我们希望找到一种技巧,能够化简这种表达式,避免溢出同时得到结果。

    比如在二分查找中,我们求中点索引时用(l+r)/2转化成l+(r-l)/2,避免溢出的同时得到正确的结果。

    那么,说一个关于模运算的技巧吧,毕竟模运算在算法中比较常见:

    (a*b)%k = (a%k)(b%k)%k

    证明很简单,假设:

    a=Ak+B;b=Ck+D

    其中 A,B,C,D 是任意常数,那么:

    ab = ACk^2+ADk+BCk+BD

    ab%k = BD%k

    又因为:

    a%k = B;b%k = D

    所以:

    (a%k)(b%k)%k = BD%k

    综上,就可以得到我们化简求模的等式了。

    换句话说,对乘法的结果求模,等价于先对每个因子都求模,然后对因子相乘的结果再求模

    那么扩展到这道题,求一个数的幂不就是对这个数连乘么?所以说只要简单扩展刚才的思路,即可给幂运算求模:

    int base = 1337;
    // 计算 a 的 k 次方然后与 base 求模的结果
    int mypow(int a, int k) {
        // 对因子求模
        a %= base;
        int res = 1;
        for (int _ = 0; _         // 这里有乘法,是潜在的溢出点
            res *= a;
            // 对乘法结果求模
            res %= base;
        }
        return res;
    }

    int superPow(int a, vector<int>& b) {
        if (b.empty()) return 1;
        int last = b.back();
        b.pop_back();

        int part1 = mypow(a, last);
        int part2 = mypow(superPow(a, b), 10);
        // 每次乘法都要求模
        return (part1 * part2) % base;
    }

    你看,先对因子a求模,然后每次都对乘法结果res求模,这样可以保证res *= a这句代码执行时两个因子都是小于base的,也就一定不会造成溢出,同时结果也是正确的。

    至此,这个问题就已经完全解决了,已经可以通过 LeetCode 的判题系统了。

    但是有的读者可能会问,这个求幂的算法就这么简单吗,直接一个 for 循环累乘就行了?复杂度会不会比较高,有没有更高效的算法呢?

    有更高效的算法的,但是单就这道题来说,已经足够了。

    因为你想想,调用mypow函数传入的k最多有多大?k不过是b数组中的一个数,也就是在 0 到 9 之间,所以可以说这里每次调用mypow的时间复杂度就是 O(1)。整个算法的时间复杂度是 O(N),N 为b的长度。

    但是既然说到幂运算了,不妨顺带说一下如何高效计算幂运算吧。

    如何高效求幂

    快速求幂的算法不止一个,就说一个我们应该掌握的基本思路吧。利用幂运算的性质,我们可以写出这样一个递归式:

    0751ba0ef80ea91bd3966fe4e42d5667.png

    这个思想肯定比直接用 for 循环求幂要高效,因为有机会直接把问题规模(b的大小)直接减小一半,该算法的复杂度肯定是 log 级了。

    那么就可以修改之前的mypow函数,翻译这个递归公式,再加上求模的运算:

    int base = 1337;

    int mypow(int a, int k) {
        if (k == 0return 1;
        a %= base;

        if (k % 2 == 1) {
            // k 是奇数
            return (a * mypow(a, k - 1)) % base;
        } else {
            // k 是偶数
            int sub = mypow(a, k / 2);
            return (sub * sub) % base;
        }
    }

    这个递归解法很好理解对吧,如果改写成迭代写法,那就是大名鼎鼎的快速幂算法。至于如何改成迭代,很巧妙,这里推荐一位大佬的文章 让技术一瓜共食:快速幂算法。

    虽然对于题目,这个优化没有啥特别明显的效率提升,但是这个求幂算法已经升级了,以后如果别人让你写幂算法,起码要写出这个算法。

    至此,Super Pow 就算完全解决了,包括了递归思想以及处理模运算、幂运算的技巧,可以说这个题目还是挺有意思的,你有什么有趣的题目,可以留言分享一下。

    历史文章:

    回溯算法团灭排列/组合/子集问题

    加密算法的前世今生

    这个问题不简单:寻找缺失元素

    db76d0640ef46dafc95f2f506e879d29.png

    展开全文
  • 取模运算(“Modulus Operation”)它和取余...模运算在数论和程序设计中都有着广泛的应用,奇偶数的判别到素数的判别,从模运算到最大公约数的求法,从孙子问题到凯撒密码问题,无不充斥着模运算的身影。虽然很多数...

    取模运算(“Modulus Operation”)

    它和取余运算(“Remainder Operation ”)两个概念有重叠的部分但又不完全一致。主要的区别在于对负整数进行除法运算时操作不同。取模主要是用于计算机术语中。取余则更多是数学概念。

    模运算在数论和程序设计中都有着广泛的应用,奇偶数的判别到素数的判别,从模幂运算到最大公约数的求法,从孙子问题到凯撒密码问题,无不充斥着模运算的身影。虽然很多数论教材上对模运算都有一定的介绍,但多数都是以纯理论为主,对于模运算在程序设计中的应用涉及不多。

    “模”是指一个计量系统的计数范围;如时钟,12个整点为计算范围,则模为12;计算机也是一个计量机器,模为32位或者64位;

    32位计算机正常理解 在模 范围内能表达的 有 [0, 2³²-1];那么负数该怎么表达呢,所以出现了补码;也就是 正数 + 负数 正好达到模的溢出阀值2³²;所以在计算机中负数是用补码方式表达的原因;

    关于补码的例子:在12模的时钟中;假设当前时针指向10点,而准确时间是6点,调整时间可有以下两种拨法

    倒拨4小时,即:10-4=6 (10-4) mod 12 = 6

    顺拨8小时:10+8=12+6=6 (10+8)mod 12 = 6

    在以12模的系统中,加8和减4效果是一样的;因此凡是减4运算,都可以用加8来代替。对“模”而言,8和4互为补数。实际上以12模的系统中11和1、10和2、9和3、7和5、6和6都有这个特性;共同的特点是两者相加等于模

    “取模”实质上是计量器产生“溢出”的量,它的值在计量器上表示不出来,计量器上只能表示出模的余数(取模);任何有模的计量器,均可化为加减法运算

    5 mod 3 = 2 例子中;模 为 3;2 为取模的值

    取模和取余的区别

    1.相同

    假设有整数a和b,那么取模/取余运算可以分为两步运算:

    求整数商:c = a/b;

    计算模/余数:2.计算模或者余数: r = a - c*b.

    2.不同

    取余运算 在计算商值时 商值向0方向舍入;靠近0原则

    取模运算 在计算商值时 商值向负无穷方向舍入;尽可能让商值小的原则(不超多商值的最大值)

    求模运算和求余运算在第一步不同: 取余运算在取c的值时,向0 方向舍入(fix()函数);而取模运算在计算c的值时,向负无穷方向舍入(floor()函数)。

    例子

    取模

    简述

    商值

    取模值

    5 mod 3 = 2

    5/3 = 1.66商取小原则 商=1

    5 - 3 * 1 = 2

    2

    -5 mod 3 = 1

    -5/3 = -1.66 商取小原则 商=-2

    -5 - (3 * -2) = 1

    1

    5 mod -3 = -1

    5/-3 = -1.66 商取小原则 商=-2

    5 - (-3 * -2) = -1

    -1

    -5 mod -3 = -2

    -5/-3 = 1.66 商取小原则 商=1

    -5 - (-3 * 1) = 2

    -2

    取余

    简述

    商值

    取余值

    5 rem 3 = 2

    5/3 = 1.66

    商靠0原则 商=1

    5 - 3 * 1 = 2  2

    -5 rem 3 = -2

    -5/3 = -1.66 商靠0原则 商=-1

    -5 - (3 * -1) = - 2

    -2

    5 rem -3 = 2

    5/-3 = -1.66 商靠0原则 商=-1

    5 - (-3 * -1) = 2

    2

    -5 rem -3 = -2 -

    5/-3 = 1.66 商靠0原则 商=1

    -5 - (-3 * 1) = - 2

    -2

    java 中 % 是取余运算;Python中 % 是取模运算

    Python代码

    # 取模,Python中可直接用%,计算模,r = a % b

    def mod(a, b):

    c = a // b

    r = a - c * b

    return r

    # 取余

    def rem(a, b):

    c = int(a / b)

    r = a - c * b

    return r

    x=mod(-5,3)

    y=rem(-5,3)

    print(x,y)

    输出结果

    1 -2

    展开全文
  • 3二、求,求余百度百科: 取模运算(“Modulo Operation”)和取余运算(“Remainder Operation”)两个概念有重叠部分但又不完全一致。主要区别在于对负整数进行除法运算时操作不同。取模主要是用于计算机...

    javascript

    一、 求平方根

    2*2=4
    3*3=9
    
    Math.sqrt(4)
    2
    Math.sqrt(16)
    4
    Math.sqrt(9)
    3

    二、求模,求余

    百度百科: 取模运算(“Modulo Operation”)和取余运算(“Remainder Operation”)两个概念有重叠的部分但又不完全一致。主要的区别在于对负整数进行除法运算时操作不同。取模主要是用于计算机术语中。取余则更多是数学概念。
    
    24对5取模为4  数学上就是25除以5余4
    24 % 5 = 4

    三、向上取整 向下取整

    向下取整数
    Math.floor(1.4) 
    1
    向上取整数
    Math.ceil(1.4)
    2

    四、求幂

    23次方 2*2*2=8
    Math.pow(2, 3)
    也可以写成
    2 ** 3

    五、求对数

    在js中
    指定底数求对数
    
    2 * 2 * 2 = 8
    Math.log(8) / Math.log(2)
    展开全文
  • 注意一点,最后函数计算的结果要再次取余。因为 0次方取余1这个测试点。 代码: #include<bits/stdc++.h> using namespace std; long long a,b,c;//ab次方,取余c long long f(long long t) { if(t==0) ...
  • 模运算性质及应用

    千次阅读 2016-01-30 10:15:36
    RSA 算法核心是大整数的模幂运算(Modular Power),模幂运算又称为乘方运算。用数学表达式表示模幂运算就是: C=AB%n C=A^B\;\%\;n 无论是乘方还是除法求余数的计算量都非常大,除此之外,乘方计算的中间结果 ...
  • 这个算法思想我是从一本书上看到,对合法输入能很快的计算出结果来,其思想是利用 数学公式: (a * b ) mod c = (( a mod c) * b) mod c; 首先把 b 转化成二进制如: b0 b1 b2 b3..... b31 即 b = b0...
  • R语言中的数学运算-最全总结+解惑

    万次阅读 多人点赞 2018-07-23 19:27:26
    A%%B 取余,模运算 A%/%B 整数除法 == 严格等于,判断是否相等 !x 不等于x x|y 或,&amp;或|比较两个向量所有元素 x&amp;y 与 sign() 判断正负 &amp;&amp;或|| 逻辑计算操作,只比较两个向量第一个...
  • 取模运算

    千次阅读 多人点赞 2018-08-07 20:55:09
    取模运算(“Modulo Operation”)和取余...模运算在数论和程序设计中都有着广泛应用,比如: 从奇偶数判别 素数判别 模运算 最大公约数求法 孙子问题 凯撒密码问题 虽然很多数论教材上对模运算...
  • 求一个大数较高次幂模运算,可以将其指数分解成二进制形式进行分解。 举一个简单例子: 我们要求501^13(mod 667),这时13可以分解成2进制形式,13= 2^3 + 2^2 + 2^0。 (此图是陈恭亮《信息安全数学...
  • 本软件不仅是一个强大的数学学习工具,包括了从初中到大学几乎所有的数学函数、平面解析几何、重要公式等以及他们的相关图像,而且也是工程测量数理统计等部门的最佳辅助运算工具,十几种统计分析预测模型及他们的...
  • 筛选法+求一个整数分解+快速模幂运算+递归求计算1+p+p^2+````+p^nPOJ 1845 Sumdiv求A^B所有约数之和%9901 */#include<stdio.h>#include<math.h>#include<iostream>#include<algorithm>...
  • 掌握密码学相关的数学基础知识,理解模幂、求逆等运算的过程,编程实现相关算法 二、实验原理 考虑指数,即计算形如 x^c mod n 的函数,在RSA密码体制中,加密和解密运算都是指数运算。计算 x^c mod n 可以通过c...
  • 数学概念与方法

    2018-10-26 16:20:43
    熟练掌握模运算规则,快速取模算法和模线性方程解法 熟悉杨辉三角、二项式定理和组合数基本性质 学会推导约数个数公式和欧拉函数公式 熟练掌握可重集全排列编码和解码算法 理解样本空间、事件和概率,...
  • 这篇博客将复习欧拉函数的定义及性质,然后给出三个关于欧拉函数的重要定理,最后介绍一种加速平方运算的方法(重复平方计算法) 一.欧拉函数的性质 定理:设m1,m2是互素的两个正整数,如果k1,k2分别遍历m1和...
  • 关于%取余一些知识

    千次阅读 2016-03-31 14:31:34
    模运算在数论和程序设计中都有着广泛的应用,从奇偶数的判别到素数的判别,从模运算到最大公约数的求法,从孙子问题到凯撒密码问题,无不充斥着模运算的身影。 3;方法 1.求 整数商: c = a/b; 2.计算模或者余数...
  • 2·1 复数的四则运算的图示 2·2 复数的性质 2·3 映射 2·4 二直线的夹角 2·5 在图形上的应用 3.棣莫佛定理 3·1 棣莫佛定理 3·2 棣莫佛定理和倍角公式 3·3 二项方程 4.向量 4·1 向量 4·2 向量的相等、和、差...
  • 2·1 复数的四则运算的图示 2·2 复数的性质 2·3 映射 2·4 二直线的夹角 2·5 在图形上的应用 3.棣莫佛定理 3·1 棣莫佛定理 3·2 棣莫佛定理和倍角公式 3·3 二项方程 4.向量 4·1 向量 4·2 向量的相等、和、差...
  • 数据结构与算法分析(Java语言描述)学习--第二天第2章 算法分析数学基础模型要分析问题运行时间计算折半查找欧几里德算法幂运算 第2章 算法分析 数学基础 模型 要分析问题 运行时间计算 折半查找 欧几里德算法 ...
  • 今天来聊一道与数学运算有关题目,LeetCode 372 题 Super Pow,让...这个算法其实就是广泛应用于离散数学的模幂算法,至于为什么要对 1337 求我们不管,单就这道题可以有三个难点: 一是如何处理用数组表示指数,
  • 算术运算符 a = 20 b = 10 运算符 说明 示例 - 负号,取原数的相反数 a = 10 print(-a) #-10 ...加减乘除,同数学上一样 ...对运算符进行指数(计算 ...模运算的符号取决于第二个操作数(右操
  • 递归算法学习

    2007-05-28 11:34:00
    数学家们则将递归用于组合数学领域,其处理对象是大量的计算和可能性问题.递归都是算法研究.运算研究模型/博弈论和图论重要课题.递归概念: 大多数人不会自然地想到递归.例如,如果要求定义函数XN字方,其中X为...
  • 第7 章符号数学计算 7.1 MATLAB 符号计算概述 7.2 符号对象和符号表达式 7.2.1 符号对象创建命令 7.2.2 符号对象创建示例 7.2.3 符号计算中运算符和函数 7.2.4 符号对象类别识别函数 7.2.5 符号...
  • 第6~8 章为数学应用部分,讲解数据分析、符号数学计算和概率统计等;第9~15 章为工程应用部分,讲解偏微分方程、优化、图像处理、信号处理、小波分析等工具箱,Simulink 仿真基础及应用等;第16~20 章为知识拓展...
  • 清明 DAY 1

    2019-04-08 21:22:00
    意义下的运算 mod 对一个数取模,其实就是取余数 注意: • 无除法运算 • 满足基本交换律、分配率、结合律 • 对中间结果取模不影响最终答案 Part 3. 快速 ...
  • 算法艺术和数学的智慧在本书中得到了完美体现,书中总结了大量高效、优雅和奇妙算法,并从数学角度剖析了其背后原理。 第1章 概述 1 1.1 记法 1 1.2 指令集与执行时间模型 5 1.3 习题 10 第2章 基础知识 ...
  • 当前面向矩阵运算的数学工具软件另外还有:Maple、Mathematica、Scilab、MatCom、MATFOR等。众所周知,MATLAB拥有强大的矩阵运算能力,灵活多变的外部应用程序编程接口,作为矩阵数值运算的首选工具具有无可比拟的...

空空如也

空空如也

1 2 3
收藏数 50
精华内容 20
关键字:

幂模运算的数学计算