合成方法论群论的兄弟篇

白新岭

齐头并进，再创辉煌。
合成方法论将彻底打破素数王国的寂寞。

独木星空谁

截止2022年04月30日周六20:34分浏览量6532，回复1144

白新岭

截止2022年04月30日周六20:34分浏览量6532，回复1144
截止2022年05月01日周日21:13分浏览量6559，回复1145

白新岭

数论是纯粹数学的分支之一，主要研究整数的性质。

整数可以是方程式的解(丢番图方程)。有些解析函数(像黎曼ζ函数)中包括了一些整数、质数的性质，透过这些函数也可以了解一些数论的问题。透过数论也可以建立实数和有理数之间的关系，并且用有理数来逼近实数(丢番图逼近)。

按研究方法来看，数论大致可分为初等数论和高等数论。初等数论是用初等方法研究的数论，它的研究方法本质上说，就是利用整数环的整除性质，主要包括整除理论、同余理论、连分数理论。高等数论则包括了更为深刻的数学研究工具。它大致包括代数数论、解析数论、计算数论等等。

独舟星海

一种方法的成熟需要千锤百炼。

独木星空谁

合成方法论可操作性更强，比起解析数论而言。也更容易透明性分析，摸得着，看得见，形象而逼真。

白新岭

计算数论
作者简介
作者英国)颜松远译者:杨思熳刘巍齐璐璐

折叠编辑本段目录
第1章 初等数论

1.1 导言

1.1.1 数论概述

1.1.2 数论的应用

1.1.3 代数初步

1.2 可除性理论

1.2.1 可除性的基本概念及性质

1.2.2 算术基本定理

1.2.3 梅森素数与费马数

1.2.4 欧几里得算法

1.2.5 连分数

1.3 丢番图方程

1.3.1 丢番图方程的基本概念

1.3.2 线性丢番图方程

1.3.3 Pell方程

1.4 算术函数

1.4.1 可积函数

1.4.2 函数r(n)、d(n)和s(n)

1.4.3 完全数、亲和数与多亲数

1.4.4 函数φ(n)、λ(n)和μ(n)

1.5 素数分布

1.5.1 素数分布函数π(x)

1.5.2 用逼近π(x)

1.5.3 用Li(x)逼近π(x)

1.5.4 黎曼函数

1.5.5 第n个素数

1.5.6 孪生素数分布

1.5.7 素数项算术级数

1.6 同余理论

1.6.1 同余的基本概念与性质

1.6.2 模运算

1.6.3 线性同余方程

1.6.4 中国剩余定理

1.6.5 高阶同余方程

1.6.6 勒让德和雅可比符号

1.6.7 阶和原根

1.6.8 指数和k次剩余

1.7 椭圆曲线的算术理论

1.7.1 椭圆曲线的基本概念

1.7.2 椭圆曲线的几何复合定律

1.7.3 椭圆曲线的代数计算定律

1.7.4 椭圆曲线上的群定律

1.7.5 椭圆曲线上点的个数

1.8 小结

第2章 计算数论/算法数论

2.1 简介

2.1.1 计算/算法数论概述

2.1.2 计算可行性

2.1.3 计算复杂性

2.1.4 数论算法的复杂性

2.1.5 快速模指数算法

2.1.6 椭圆曲线上的快速群运算

2.2 素性检测算法

2.2.1 确定性的严格素性检测

2.2.2 费马的拟素性检测

2.2.3 强拟素性检测

2.2.4 卢卡斯拟素性检测

2.2.5 椭圆曲线检测

2.2.6 关于素性检测历史的小结

2.3 整数因子分解算法-._

2.3.1 整数因子分解的复杂性理论

2.3.2 试除法和费马方法

2.3.3 勒让德同余

2.3.4 连分数法

2.3.5 二次筛法和数域筛法

2.3.6 Pollard的"rho"方法和"p-1"方法

2.3.7 Lenstra的椭圆曲线方法

2.4 离散对数问题的算法

2.4.1 Shanks的小步一大步算法

2.4.2 Silver-Pohlig-Hellman算法

2.4.3 离散对数的指数演算法

2.4.4 椭圆曲线离散对数问题的算法

2.4.5 求根问题的算法

2.5 量子数论算法

2.5.1 量子信息和计算

2.5.2 量子可计算性和复杂性

2.5.3 整数因子分解的量子算法

2.5.4 离散对数的量子算法

2.6 数论中的各式算法

2.6.1 计算π(x)的算法

2.6.2 生成亲和数的算法

2.6.3 验证哥德巴赫猜想的算法

2.6.4 寻找奇完全数的算法

2.7 小结

第3章 计算/码学中的应用数论

3.1 研究应用数论的意义

3.2 计算机系统设计

3.2.1 剩余系中数的表示

3.2.2 剩余数系中的快速计算

3.2.3 剩余计算机

3.2.4 余运算

3.2.5 哈希函数

3.2.6 检错和纠错方法

3.2.7 随机数的生成

3.3 密码学和信息安全

3.3.1 介绍

3.3.2 私钥密码学

3.3.3 数据/高级加密标准

3.3.4 公钥密码学

3.3.5 基于离散对数的密码体制

3.3.6 公钥密码体制

3.3.7 二次剩余密码体制

3.3.8 椭圆曲线公钥密码体制

3.3.9 数字签名

3.3.10 数字签名标准

3.3.11 数据库安全

3.3.12 秘密共享

3.3.13 因特网/环球网安全和电子商务

