博客园  :: 首页  :: 管理

随笔分类 -  [24]数学相关

关于-密码学算法中-类似-编程函数pow(3, 13, 7)的计算-快速幂算法结合模运算（Exponentiation by Squaring with Modular Reduction）

摘要：而 pow(g, a, p) 之所以能“秒算”，是因为它在底层使用了高度优化的快速幂算法结合模运算（Exponentiation by Squaring with Modular Reduction）。 它的精妙之处在于“边算边约减”——在每一次平方或乘法运算后，立刻对中间结果进行取模操作。这样，整 阅读全文

posted @ 2026-06-05 17:00 520_1351 阅读(14) 评论(0) 推荐(0)

关于模运算的乘法性质-大数乘法取模时-可以先分别对乘数取模-相乘后再取模

摘要：模运算的乘法性质：在计算机算法和编程领域，通常直接这样称呼。 它表明在进行大数乘法取模时，可以先分别对乘数取模，相乘后再取模，结果与直接相乘后取模是等价的。 (a×b)≡[(a mod m) × (b mod m)](mod m) 也即 a×b 的结果对m取模， 结果是等于 ，（a对m取模的结果 * 阅读全文

posted @ 2026-06-04 19:17 520_1351 阅读(16) 评论(0) 推荐(0)

模幂运算（Modular Exponentiation）

摘要：模幂运算（Modular Exponentiation，也称模指数运算）是现代密码学、数论和高性能计算中极其核心的基础运算。 它的核心目标是高效地计算形如下： 为什么需要模幂运算？ 核心算法：快速幂（二进制求幂） 尊重别人的劳动成果 转载请务必注明出处：https://chuna2.787528.xyz 阅读全文

posted @ 2026-06-04 18:55 520_1351 阅读(12) 评论(0) 推荐(0)

关于欧拉定理与费尔马定理-费马小定理

摘要：关于欧拉定理：看到很多地方包括百科上都是下面方式定义的 如果a,m都属于正整数，且gcd(a,m)=1 ,则会有a^φ(m)≡1(mod m) 也看到有的数论教材，是设的m是大于1的整数，应下图所示 当然实际上对于这个定理，对于a和m是可以等于1的，甚至都等于1也满足定理 因此只要满足：如果a,m都 阅读全文

posted @ 2023-03-18 12:11 520_1351 阅读(151) 评论(0) 推荐(0)

关于m与n互质-构成的矩阵的特性及证明

摘要：在网上看到很多证明欧拉函数是积性函数的证明，其中一部分就使用到了矩阵的方式加以证明 当然笔者并没有完全理解到整个证明过程，于是只是将其中的部分m与n互质-构成的矩阵的特性说明记录如下 如果m与n互质，那么就可以构成如下的m列与n行的矩阵，这个矩阵里列举了从1到m*n的所有数， 1、先从每一行观察（刚 阅读全文

posted @ 2023-03-18 10:44 520_1351 阅读(345) 评论(0) 推荐(0)

关于欧拉函数φ(n)的积性函数特性说明

摘要：积性函数指对于所有互质的整数a和b有性质f(ab)=f(a)f(b)的数论函数。 积性函数分为两类： 积性函数：对于任意互质的整数a和b有性质f(ab)=f(a)f(b)的数论函数。 完全积性函数：对于任意整数a和b有性质f(ab)=f(a)f(b)的数论函数 刚好最近笔者经常用到的欧拉函数，也是一 阅读全文

posted @ 2023-03-18 10:13 520_1351 阅读(145) 评论(0) 推荐(0)

关于数论中的欧拉函数φ的定义和理解

摘要：在百度百科中，我们可以看到欧拉函数的定义为：在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目 那么根据这个定义，有几个关键的点， 1、欧拉函数是针对于正整数的，那么，我们就不用去考虑0和负数的欧拉函数了 2、计算的也是小于n的正整数中（有的地方写的小于等于，其实一样）与正整数 n 互 阅读全文

posted @ 2023-03-08 20:07 520_1351 阅读(626) 评论(0) 推荐(0)

关于最大公约数-最大公因数-互质-互素的原理与表示方法

摘要：在数学中，有两个名词经常会被听到，最大公因数，最大公约数 刚开始还以为他们有什么区别呢，后来查询了一下，其实都是一个意思，只是叫法不一样 接下来说一下最大公因数的定义 理解一下，即多个数中，他们都会有公同的因数（能整除他们的数），公因数中最大的那一个叫做他们的最大公因数，也有地方称为最大公约数 表示 阅读全文

posted @ 2023-03-04 10:24 520_1351 阅读(633) 评论(0) 推荐(0)

关于同余定理的证明及反向推导

摘要：首页说一下同余定理的概念与定义： 给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m) 对模m同余是整数的一个等价关系。 证明过程：已经的条件是 m|(a-b)，即a-b能被m整除，证明a≡b(mod m) 阅读全文

posted @ 2023-03-03 21:45 520_1351 阅读(553) 评论(0) 推荐(0)

关于素数-质数-无限个数的证明方法

摘要：素数 -（prime number），也叫质数，是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。 根据这样的定义，我们可以知道最小的素数为2，然后依次还有 3，5，7，11，13，17，19，23，29....等等，100以内的素数就共25个 这里我能知道有最小的素数，那么是否有最 阅读全文

posted @ 2022-11-26 16:51 520_1351 阅读(537) 评论(1) 推荐(0)

关于自然数-质数-合数-的概念定义

摘要：素数（prime number），也叫质数，是指在大于1的正整数中，只能被1和它本身整除，不能被其他正整数整除，即除了1和它本身以外不再有其他因数的 与之相对的还有一个概念，即合数，也称复合数，它是指大于1的正整数中，除了能被1和本身整除以外，还能被另外的正整数整除，这样的正整数叫做合数 这里补充一 阅读全文

posted @ 2022-11-26 14:51 520_1351 阅读(888) 评论(0) 推荐(0)

关于初等数论之同余定理及其性质

摘要：数论中的重要概念。给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数， 那么就称整数a与b对模m同余，记作a≡b(mod m)。对模m同余是整数的一个等价关系。如下图 当然反之也成立，也好证明：即a≡b(mod m)时，m|(a-b)也是成立的（因为a与b对模m 阅读全文

posted @ 2022-11-24 22:10 520_1351 阅读(330) 评论(0) 推荐(0)