整数模n乘法群

同余理论中,模 n互质同余类组成一个乘法,称为整数模 n 乘法群,也称为模 n 既约剩余类。在环理论中,一个抽象代数的分支,也称这个群为整数模 n 的环的单位群(单位是指乘法可逆元)。

这个群是数论的基石,在密码学整数分解均有运用。例如,关于这个群的阶(即群的“大小”),我们可以确定如果 n质数当且仅当阶数为 n-1。

群公理

容易验证模 n 互质同余类在乘法运算下满足阿贝尔群的公理。

互质同余类的乘法是良好定义:an 互质,当且仅当 gcd(a, n) = 1. 同余类中的整数ab (mod n) 满足gcd(a, n) = gcd(b, n), 因此一个整数与 n 互质当且仅当另一个整数也与 n 互质.
恒同: 1 是恒同; 1所在的同余类是唯一的乘法恒同类
闭:如果 ab 都与 n 互质,那么 ab 也是;因为gcd(a, n) = 1gcd(b, n) = 1 意味着 gcd(ab, n) = 1, 与 n 互质的同余类在乘法下是封闭的。
逆:找 x 满足 ax ≡ 1 (mod n) 等价于解 ax + ny = 1,可用欧几里得算法求出x,并且x在模n的同余类里。当 an 互质, 由于 gcd(a, n) = 1 ,根据 裴蜀定理 存在整数 xy 满足 ax + ny = 1. 注意到由等式 ax + ny = 1 可推出 xn 互质, 所以乘法逆元属于群.
结合性和交换性:由整数的相应事实以及模 n 运算是一个环同态推出。由于同余类aa' bb' (mod n) 的整数乘法意味着 aba'b' (mod n). 这可推出乘法满足结合律、交换律。

记法

整数模 n 环记作 (即整数环模去理想 nZ = (n) ,由 n 的倍数组成)或 因作者所喜,它的单位群可能记为 或类似的记号,本文采用

结构

2 的幂次

模 2 只有一个互质同余类 1,所以 平凡。

模 4 有两个互质同余类,1 和 3,所以 两元循环群。

模 8 有四个互质同余类,1, 3, 5 和 7,每个平方都是 1,所以 Klein 四元群

模 16 有八个互质同余类,1, 3, 5, 7, 9, 11, 13 和 15。 为 2-扭子群(即每个元素的平方为 1),所以 不是循环群。3的幂次: 是一个 4 阶子群,5 的幂次也是,。所以

以上 8 和 16 的讨论对高阶幂次 2k, k > 2[1] 也成立: 是 2-扭子群(所以 不是循环)而 3 的幂次是一个2k- 2 子群,所以

奇质数的幂

对奇质数的幂 pk,此群是循环群:[2]

一般合数

中国剩余定理[3] 说明如果 那么环 每个质数幂因子相应的环的直积

类似地, 的单位群是每个质数幂因子相应群的直积:

阶数

群的阶数由欧拉函数给出: OEIS數列A000010 这是直积中各循环阶数的乘积。

指数

指数为卡邁克爾函數OEIS數列A002322,即这些循环群的阶数的最小公倍数。这意味着如果 an 互质,

生成元

循环群当且仅当 这在 n 为奇质数的幂次、奇质数幂次 2 倍、2 和 4 成立,此时也称一个生成元为模 n 的原根

因为所有 n = 1, 2, ..., 7 是循环群,上述结论的另一种说法是:如果 n < 8 那么 有原根;如果 n ≥ 8,且不能被 4 或者两个不同的奇质数整除, 有原根。(OEISA033948 = 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, 22, 23, 25, 26, 27, 29, 31, 34, 37, 38, 41, 43, 46, 47, 49, 50, ... )

一般情形每个直积因子循环有一个生成元。

列表

这个表列出了较小 n 的结构和生成元。生成元不是惟一(mod n)的,比如 (mod 16) 时 {–1, 3} 和{–1, 5} 都可以。生成元以和直积因子相同的顺序列出。

