蒙哥马利算法详解

蒙哥马利乘模，是用来计算x⋅y(modN)x⋅y(modN)

蒙哥马利约减，是用来计算t⋅ρ−1(modN)t⋅ρ−1(modN)

蒙哥马利幂模，是用来计算xy(modN)xy(modN)

其中蒙哥马利幂乘是RSA加密算法的核心部分。

基本概念

梳理几个概念，试想一个集合是整数模N之后得到的

ZN={0,1,2,⋯,N−1}ZN={0,1,2,⋯,N−1}

注：N在base-b进制下有lNlN位。 比如10进制和100进制，都属于base-10进制，因为100=102100=102，所以b=10。在10进制下，667的lN=3lN=3

这样的集合叫做N的剩余类环，任何属于这个集合Z的x满足以下两个条件：

1. 正整数

2. 最大长度是lNlN

这篇文章中讲到的蒙哥马利算法就是用来计算基于ZNZN集合上的运算，简单讲一下原因，因为RSA是基于大数运算的，通常是1024bit或2018bit，而我们的计算机不可能存储完整的大数，因为占空间太大，而且也没必要。因此，这种基于大数运算的加密体系在计算的时候都是基于ZNZN集合的，自然，蒙哥马利算法也是基于ZNZN。

在剩余类环上，有两种重要的运算，一类是简单运算，也就是加法和减法，另一类复杂运算，也就是乘法。我们比较熟悉的是自然数集上的运算，下面看下怎么从自然数集的运算演变成剩余类环上的运算。

对于加法运算，如果计算x±y(modN)x±y(modN) (0⩽x,y

0⩽x+y⩽2⋅(N−1)0⩽x+y⩽2⋅(N−1)

−(N−1)⩽x−y⩽(N−1)−(N−1)⩽x−y⩽(N−1)

我们可以简单的通过加减N来实现从自然数到剩余类集的转换

另外一类是乘法操作，也就是x⋅y(modN)x⋅y(modN)(0⩽x,y

0⩽x⋅y⩽(N−1)20⩽x⋅y⩽(N−1)2

如果在自然数集下，令t=x⋅yt=x⋅y，那么对于modNmodN我们需要计算

t−（N⋅⌊tN⌋）t−（N⋅⌊tN⌋）

解析数论

借助微积分及复分析（即复变函数）来研究关于整数的问题，主要又可以分为乘性数论与加性数论两类。乘性数论藉由研究积性生成函数的性质来探讨素数分布的问题，其中质数定理与狄利克雷定理为这个领域中最著名的古典成果。加性数论则是研究整数的加法分解之可能性与表示的问题，华林问题是该领域最著名的课题。

解析数论的创立当归功于黎曼。他发现了黎曼zeta函数之解析性质与数论中的素数分布问题存在深刻联系。确切的说， 黎曼ζ函数的非平凡零点的分布情况决定了素数的很多性质。黎曼猜测， 那些零点都落在复平面上实部为1/2的直线上。这就是著名的黎曼假设—千禧年大奖难题之一。值得注意的是，欧拉实际上在处理素数无限问题时也用到了解析方法。

解析数论方法除了圆法、筛法等等之外， 也包括和椭圆曲线相关的模形式理论等等。此后又发展到自守形式理论，从而和表示论联系起来。