上一篇咱们聊了聊进制与编码，那么对于如何将数据调度为数字也曾不可问题了，这匡助初入密码学的一又友科罚了心里的第一个槛。于是接下来，咱们就聊一聊这些由数据调度而来的数字上的一些联系学问，没错，数学来了。信赖这可能是好多没罕有理基础的又思在 CTF 里玩密码学的一又友会遭受的第二个槛：嗨嗨嗨，我搞了一堆python 剧本对阿谁叫 RSA 的东西一顿梭梭梭，然而有一天，题策动式子略微变了变，哎，一下给整懵逼了。
但这里咱们先不讲高中数学，也不聊高等数学，这里思给全球先容的，是详尽代数。固然我也只是懂得其中的一些外相，但也但愿能将这些省略的东西共享出来，也算是为后续在一些式子上的推导打个基础吧。
另外知乎上刘巍然一篇科普向的书本《质数了不得》，和 b 站上的一个学习视频《某群清华大佬磨真金不怕火“形象”代数》 中的群论基础部分，推选全球在某个失眠的夜去浅读（看）一下子。
群的界说信赖全球对群是既熟习又生疏吧，可能在好多地点皆有听过它的名号，然而让具体去刻画它是个什么东西，可能又说不出个是以然。在先容群的界说之前，咱们需要先了解一些愈加基础的成见。
招引与元素，全球第一次听到这两个成见应该是不错一直上前记忆的小学的。招引是“慑服的一堆东西”，而招引里的“东西”则称之为元素，况且招引内部的东西不错是轻易的东西。
第一颗🌰：咱们界说一个招引 ，况且其中的元素皆是 10 的倍数，于是这个招引为 ，内部会有无尽多个元素，这么的招引也叫作念无尽招引。
咱们对 中的元素加一个限定，比如还条目完全值小于等于 10，于是咱们就有了一个具有三个元素的有限招引
终末咱们再界说一个招引 ，这个招引会相对详尽些，咱们不雅察如下图形
图片
咱们设定招引 中的元素是概况使得图片（名义上）不发生任何变化的等距变换（旋转、平移），于是这个招引为 其中正号暗示顺时针旋转、标志暗示逆时针旋转。相通的，这亦然一个无尽招引。
运算，这个成见全球交往的就更早了，思必诸君在幼儿园之前就也曾被爸妈培植 一加一等于二 了，这里加，即是一种运算。上头元素不错是轻易的东西，那么这里的运算也不错是轻易的“法规”。例如全球慑服在数学试卷中见到过 “界说一种运算 ' 叭，底下慑服还接着给出了运算 的一些运算国法，然后让你去推导一些东西什么的巴拉巴拉。（是以其实咱们或多或少的早皆交往过群论了）
第二颗🌰：沿用上述三个招引 ，咱们为招引 赋予一个加法运算，组成一个代数结构 ' data-formula-type='inline-equation'>，那么对于其中的轻易两个元素 ，咱们不错进行计算 ，况且不难考据的是， 的运算效力亦然 中的一个元素，于是咱们称这个代数结构中的运算，也即是加法，具有顽固性。
若是咱们对 也赋予一个加法运算，组成代数结构 ' data-formula-type='inline-equation'>，那么咱们很容易发现，这里的加法是不具有顽固性的，因为 ，而 这个元素是不在 中的。
对于招引 ，咱们赋予一个运算叫复合变换 ，组成 ' data-formula-type='inline-equation'>，直不雅上来说该变换在这里即是将两个旋转的角度相加（是以要意会成角度的加法也没联系联），容易考据，这个复合变换亦然具有有顽固性的。
在了解联系”基础体式“之后，咱们运转界说群：
最初咱们需要有一个非空招引 ，和一个具有顽固性的二元运算 ，即无礼 （S 中的元素和 S 中的元素运算后还在 S 中）组成代数结构 < S,★ > 。
若是这个代数结构无礼 结合律，即对于通盘元素 均无礼 ，则称该代数结构为 半群。若是这个半群存在 恒等元 （也称幺元），即对于通盘元素 ，均无礼 ，则称该代数结构为幺半群。若是这个幺半群中通盘的元素皆存在 逆元，即对于通盘元素 ，均存在元素 无礼 ，则称该代数结构为群。若是群中的运算具有交换律，即对于通盘元素 均无礼 ，则称该代数结构为 阿贝尔群。老规定，运转例如。
第三颗🌰：
沿用前边的招引 ，昭彰咱们所熟知的加法运算是具有结合律的（在很厚情况下结合律其实很难讲授，是以这里我挑了一个省略的运算来略过这一步），于是不错称 为半群。然后 中存在恒等元 ，因为对于任何元素 ，皆有 ，于是不错称 为幺半群。对于 中的轻易元素 ，皆有对应的逆元 无礼 ，于是不错称 为群。另外加法运算是无礼交换律的，即对于任何元素 ，皆有 ，于是不错称 为阿贝尔群。另外咱们不错再新界说一个代数结构，其中 是包含通盘 的矩阵的招引，运算为矩阵乘法。回思一下还残存未几的线性代数的常识，咱们知说念矩阵乘法具有结合律；有单元矩阵 ，但惟有行列式不为 0 的矩阵存在逆矩阵。因此该代数结构只是是一个幺半群。若思要让它”升级“为群，则需要给元素加一个行列式不为 0 的畛域。另外咱们知说念矩阵乘法不具有交换律，是以即使通盘元素的行列式皆不为 0 ，该代数结构也不组成阿贝尔群。
是以在咱们了解了群的界说，然后呢？群有什么用呢？具体来说其实莫得什么功能上的作用，不外它概况匡助咱们更好的意会后续的好多更”高档“的成见。接下来即是第一个成见，剩余系。
剩余系又从一个咱们小学就交往过的成见起手（是以这篇实质先容的东西的确很基础）：带余除法。例如 ，一般咱们需要的是这个商 ，但这里咱们温存的是这个尾数 ，甚而咱们还给他一个极度的标志 ，有 。
于是目下咱们又界说一个招引 ，其中的元素是轻易整数除 3 后通盘可能的尾数，于是咱们有 。尾数即是剩余的数，是以除数 3 的通盘可能尾数组成的招引，即是 的剩余系。同理咱们能知说念 2 的剩余系即是 ，这即是二进制中的两个元素；5 的剩余系即是 ; 10 的剩余系即是 。
前边咱们有 ，目下咱们换个标志: ，有 。原本 3 叫作念除数，这里咱们也换个名字，叫作念模数。是以上式就暗示为模 3 下 5 和 2 同余。即在模数为 3 的情况下，5 和 2 具有调换的尾数（5 的尾数是 2，2 的尾数亦然 2）。除了 5 和 2 同余，，5 还和 8 同余；，8 也和 11 同余；不贵重出：2 + 3的轻易整数倍的值皆彼此同余 （注目这个整数倍也不错是负数）。这么的数也不错组成一个招引 ，叫作念模 3 的一个剩余类（因为它们会有一些调换的性质，是以是一类）。
剩余系只是一个招引，跟前边咱们提到的群还差了一个运算，于是这里咱们就赋予一个运算给剩余系：模加。
模加其实即是剩余系中的一个无礼顽固性的粗野加法。为什么不径直用加法呢？以 例如，若是是加法，在计算 1+1 的时分就等于 2，而 2 并不在 中，因此加法在这里不无礼顽固性，就更别说用来组成一个群了。那么模加的运算法规是如何的呢？沿用上头的例子，在 1+1 = 2 行将毒害顽固性的时分，咱们对 2 进行一个模 2 的运算，即 ，是以有 。不错发现， 长得跟等号 很像，其实功能也和等号差未几：一个暗示同余，一个暗示荒谬；模加的时分用同余，加法的时分用荒谬。
第四颗🌰：咱们阐明 ' data-formula-type='inline-equation'> 是一个阿贝尔（交换）群（这里的加法是模加）
最初咱们有非空子集 ，和具有顽固性的二元运算 模加结合律设立：有单元元 ：轻易元素均有逆元：，咱们径直成列：模加具有交换律：既然加法有对应的模加，那么咱们熟习的乘法有对应的模乘么？有的，和粗野乘法运算法规亦然一致，只需要对终末计算的效力，也即是积，取尾数就好。那么 ' data-formula-type='inline-equation'> 组成群么？不组成，固然其无礼结合律，有单元元 1，然而元素 0 莫得逆元，是以其只是算是个幺半群。另外若是是 < S10, · > ，除了 0 之外，元素 2,4,5,6,8 均莫得逆元（不错用 2 乘以 0,1,……9 来考据）。这里径直给出一个论断，当且仅当元素和模数互素时，该元素存在对应的乘法逆元。（互素这个成见应该皆知说念叭，即是两个元素除了 1 莫得其他公因子，至少公因子这个成见是知说念的叭。。。）
第五颗🌰：以 ' data-formula-type='inline-equation'> 为例，其中 1,3,7,9 和模数10互素，它们均有逆元：；因此 1 的逆元是它我方；，因此 3,7 互为逆元；，因此 9 的逆元亦然它我方。而其它元素则找不到逆元。
于是，这些有逆元的元素（也即是和模数互素的元素）也组成了一个系，叫作念简化剩余系。这么，简化剩余系再附加一个模乘运算，就概况组成一个阿贝尔群；一般情况下咱们会以运行为为标签，模乘的叫作念乘法群，模加的叫作念加法群。
然后这里提一下，咱们在密码学中常常会提到有限域（也即是伽罗华域），这个域比较于群即是具有两个运算的代数结构，如加法和乘法，其中条目每个元素皆要有我方的加法逆元和乘法逆元，不外不条目 0 有我方的乘法逆元。是以问全球一个问题，咱们在 RSA 中的计算皆是在模 下的，其中 是两个大素数。那么模 下的剩余系和加法、乘法能组成一个有限域么？
对于乘法群中的破裂对数问题咱们知说念乘法是二元运算，是两个元素之间的运算；然而咱们不错将乘法运算进行重复，这么就不错作念到三个，甚而更多个元素的运算。当咱们将一个元素不停的和我方进行乘法运算时，也就酿成咱们熟知的幂次运算。例如咱们在模 下将 个 相乘获取 , 可记为 。
需要明确的是，幂次运算是乘法运算的重复，是以严格酷爱上它在乘法群中不是一个运算，既莫得结合律，也莫得幺元，更不存在逆元。
当咱们有式子 ，其中仅知说念 ，需要计算出 ，这么一个问题即是解乘法群下的破裂对数问题。之是以破裂，是因为咱们的元素是模 p 剩余系中的整数，这在数轴，亦或是坐标系中，是一系列破裂的点。之是以对数，是因为这是一个已知底数和幂求指数的计算。
破裂对数问题是数学不毛问题之一，尚莫得支吾通盘破裂对数问题的高效算法。后续应该会先容目下已知的解某些特殊情况下破裂对数问题的算法。
椭圆弧线椭圆弧线亦然当代密码学中的常客了，不外对于入门者来说它可能比较生疏，又相对复杂，是以就会让东说念主感到孩怕（事实上也如实挺难的）。但这里暂且不先容椭圆弧线上很复杂的表面，只是思省略先容一下这个代数结构。
咱们常听到椭圆弧线加法群，是以它其实亦然一个由元素和运算结合起来的一个代数结构 ' data-formula-type='inline-equation'>，招引中的元素是一系列无礼同余式 的坐标 ，其中 是素数， 是模 下的整数。为了让这个代数结构组成一个群，还往招引中”硬塞“了一个点 ，也即是背濒临于运算 的单元元。
而这里的运算法规 + 并不是粗野的加法，具体国法为：设相加的两个点为 ：
若是 ，则若是 ，则不然设其中若是 ，则若是 ，则若是 ，则不然设椭圆弧线的加法具有结合律，即
椭圆弧线的单元元是 ，即
椭圆弧线中每个元素皆存在逆元，即 ，一般咱们记 ，设 ，则
椭圆弧线的加法具有交换律，即
是以这亦然一个阿贝尔群。（讲授挺复杂的，感意思意思的一又友不错去翻翻椭圆弧线的联系书本）
椭圆弧线下的破裂对数问题椭圆弧线的加法相通不错重复，例如咱们将 个 相加获取 , 可记为 ，固然这看起来像是数乘，但可没宗旨通过 来计算获取 。是以类比上头乘法群下的破裂对数问题，已知 解出 这么的问题就称为椭圆弧线下的破裂对数问题。是以其实不错把通盘破裂对数问题详尽成一种求运算重复次数的问题。而各个破裂对数问题有难有易，椭圆弧线下的破裂对数问题就比乘法群下的破裂对数问题不毛，但加法群下的破裂对数问题就比较省略。
那么这即是这周基础系列著述的沿途实质了，下周准备以今天的实质为基础，省略先容一下数论四大定理。
本站仅提供存储做事，通盘实质均由用户发布，如发现存害或侵权实质，请点击举报。