n=20 为例。 意味着 的阶数是 8(即有 8 个小于 20 的正整数与其互质); 说明任何和20互质的数的 4 次幂≡ 1(mod 20);至于生成元,19 的指数为2,3 的指数为 4,而任何 中元素都是 19a × 3b 的形式,这里 a 为 0 或 1,b 为 0, 1, 2, 或 3。

19 的幂是 {±1},3 的幂为 {3, 9, 7, 1}。后者和他们的负数 (mod 20),{17, 11, 13, 19} 是所有小于 20 且与其互质的数。19 的指数为 2 而 3 的指数为 4 意味着任何 中数的 4 次幂 ≡ 1 (mod 20)。

(Z/nZ)× 的群结构
生成元   生成元   生成元
1 C1110 32 C2×C816831, 3 63 C6×C63662, 5
2 C1111 33 C2×C10201010, 2 64 C2×C1632163, 63
3 C2222 34 C1616163 65 C4×C1248122, 12
4 C2223 35 C2×C1224126, 2 66 C2×C1020105, 7
5 C4442 36 C2×C612619, 5 67 C6666662
6 C2225 37 C3636362 68 C2×C1632163, 67
7 C6663 38 C1818183 69 C2×C2244222, 68
8 C2×C2427, 3 39 C2×C12241238, 2 70 C2×C1224123, 11
9 C6662 40 C2×C2×C416439, 11, 3 71 C7070707
10 C4443 41 C4040406 72 C2×C2×C624125, 7, 11
11 C1010102 42 C2×C612613, 5 73 C7272725
12 C2×C2425, 7 43 C4242423 74 C3636365
13 C1212122 44 C2×C10201043, 3 75 C2×C2040202, 74
14 C6663 45 C2×C12241244, 2 76 C2×C1836183, 75
15 C2×C48414, 2 46 C2222225 77 C2×C3060302, 76
16 C2×C48415, 3 47 C4646465 78 C2×C1224125, 7
17 C1616163 48 C2×C2×C416447, 7, 5 79 C7878783
18 C6665 49 C4242423 80 C2×C4×C43243, 7, 11
19 C1818182 50 C2020203 81 C5454542
20 C2×C48419, 3 51 C2×C16321650, 5 82 C4040407
21 C2×C612620, 2 52 C2×C12241251, 7 83 C8282822
22 C1010107 53 C5252522 84 C2×C2×C624125, 11, 13
23 C2222225 54 C1818185 85 C4×C1664162, 3
24 C2×C2×C2825, 7, 13 55 C2×C20402021, 2 86 C4242423
25 C2020202 56 C2×C2×C624613, 29, 3 87 C2×C2856282, 86
26 C1212127 57 C2×C18361820, 2 88 C2×C2×C1040103, 5, 7
27 C1818182 58 C2828283 89 C8888883
28 C2×C612613, 3 59 C5858582 90 C2×C1224127, 11
29 C2828282 60 C2×C2×C416411, 19, 7 91 C6×C1272122, 3
30 C2×C48411, 7 61 C6060602 92 C2×C2244223, 91
31 C3030303 62 C3030303 93 C2×C3060305, 11

参见

Lenstra 椭圆曲线分解Lenstra 给出的基于椭圆曲线的整数因子分解算法)

注释

  1. 高斯, DA, arts. 90-91
  2. 高斯, DA, arts.52-56, 82-89
  3. Riesel 包含所有情形。 pp. 267-275

参考文献

高斯算术研究(Disquisitiones Arithemeticae)由西塞罗拉丁语翻译成英语和德语。德语版包含他所有数论的论文:所有关于二次互反律的证明,高斯和符号的确定,双二次互反律的研究以及未发表的笔记。

  • Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English), , New York: Springer, 1986, ISBN 0387962549
  • Gauss, Carl Friedrich; Maser, H. (translator into German), , New York: Chelsea, 1965, ISBN 0-8284-0191-8
  • Riesel, Hans, , Boston: Birkhäuser, 1994, ISBN 0-8176-3743-5

外部链接

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.