费马小定理讲解(费马小定理的公式)

在生活中，很多人可能想了解和弄清楚费马小定理之阶和原根的相关问题？那么关于费马小定理讲解的答案我来给大家详细解答下。

先复习一下费马小定理。

那么显然有以下推论：

理解很容易，h最大为p−1，或许有更小的h。

因为

所以，h一定是p−1的某一个因子，但不知道是哪一个。我们可以通过试的办法求出h。

接下来我们就用一些小小的数来仔细分析模7

我们发现，有两个整数3和5，它们模7的阶为6

显然原根不一定只有一个，最小的原根称为最小原根。

7的原根有两个3和5，其中3是最小原根。

原根的意义在于：在模p下，

求最小原根的方法，几乎是架构在穷举法之上的，高斯做了一个优化，我再简化一下。

（高斯的算法此处有若干运算，可以更快确定原根，但不是最小原根）

例：求模73的最小原根

之前我们已经发现，a模p的阶h必然整除p-1，所以，只要在p-1的因子中尝试就可以了。

因为72=2 ×3 ，72的因子有：1,2,3,4,6,8,9,12,18,24,36,72

所以，我们可以简化上述的尝试过程。

简化解法：

我们看到，这样的计算量已经非常非常小，一般的电脑都能够吃得消，哪怕手算也能勉强应付。

嗯，怎么这篇蚊子不像数学，倒像是程序设计课程了。（暗笑）

原根在密码学中有非常非常重要的作用，如果有机会，我们来仔细研究非对称密码系统，这个系统之所以非常牛逼，原因是数学对自然数的知识极度贫乏，如果有一天哪个数学家能找到很简单计算素数的方法。现行的密码系统全部崩盘！可怕不可怕？

别担心，在我有生之年，恐怕都不会有这么一天。

温馨提示：通过以上关于费马小定理之阶和原根内容介绍后，相信大家有新的了解，更希望可以对你有所帮助。