3.3.14 隐写术

3.3.15 量子密码学

3.4 小结

白新岭

众里寻他千百度。蓦然回首，那人却在，灯火阑珊处
矩阵乘法
矩阵乘法是一种高效的算法可以把一些一维递推优化到log( n )，还可以求路径方案等，所以更是一种应用性极强的算法。矩阵，是线性代数中的基本概念之一。一个m×n的矩阵就是m×n个数排成m行n列的一个数阵。由于它把许多数据紧凑的集中到了一起，所以有时候可以简便地表示一些复杂的模型。矩阵乘法看起来很奇怪，但实际上非常有用，应用也十分广泛。
适用范围
只有当矩阵A的列数与矩阵B的行数相等时A×B才有意义。一个m×n的矩阵a(m,n)左乘一个n×p的矩阵b(n,p)，会得到一个m×p的矩阵c(m,p)。左乘:又称前乘，就是乘在左边(即乘号前)，比如说,A左乘E即AE。

矩阵乘法满足结合律，但不满足交换律和约去律

一般的矩乘要结合快速幂才有效果。(基本上所有矩阵乘法都要用到快速幂的)

在计算机中，一个矩阵实际上就是一个二维数组。一个m行n列的矩阵与一个n行p列的矩阵可以相乘，得到的结果是一个m行p列的矩阵，其中的第i行第j列位置上的数为第一个矩阵第i行上的n个数与第二个矩阵第j列上的n个数对应相乘后所得的n个乘积之和。比如，下面的算式表示一个2行2列的矩阵乘以2行3列的矩阵，其结果是一个2行3列的矩阵。其中，结果矩阵的那个4(结果矩阵中第二(i)行第二(j)列)=

2(第一个矩阵第二(i)行第一列)*2(第二个矩阵中第一行第二(j)列)

+

0(第一个矩阵第二(i)行第二列)*1(第二个矩阵中第二行第二(j)列):

程序运行结果示例:
一般矩乘的代码:function mul( a , b : Tmatrix ) : Tmatrix;

var

i,j,k : longint;

c : Tmatrix;

begin

fillchar( c , sizeof( c ) , 0 );

for k:=0 to n do

for i:=0 to m do

for j:=0 to p do

begin

inc( c[ i , j ] , a[ i , k ]*b[ k , j ] );

if c[ i , j ] > ra then c[ i , j ]:=c[ i , j ] mod ra;

end;

mul:=c;

end;

白新岭

这里我们不介绍其它有关矩阵的知识，只介绍矩阵乘法和相关性质。

不要以为数学中的矩阵也是黑色屏幕上不断变化的绿色字符。在数学中，一个矩阵说穿了就是一个二维数组。一个n行m列的矩阵可以乘以一个m行p列的矩阵，得到的结果是一个n行p列的矩阵，其中的第i行第j列位置上的数等于前一个矩阵第i行上的m个数与后一个矩阵第j列上的m个数对应相乘后所有m个乘积的和。比如一下的例子中，算式所表示的是一个2行2列的矩阵与一个2行3列的矩阵相乘，所得的结果是一个2行3列的矩阵。所得矩阵中第2行第2列的"4"是2*2+0*1的和:右面的算式则是一个1 x 3的矩阵乘以3 x 2的矩阵，得到一个1 x 2的矩阵:

矩阵乘法的两个重要性质: 一，矩阵乘法不满足交换律;二，矩阵乘法满足结合律。为什么矩阵乘法不满足交换律呢?这是由矩阵乘法定义决定的。因为矩阵AB=C，C的结果是由A的行与B的列相乘和的结果;而BA=D，D的结果是由B的行与A的列相乘和的结果。显然，得到的结果C和D不一定相等。同时，交换后两个矩阵有可能不能相乘。为什么它又满足结合律呢?假设你有三个矩阵A、B、C，那么(AB)C和A(BC)的结果的第i行第j列上的数都等于所有A(ik)*B(kl)*C(lj)的和(枚举所有的k和l)。

白新岭

相关符号
相关符号 以下是一个 4 × 3 矩阵:

某矩阵 A 的第 i 行第 j 列，或 i,j位，通常记为 A[i,j] 或 Ai,j。在上述例子中 A[2,3]=7。

在C语言中，亦以 A[j] 表达。(值得注意的是，与一般矩阵的算法不同，在C中，"行"和"列"都是从0开始算起的)

此外 A = (aij)，意为 A[i,j] = aij 对于所有 i 及 j，常见于数学著作中。

一般环上构作的矩阵

给出一环 R，M(m,n, R) 是所有由 R 中元素排成的 m× n 矩阵的集合。若 m=n，则通常记以 M(n,R)。这些矩阵可加可乘 (请看下面)，故 M(n,R) 本身是一个环，而此环与左 R 模Rn 的自同态环同构。

若 R 可置换， 则 M(n, R) 为一带单位元的 R-代数。其上可以莱布尼茨公式定义 行列式:一个矩阵可逆当且仅当其行列式在 R 内可逆。

除特别指出，一个矩阵多是实数矩阵或虚数矩阵。

分块矩阵:

分块矩阵 是指一个大矩阵分割成"矩阵的矩阵"。举例，以下的矩阵

可分割成 4 个 2×2 的矩阵，矩阵将多种信号自由控制，将BSV液晶拼接跨屏显示。

此法可用于简化运算，简化数学证明，以及一些电脑应用如VLSI芯片设计等。

折叠编辑本段基本性质