Question

近世代数理论基础17：群的应用

Answer 1

满足 的a称为一个n次单位根,若 ,而 时, ,则称a为n次本原单位根

一个n次本原单位根可生成所有的n次单位根

方程 在复数范围内有n个根 ,其中

令 ,则S关于复数的乘法法构成一个n阶循环群,故 是本原单位根

n元多项式 ,若 ,有 ,则称为对称多项式

对称多项式与对称群 有关

中的元 是 这n个数码的一个置换

设 为任一多项式,定义 在 上的作用：

故 是对称多项式 ,有

由任一置换都可表成一些对换的乘积,故 是对称多项式 ,有

例：n=3时, ,取 ,则

是一个对称多项式

若取 ,则

也是一个对称多项式

例：在苯环上结合 ,一共可形成多少种不同的化合物

解：

RSA公钥密码

成立一个密码管理中心,使用密码的每个用户都需要取密码管理中心登记,每个用户在登记时,密码管理中心为用户选取一个大整数 ,其中p和q是两个不同的大素数

中心可计算欧拉函数 ,用户选择一个小于 且与它互素的正整数e

由辗转相除法可得整数d,l使 ,即

用户将n和e公开,将d,p,q保密,仅用户与中心知道

e称为该用户的公开密钥或加密密钥,d称为该用户的秘密密钥或解密密钥

在选择n时,n要选得足够大,使得在现有的技术条件下,因子分解n是不可能的

若不知道p和q则无法计算欧拉函数

只要知道了一个用户(A)的公开密钥e,任何人(B)都可向他发送加密信息,在计算机中,一个信息都由0和1组成的数字串表示,设B要发给A的信息m为 ,利用二进制,可将m表为一个整数 ,假设 ,B可利用A的公开密钥e将信息m加密,得到密文 ,B将密文c通过公开的信道发给A,A收到密文后,利用他的秘密密钥d解密,计算 ,由欧拉定理, ,A就从密文c得到了明文m

注：假设m与n互素,实际上m为p或q的倍数的可能性很小

任何人都可从公开信道上截获密文c,但由于他不知道A的秘密密钥d,因而很难从c算出m,若秘密密钥d泄露出去,该密码就被破译了

若不知道 ,很难从已知的公开密钥e推算出秘密密钥d,若知道 ,就相当于知道n的因子分解

由 可知p和q是二次方程 的根,故RSA公钥密码的安全性与因子分解问题密切相关,若n能被分解,该密码就能破了