第 3 讲
§7—9 一一映射，同态及同构（2课时）
(Bijection Homomorphism and Osomorphism )
本讲教学目的和要求：通过了解双射，同态及同构的理论，为后继课程中学习群同态，群同构（群第一、二同构定理）环同态，环同构理论做准备。具体要求：
1、在第一讲的基础上，对各类映射再做深入的研究。
2、充分了解双射（一一映射）的特性以及由此引导出的逆映射。
3、两个代数系统的同态的概念，尤其是同态的满射所具有的性质。
4、掌握同构映射的实质，为以后教学内容奠定基础，
本讲的重点和难点：本讲的重点在于对同态映射定义的了解；由同态满射引导的一系列性质及同构映射本质的掌握。而对双射及自身的逆映射之间的关系学生不易把握，需要认真对待。
本讲的教法和教具：在多媒体教室使用投影仪。在教学活动中安排时间让学生展开讨论。
本讲思考题及作业：本讲思考题将随教学内容而适当地展开。作业布置在本讲结束之后。
一、一一映射
在第1讲中，已对各类映射作了系列性的介绍，这里只对重要的一一映射作重点的讨论。
定义1、设?是集合A到A的映射，且?既是单的又是满的，则称?是一个一
一映射（双射）。
例1：},4,2,0,2,4,{2},2,1,0,1,2,{:ΛΛΛΛ--=→--=Z Z ?，
其中Z n n n ∈?=,2)(?，可知?显然是一个双射。
注意：Z 与偶数集Z 2之间存在双射，这表明：Z 与它的一个真子集Z 2一样“大”。
思考题：从例1中得知：一个无限集与其的某个真子集一样“大”。这是否可作为无限集都有的特性？即我们是否有如下的结论：A 为无限集的充要条件是A 与其某个真子集之间存在双射。
定理1：设?是A 到A 的一个双射，那么由?可诱导出（可确定出）A 到A 的一个双射1-?（通常称1-?是?的逆映射）
证明：由于?是A 到A 的双射，那么就A 中任一个元素a ，它在A 中都有逆象a ，并且这个逆象a 是唯一的。利用?的这一特点，则可确定由A 到A 的映射1-?：
a a A a A A =∈?→--)(,,:11??，如果a a =)(?，由上述说明，易知1-?是映射。
1-?是满射：A a ∈?，因?是映射a a A a =∈??)(,?使，再由1-?的定义知a a =-)(1?，这恰说明，a 是a 在1-?下的逆象。由a 的任意性，知1-?是满射。
1-?是单射：2121,,a a A a a ≠∈?若由?是满射21a a 及?的逆象分别是
22111121)(,)(,a a a a a a ==--??即及，又?是单射21a a ≠?， 这说明)()(2111a a --≠??，所以1-?是单射。
综合上述讨论知：1-?是A 到A 的一个双射。
结论：设A A →:?是映射，那么：
（1）?是双射??可唯一的确定一个逆映射A A →-:1?，使得：
? 1-?是双射；
? A A 1,111==--????；
? ?也是1-?的逆映射，且??=--11)(；
（2）?是双射A A 与?同时是有限集或同时是无限集。
二、变换
定义2：设A A →:?是映射，那么习惯上称为是A 的变换。
当?是双射（单射，满射）时，也称?为一一变换（单射变换，满射变换）
例2 19P
三、同态（本目与高代中的线性变换类似）——对代数系统的比较。 例3、设}1,1{:-=→A Z ?，其中},{οZ 中的代数运算ο就是Z 中的加法，而},{οA 中的代数运算ο为数中的乘法。
)
3()2()32(,111)1()1()1()1()3()2(,
1)5()32()32(,1)3(,1)2(,,1)(???????????οοοοο≠-≠?=-?-=--=-==+=-=-=∈?-=即
而那么
现设Z n n
定义3：设集合A A ,都各有代数运算οο,（称},{οA 及},{οA 为代数系统）而A A →:?是映射，且满足下面等式：
)()()(,,b a b a A b a ???οο=∈?（习惯上称?可保持运算）
那么称?是A 到A 的同态映射。
例4、设},{οZ 与},{οA 同例3，今设Z n n A Z ∈?=→,1)(:ττ为，那么
的同态映射到是即A Z n m n m n m n m Z n m τττττττ),()()(1
11)()(,1)(,,οοοο=∴=?==∈?
例5、},{οZ 与},{οA 同上，而???-= 1
1)(为奇数为偶数n n n σ
Z m n ∈?, （1） 若m n ,均为偶数时m n +?为偶数，
)()()(111)()(,1)()(m n m n m n m n m n σσσσσσσοοοο=?=?==+=∴而
（2）若m n ,均为奇数时m n +?为偶数，
)()()(1)1()1()()(,1)()(m n m n m n m n m n σσσσσσσοοοο=?=-?-==+=∴而
（3）若n 奇而m 偶时m n +?为奇数，则
)()()(11)1()()(,1)()(m n m n m n m n m n σσσσσσσοοοο=?-=?-=-=+=而
（4）若n 偶而m 奇时同理知)()()(m n m n σσσο
ο=. 由(1)～(4)知,σ是Z 到A 的同态映射.
如果同态映射?是单射（满射），那么自然称?是同态单射（同态满射），而在近世代数中，同态满射是尤其重要的。
定义4：若?是},{οA 到},{οA 的同态满射，那么习惯上称A A 与同态，并记为A ～A ；习惯上称A 是A 的同态象.
定理2. 如果?是},{οA 到},{οA 的同态满射，那么
（1） 若ο满足结合律ο?也适合结合律；
（2） 若ο满足交换律ο?也适合交换律.
证明：（1）任取?因,,,A c b a ∈是满射b b a a A c b a ==∈??)(,)(,,,??使，又因为A 中ο的满足结合律c b a c b a οοοο)()(=?
即))(())((c b a c b a οοοο??=，但是?是同态映射。
)()]()([)()()())((c b a c b a c b a c b a οοοοοοοο===??????
c b a c b a c b a c b a οοοοοοοο)()()]()([)()()))((===?????? 所以c b a c b a οοοο)()(=
同理可以证明（2）
定理3、设},,{⊕?A 和},,{⊕?A 都是代数系统，而映射A A →:?关于⊕?,以及⊕?,都是同态满射，那么：
（1） 若⊕?,满足左分配律?⊕?,也适合左分配律；
（2） 若⊕?,满足右分配律?⊕?,也适合右分配律。
证明：（1）?因,,,A c b a ∈?是满射c c b b a a A c b a ===∈??)(,)(,)(,,,???使. 又因为?是关于⊕?,及⊕?,的同态映射?
)
()()]()([)]()([)()()]()[()]([))()(()()(c a b a c a b a c a b a c a b a c b a c b a c b a ?⊕?=?⊕?=?⊕?=
?⊕?=⊕?=⊕?=⊕???????????? 即)()()(c a b a c b a ?⊕?=⊕?.
同理可证明（2）。
思考题1：在定理2及定理3中，都要求映射?是满射，似乎当?是同态满射时，才能将A 中的代数性质（结合律、交换律及分配律）“传递”到A 中，那么：
（1） 当?不是满射时，“传递”还能进行吗？（即定理2，3成立吗？）
（2） 即使?是满射，“传递”的方向能改变吗？（即A 中的性质能“传递”
到A 中去吗？）
（3） 依照定理2，3的思路，若将?换成同态单射后，能获得什么结论？
四、同构
定义4、设?是},{οA 到},{οA 的同态映射，若?是个双射，那么称?是同构映射，或称A 与A 同构，记为A A ?。
例6、设οοΛΛ与而},,3,2,1{},,3,2,1{---====-+Z A Z A 都是整数中通常的加法“+”，现作A n n n A A ∈?-=→,)(},{},{:??其中οο，那么?是同构映射. 事实上，
（1）?是单射：当???∴=-≠-=≠∈)()(,,m m n n m n A m n 时且是单射.
（2）?是满射：??∴∈=--=-∈-∈?A t t t A t A t )()(,,且则是满射.
（3）?是同态映射：
)()()()
()()()()()()(,,m n m n m n m n m n m n m n A m n ???????οοοο=∴=-+-=+-=+=∈?
由（1），（2），（3）知，?是同构映射，即A A ?。
定理4、设?是},,{+οA 到},,{+οA 的同构映射，那么
（1）“ο”适合结合律?“ο”也适合结合律；
（2）“ο”适合交换律?“ο”也适合交换律；
（3）“ο”和“+”满足左（右）分配律?“ο”和“+”满足 左（右）分配律。
注意：由上述表明，同构的两个代数体系由运算所带来的规律性是相同的，因此，同构的两个代数体系尽管可能有这样或那样的差别，但从近世代数的宗旨来看，我们自然认为：它们的差别是表面上的，次要的，而它们的共同点——运算所体现的规律性则是本质的，主要的。于是，我们需要阐明近世代数的观点是：凡同构的代数体系都认为是（代数）相同的。
在上述的观点下，一个代数体系经同构映射而保持不变的性质叫做它的代数性质。于是，由代数运算所表述的任意一个性质都是代数性质。我们将代数体系的代数性质的总合统称为它的代数结构。因此，同构的代数体系由于完全相同的代数结构。研究代数体系的首要目的就是确定所有互不同构的代数体系以及它们的代数结构。而为了确定一个代数体系的代数结构，只须让它与一个代数结构已经清楚的代数体系同构则可。
课堂练习：设},3,2,1{},,3,2,1,0{ΛΛ==*N N ，那么，},{},{++*N N 与不可能同构.
证明：（反证法）若N N ?
?*，那么?是同构映射。设 推出矛盾中没有但而,00)1()0()1(,110,)1(,)0(N n m n m m N n =?+=+==∴=+=∈=????? 思考题2：
试证：（1）},{},{??*N N 与不同构（为普通乘法）。
（2）},{},{?+Z Z 与不同构.
（3）},{},{?+*Q Q 与不同构（其中*Q 为非零有理数集）.
思路：
（1）（反证法）若N N ?*，且?是*N 到N 的同构映射。则
推出矛盾令,1)0()0()00()0(),1()0(,1)1(2=∴==?==∴≠∴==a a a a a ??????
（2）（反证法）若Z Z ?，且?是Z 到Z 的同构映射。则
推出矛盾令),(2)()()()0(12)(,1)0(n n n n n n -=-=-==∴==???????.
（3）（反证法）若*?Q Q ，且?是Q 到*Q 的同构映射。则
推出矛盾令,0,02)()()()1)(1(11)(,1)0(=∴=?+==--=∴-==q q q q q q q ?????
五、自同构
定义5、设},{οA 是一个代数体系，若?是A 到A 的一个同构映射，那么称?为A 的一个自同构。
例7（26P ）
思考题3
（1） 两个代数体系如果同构了，那么它们之间的同构映射是唯一的吗？
（2） 设F 为数域，44321}),,,{(F F a a a a a A i =∈=
)(24321F M F x x x x x A i =?
?????∈???? ??= 试证：},{},{++A A 与是同构的。（其中“+”为数组间的加法，“+”为矩阵的加法）
作业：19P ①② 23P ② 26P ②
全同态加密算法研究与实现素质拓展报告 FHE 的应用价值早就被众人所熟知，但是直到目前为止，还没有真正实用的FHE 方案。2009 年，Gentry 首次创造性地提出基于理想格的第一个 FHE 方案之后，FHE 的研究再一次成为了众多密码学家和公司关注的焦点。因此，FHE方案的构造是当前密码学领域的主要研究的问题之一。 在以前的基于“译码难题（其中包括格上难题）”陷门的非对称同态密码方案的构造过程中，密码学家所考虑的是如何将有限的双同态的“限”做大，使得它能够接近无限的双同态。其具体做法是将密文空间的“模”尽可能的做大而能够容纳大尺寸的误差。但是，这样做的代价是密文空间的尺寸将大得难以承受。 2009 年 Gentry 创造性的提出了一个新的 FHE 方案的构造方法 [2] 。由于明文比特之间的“异或”运算和“与”运算构成了操作完备集，Gentry 基于一个对“异或”操作（或者是 mod 2 加法运算）和“与”操作（或者是 mod 2 乘法运算）同态加密 方案来实现 FHE 方案的构造，其主要构造思想是： 构造一个支持有限次“异或”操作（或者是 mod 2 加法运算）和“与”操作（或者是 mod 2 乘法运算）同态的加密方案。在构造一般的同态加密方案时，为了保证安全性，Gentry 引入了噪声。但是随着同态操作的进行，噪声的值将迅速增长，当噪声的尺寸过大时，解密会出错。 为了降低噪声的尺寸，Gentry 考虑到可以对解密运算进行“密文端的同态运算”——重加密（recrypt），从而实现压缩噪声的尺寸进而继续进行加法同态和乘法同态运算。为此，Gentry 引入了重加密和自举的概念。Gentry 的构造方法完成了一个不可思议的功能：解密算法不但能够表示成简单的布尔运算，而且该运算竟然能够进行“密文端的同态运算”；通过递归式自嵌入的方式，一般地同态加密方案可以转化为 FHE 方案。 重加密技术是通过实施“密文端的同态运算”来实现的。假设消息 m 在公钥1pk 作用下的密文为1c ，符号 D 表示解密电路。如果使用加密公钥2pk 加密1sk 后的解密密钥为1sk ←Encrypt(2pk 1sk),通常情况下，对于一个加密方案实施二次加密的过程是：首先对外层加密进行解密，而后才能对内层加密进行解密。但是， Recrypt 算法的奇妙之处正在于它能够突破这种常规，具有直接对”内层加密”实施解密的能力。当然，在这个过程中，必须保证密文的噪声不会增大或者增长不能太大。
第九节 同态基本定理与同构定理 重点、难点：同态基本定理，满同态与子群的关系. 一 同态基本定理 前几节是研究一些定量的东西，下面我们来研究一些定性的东西.本节中的同态基本定理是群论中的研究基础. 定理2.9.1 一个群G 与它的每一个商群N G /同态. 证 令G a aN a N G G ∈?→,;/: π 显然π是G 到N G /的满射.G b a ∈?,，)()())(()()(b a bN aN N ab ab πππ=== 故π是一个满同态. 注1 定理2.9.1中的π称为自然同态； 注2 自然同态π一定是满同态. 利用子群来研究群本身，任意给定一个不变子群N ，有两个可以供我们参考的群： N 和N G /，由于0/→→→N G G N ，故更容易推测G 的性质. 自然会问：定理2.9.1的逆命题是否成立？即0→'→G G ，G '是否与G 的某个商群是同构的呢？我们说是对的.首先有一个概念. 定义2.9.1 设G G '→Φ:为一个群同态.e '为G '的单位元,集合 })(|{e a G a Ker '=Φ∈=Φ称为同态映射Φ的核. 注1 未必要求Φ为满射，但本书中同态均为满同态； 注2 一个同态是单同态?G e Ker ?=}{φ. 推论2.9.2 设π是N G G /→的自然同态，则N Ker =π. 证 由于N G /的单位元是N ，则 N N a G a N aN G a N a G a Ker =∈∈==∈==∈=}|{}|{})(|{ππ. 定理2.9.3 （同态基本定理）设?是群G 到群G '的一个同态满射，则 (1)G Ker ?； (2)G Ker G '??/. 证 (1)由于φ??≠?∈Ker Ker e .,,,G x Ker b a ∈?∈??则e b a '==)()(??为G '的单位元.则
整数上全同态加密方案分析 一篇论文看完了，如果都看懂了的话，很多人觉得案例都是小菜一碟，但是在我写这个案例的时候我发觉论文看懂了，更需要案例或者说实现来进一步深入或者夯实，因为只有通过具体的实现步骤，才能发现有些在论文中的一些细节问题，反过来更可以促进对论文的理解。 整数上全同态加密方案有两篇非常经典的论文，一篇是《Fully Homomorphic Encryption over the Integers》以下简称DGHV方案，还有一篇是Gentry写的《Computing Arbitrary Functions of Encrypted Data》简称CAFED论文。入门者适合先阅读CAFED论文，这并不是说这篇论文简单，只是因为这篇文章的写法很通俗（严格意义上这篇文章并不是一篇真正的论文，是给杂志写的文章，有点科普性质），有一个很好的比喻的例子“Glovebox”贯穿于整个论文中，Gentry的文笔很好写的也很生动，对有些地方进行了背景解释，而这些解释恰好是DGHV论文中没有说的，当然一开始要想把CAFED论文彻底读懂也不是那么容易的。这个时候可以开始阅读DGHV这篇论文。这篇论文对于我来说是百读不厌，因为有些地方就算读了一百篇也不见得可以理解，而且这篇文章很适合深挖，有些很有趣的地方，例如噪声参数的设置等等。还有一篇论文就是全同态的经典论文《Fully homomorphic encryption using ideal lattices》，如果对
格不熟悉的话，可以读这篇文章的前面三分之一，因为有详细的全同态的定义、层级全同态、允许电路、增强解密电路、bootstrable、重加密原理，以及如何通过递归实现全同态的，尤其是递归实现全同态的过程，在论文中还是值得反复理解的。剩下的当然还有Gentry 的博士论文，也可以分阶段阅读。 这篇文章就算是一个阅读笔记吧，分为两个部分，一个是实现过程，另一个是方案的参数分析。 一、方案实现过程 1、全同态加密方案 至于什么是全同态等等形式化定义我就不说了，请参阅论文。 全同态加密用一句话来说就是：可以对加密数据做任意功能的运算，运算的结果解密后是相应于对明文做同样运算的结果。有点穿越的意思，从密文空间穿越到明文空间，但是穿越的时候是要被蒙上眼睛的。另外上面的那句话是不能说反的，例如：运算的结果加密后是相应于对明文做同样运算结果的加密，这样说是不对的，因为加密不是确定性的，每次加密由于引入了随机数，每次加密的结果都是不一样的，同一条明文对应的是好几条密文。而解密是确定的。 全同态具有这么好的性质，什么样的加密方案可以符合要求呢？往下看： Enc(m):m+2r+pq Dec(c):(c mod p)mod2=（c–p*「c/p」）mod2=Lsb(c)XOR Lsb(「c/p」)
若一个加密方案对密文进行任意深度的操作后解密，结果与对明文做相应操作的结果相同，则该方案为完全同态加密方案。 通常一个公钥加密方案有三个算法：KeyGen算法（密钥生成），Enc算法（加密），Dec算法（解密）。但是在全同态加密中，除了上述三个算法之外，还包含第四个算法：Evaluate算法（密文计算），这个算法的功能是对输入的密文进行计算。 KeyGen算法（密钥生成）用于生成公钥和密钥，公钥用于加密，私钥用于解密。还可能生成另外一种公钥，即密文计算公钥，我们把它称之为Evk。 密文计算公钥Evk的作用是在执行Evaluate算法时用到，而且Evk 的形式与使用的全同态方案直接相关。例如，如果是通过启动技术（Bootstrapple）获得全同态加密，即每次密文计算前要用同态解密约减密文的噪音，这时Evk就是对密钥的每一位加密后生成的密文，即密钥有多少位，Evk里包含的公钥就有多少个。Evk中每个公钥的大小就是使用Enc加密后产生密文的大小。
当然还有其他情况，例如，如果使用密钥交换与模交换技术获得全同态加密，典型代表就是BGV方案。这时Evk中包含的就是L–1个矩阵，L是方案中电路的深度，该矩阵用于密钥转换。每次密文计算后，都需要使用Evk中的公钥将维数扩张的密文向量转换成正常维数的密文向量。 当然还有一种情况就是不需要Evk，例如在Crypto13会议的论文GSW13中，Gentry使用的密文是矩阵（方阵），所以密文乘积或相加不会产生密文维数改变的事情，所以在密文计算时没有用到公钥，这也是该论文可以产生基于身份或基于属性全同态加密方案的根本原因。 Enc算法（加密）和我们平常意义的加密是一样的，但是在全同态加密的语境里，使用Enc算法加密的密文，一般称之为新鲜密文，即该密文是一个初始密文，没有和其他密文计算过。所以新鲜密文的噪音称之为初始噪音。 Dec算法（解密）不仅能对初始密文解密，还能对计算后的密文解密。但由于部分同态加密方案中密文存在噪音，例如在整数上的全同态加密方案里，密文乘积的噪音是噪音之积，密文加法的噪音是噪音之和。所以当密文计算到一定程度，其噪音将超过上限，所以对这样的密文解密将可能失败。全同态加密的关键就是对噪音的控制，使之能对任何密文解密。 最后一个算法：Evaluate算法（密文计算），这个算法是整个全同态加密四个算法中的核心。可以做个这样的比喻：前面三个算法是大楼的地基，后面这个Evaluate算法就是大楼。这个比喻在后面会体会到它
授课时间十一周第 2 次课
更广泛的同态映射定义 定义设V1=
全同态加密 丁津泰 一、引言 人们普遍认为全同态密码是密码学中的圣杯。Craig Gentry 在近期提出的解决方案虽然在实际应用中效率不高，但在该领域仍是一个重大突破。自那以后，人们又在提高全同态密码的效率问题上取得了很大的进步。 在一个加密体系中，Bob通过加密明文得到密文，Alice解密密文得到明文。 在全同态密码体系中，第三方可以在不知道明文内容的情况下，针对密文做一系列计算，解密的结果和对明文进行相同计算的所得相同。云计算是全同态密码的一个主要应用方向。Alice可以将她的数据存储在云端——例如，一个通过英特网连接的遥远的服务器。由于云端的存储和计算能力都要远远优于Alice的终端设备，因此她可以使用云端服务器来处理她的数据。不过，Alice还是无法信任云端，因为有些数据是很敏感的（例如，病人的医疗记录），所以她更希望云端在不知道数据本身的前提下处理数据、计算结果。因此，Alice将数据加密，传送给云端，云端在不知道原始数据的前提下对加密后的数据进行一系列数学运算。 使用全同态密码，云端可以在不知道“关键字”的前提下，使用搜索引擎搜索用户需要的内容。更精确的讲，全同态密码有如下特点：密文ci 解密得到明文mi ，其中ci , mi 是环上的元素，在这个环上，只有加法操作和乘法操作： Decrypt c i + c j=m i+ m j Decrypt c i×c j=m i× m j 这就表示解密是双重同态的（Doubly homomorphic）也就是说，解密在加法和乘法上同态。全同态意味着不论函数 f 是一个由多少（即便很多个）加法和乘法组成的环，都有如下的公式成立： Decrypt f c1,…,c n= f m1,…,m n 如果云端可以高效的计算出f c1,…,c n的结果，并且这种计算是在不知道明文m1,…,m n的前提下进行的，那么这个加密体系是安全且高效的。 全同态加密既适用于公钥加密体系，也可用于对称加密体系。 1978年，在RSA密码系统发明后不久，Rivest, Adleman, 以及Dertouzos 三人提出了全同态加密体系——所谓的“隐私同态”。在他们的论文中这样写到，
全同态加密技术助力云计算 作者：汤姆?西蒙尼发稿时间：2010-06-21 14:20:26 点击：2442 利用加密算法，云端服务器不用解密就可以处理敏感数据。 利用一项全新的技术，未来的网络服务器无须读取敏感数据即可处理这些数据。去年，一项数学论证提出的几种可行性方案问世，这使得研究人员开始努力将方案变得更实际。 2009年，IBM公司的克雷格·金特里（Craig Gentry）发表了一篇文章，公布了一项关于密码学的全新发现——一项真正的突破。他发现，对加密的数据进行处理得到一个输出，将这一输出进行解密，其结果与用同一方法处理未加密的原始数据得到的输出结果是一样的。这听起来就像是不知道问题也能给出问题的答案一样。 这一名为“全同态加密”的技术被冠以“密码学的圣杯”的称号。对数据进行加密给计算带来了难度，但如能够在不解密的前提下进行计算则进一步提高了数据的安全性。例如，远程计算服务提供商收到客户发来的加密的医疗记录数据库，借助全同态加密技术，提供商可以像以往一样处理数据却不必破解密码。处理结果以加密的方式发回给客户，客户在自己的系统上进行解密读取。这一技术同样可以应用到网络邮件或在线办公软件套装中。 英国布里斯托尔大学密码学教授奈杰尔·斯玛特（Nigel Smart）与比利时鲁汶大学研究员弗雷德里克·韦尔科特朗（Frederik Vercauteren）正在协作，对最原始的技术方案加以修改并进行实施和测试。斯玛特说：“我们吸收了金特里的方案并对之作了简化。”在最初的方案中，金特里使用了矩阵和矢量进行加密，斯玛特与韦尔科特朗进行了改进，改用整数和多项式作为加密办法。“这使得数据更简单易懂，处理起来更容易。”斯玛特说，“从而可以真正计算这些数据。” 最初的方案依赖矩阵和矢量，每一步都要分别计算每个元，这已经足够复杂；计算完矩阵后还要处理数据本身，使得计算更加复杂。这使得矩阵和矢量加密方法实用性不强。斯玛特与韦尔科特朗改写了加密方法，免去了复杂的计算，使得金特里的理念得以在电脑上进行实施和测试。“我们确实实现了他的理念：对数据进行加密但计算过程更加简单。”斯玛特说，“我们可以处理30个顺序操作。” 但是这一方案也有其局限性。随着计算步骤的增加，连续加密的计算结果质量在下降，用斯玛特的话说就是数据“变脏了”。不能进行任意计算，意味着现有的算法版本还未能实现全同态。 针对这个问题，金特里开发了一种算法，能够定期对数据进行清理，实现系统的自我纠正，从而实现全同态。然而，金特里的算法要求系统实现一定量的计算，斯玛特目前还无法实施。金特里表示，他与IBM的同事Shai Helevi已经对斯玛特的方案进行了修改，正在进行测试，今夏晚些时候将宣布改进结果。
信息系统安全题目: 同态加密综述 姓名:### 学号:2013202110076 武汉大学 二○一三年十月
同态加密综述 概念 2009年，IBM公司的克雷格·金特里（Craig Gentry）发表了一篇文章，公布了一项关于密码学的全新发现：一项真正的突破。他发现，对加密的数据进行处理得到一个输出，将这一输出进行解密，其结果与用同一方法处理未加密的原始数据得到的输出结果是一样的。这听起来就像是不知道问题也能给出问题的答案一样。 记加密操作为E，解密为E'；明文为m，加密得e，即 e = E(m)，m = E'(e)。已知针对明文有操作f，针对 E 可构造F，使得F(e) = E(f(m))，这样 E 就是一个针对 f 的同态加密算法。 来源 2009年9月，Craig Gentry 的论文发表于STOC。一名IBM研究员解决了一项棘手的数学问题，该问题自从几十年前公钥加密发明以来一直困扰着科学家们。该项创新为“隐私同态（privacy homomorphism）”或“全同态加密（fully homomorphic encryption）”领域的重要技术突破，使得加密信息，即刻意被打乱的数据仍能够被深入和无限的分析，而不会影响其保密性。 IBM研究员Craig Gentry设计了这一解决方案。他使用被称为“理想格ideal lattice”的数学对象，使人们可以充分操作加密状态的数据，而这在过去根本无法设想。经过这一突破，存储他人机密电子数据的电脑销售商就能受用户委托来充分分析数据，不用频繁与用户交互，也不必看到任何隐私数据。利用Gentry的技术，对加密信息的分析能得到同样细致的分析结果，就好像原始数据完全可见一样。 加密机理 整数上全同态加密方案有两篇非常经典的论文，一篇是《Fully Homomorphic Encryption over the Integers》以下简称DGHV方案，还有一篇是Gentry写的《Computing Arbitrary Functions of Encrypted Data》简称CAFED论文。
§8 线性空间的同构 一、数域 P 上的 n 维线性空间 n P 二、数域 P 上的一般的n 维线性空间 V 例如：[]n P x 等 设n εεε,,,21 是线性空间V 的一组基，在这组基下，V 中每个向量都有确定的坐标， 而向量的坐标可以看成n P 元素，因此向量与它的坐标之间的对应实质上就是V 到n P 的 一个映射.显然这个映射是单射与满射，换句话说，坐标给出了线性空间V 与n P 的 一个双射. 这个对应的重要性表现在它与运算的关系上.设 n n a a a εεεα+++= 2211, n n b b b εεεβ+++= 2211 而向量,,βα的坐标分别是),,,(21n a a a ,),,,(21n b b b ，那么 n n n b a b a b a εεεβα)()()(222111++++++=+ ; n n ka ka ka k εεεα+++= 2211. 于是向量,βα+αk 的坐标分别是 ),,,(),,,(),,,(21212211n n n n b b b a a a b a b a b a +=+++, ),,,(),,,(2121n n a a a k ka ka ka =. 以上的式子说明在向量用坐标表示之后，它们的运算就可以归结为它们坐标的运算. 因而线性空间V 的讨论也就可以归结为n P 的讨论. 三、线性空间同构 1．定义11 数域P 上两个线性空间V 与V '称为同构的，如果由V 到V '有一个双射σ，
具有以下性质： 1）)()()(βσασβασ+=+; 2) ).()(ασασk k = 其中βα,是V 中任意向量，k 是P 中任意数.这样的映射σ称为同构映射. 前面的讨论说明在n 维线性空间V 中取定一组基后，向量与它的坐标之间的对应 就是V 到n P 的一个同构映射.因而，数域P 上任一个n 维线性空间都与n P 同构. 2．同构映射具有下列性质 由定义可以看出，同构映射具有下列性质： (1). )()(,0)0(ασασσ-=-=. (2). )()()()(22112211r r r r k k k k k k ασασασααασ+++=+++ . (3).V 中向量组r ααα,,,21 线性相关?它们的象)(,),(),(21r ασασασ 线性相关. 因为维数就是空间中线性无关向量的最大个数，所以由同构映射的性质可以推知， 同构的线性空间有相同的维数. (4). 如果1V 是V 的一个线性子空间，那么，1V 在σ下的象集合 {}11|)()(V V ∈=αασσ 是)(V σ的子空间，并且1V 与)(1V σ维数相同. (5). 同构映射的逆映射以及两个同构映射的乘积还是同构映射. 同构作为线性空间之间的一种关系，具有反身性、对称性与传递性. 既然数域P 上任意一个n 维线性空间都与n P 同构，由同构的对称性与传递性即得， 数域P 上任意两个n 维线性空间都同构. 3. 定理12 数域P 上两个有限维线性空间同构的充要条件是它们有相同的维数. 由线性空间的抽象讨论中，并没有考虑线性空间的元素是什么，也没有考虑其中运算 是怎样定义的，而只涉及线性空间在所定义的运算下的代数性质.从这个观点看来， 同构的线性空间是可以不加区别的.因之，定理12说明了，维数是有限维线性空间的 唯一的本质特征.
本技术公开了一种改进的格上基于身份的全同态加密方法。该方法按照以下步骤实施：首先利用一种新型陷门函数与对偶LWE算法相结合，构造一个改进的标准模型下格上基于身份的加密方案，然后利用特征向量的思想将该方案转化为一个改进的标准模型下格上基于身份的全同态加密方案。本技术所公开的方法消除了基于身份全同态加密运算密钥的问题，且所生成的格的维数更低，具有更高的实际应用可行性。 权利要求书 1.一种改进的格上基于身份的全同态加密方法，其特征在于采用两层结构设计：首先将新型陷门函数与对偶LWE算法相结合，构造一个改进的标准模型下格上基于身份的加密方案iIBE，然后利用特征向量方法将iIBE转化为标准模型下格上基于身份的全同态加密方案IBFHE；IBFHE方案包括私钥生成中心，云服务方，消息发送方和消息接收方，它们之间采用双向通信； 所述改进的格上基于身份的全同态加密方法具体实施步骤是： 首先构造标准模型下的格上基于身份的加密方案iIBE： iIBE方案需要以下基本参数：均匀随机矩阵和其陷门其中n是安全参数，m＝O(n log q)，w ＝nk，模数q＝q(n)；构造一个公开矩阵其中In是n×n单位矩阵，FRD编码函数H1: 系统建立算法iIBE-Setup(1n)：选取均匀随机矩阵选取n维均匀随机向量运行陷门生成算法TrapGen(1n,1m,q,H)，其中为随机的可逆矩阵；输出矩阵和格Λ⊥(A)的陷门矩阵输出MPK＝(A,u)，MSK＝R； 用户密钥提取算法iIBE-Extract(MPK,MSK,id)：利用FRD编码函数H1:将用户身份id映射为一个可逆矩阵运行原像采样算法SampleL(A,Hid·G,R,u,σ)，输出用户密钥e，满足Aide＝u，其中
§6.8 线性空间的同构一、 同构映射的定义 一、同构映射的定义 二、同构的有关结论
我们知道，在数域P 上的n 维线性空间V 中取定一组基后，V 中每一个向量有唯一确定的坐标向量的坐标是P 上的n 元数组，因此属于P n . 这样一来，取定了V 的一组基对于V 中每一个向量，令在这组基下的坐标与对应，就得到V 到P n 的一个单射 反过来，对于P n 中的任一元素是V 中唯一确定的元素，并且即也是满射.因此， 是V 到P n 的一一对应.引入12(,,,),n a a a L α12,,,,n εεεL αα12(,,,)n a a a L α12:,(,,,) n n V P a a a σα→a L 12(,,,), n a a a L 1122n n a a a αεεε=+++L 12()(,,,), n a a a σα=L σσ
这个对应的重要必性表现在它与运算的关系上.任取设 ,,V αβ∈12()(,,,)n b b b σβ=L 1122,n n a a a αεεε=+++L 1122n n b b b βεεε=+++L 12()(,,),n a a a σα=L 则1122()(,,) n n a b a b a b σαβ+=+++L 12()(,,)n k ka ka ka k P σα=?∈L 归结为它们的坐标的运算. 这就是说，向量用坐标表示后，它们的运算可以1212(,,)(,,,)()()n n a a a b b b σασβ=+=+L L 12(,,)(), n k a a a k σα==L 从而
一、同构映射的定义 设都是数域P 上的线性空间，如果映射,V V ′具有以下性质： V V σ′→：则称的一个同构映射，并称线性空间V V σ′是到同构，记作V V ′与. V V ′?ii) ()()(), ,V σαβσασβαβ+=+?∈iii) ()(),,k k k P V σασαα=?∈?∈i) 为双射 σ
如何学习全同态加密 学习全同态加密需要三部分知识：数学基础，格密码基础，全同态加密。 许多研究生在学习全同态加密时，以为只是学习全同态加密，所以看第一篇文章时，从入门直接到放弃。 这是因为任何知识都需要其它的知识作为基础，而全同态加密属于公钥密码学，所以首先它是一个加密算法，然后具有同态属性。 因此，必须熟悉格加密算法，以及相关的数学知识。下面我们分别说说这三部分。数学基础 因为目前全同态加密都是构建在格密码算法之上的，所以格密码需要哪些数学知识，以及全同态加密本身需要哪些数学知识就构成了整个学习所需的数学基础。格密码需要哪些数学基础呢？ 主要需要线性代数和抽象代数的基础。线性代数一般理工科都学过，例如矩阵，行列式等计算，向量空间的基等。格加密算法里的计算都是矩阵行列式计算。抽象代数估计不是数学专业的，有可能没学过。抽象代数里的群、环、域等知识非常重要，尤其是环，是格加密的数学基础。抽象代数中一般还会涉及到数论一些知识，也在全同态加密中会使用，例如模计算等。 初学者可以看：An Introduction to Mathematical Cryptography 补充相关数学知识。
当然公认的最好的密码学教材当属Jonathan Katz的INTRODUCTION TO MODERN CRYPTOGRAPHY。如果你想全面而深入的学习密码学可以看这本书。里面都有相关的数学知识。 格密码 学习全同态加密必须熟悉格密码，这是绕不开的。因为本身全同态加密就是格密码算法上进行构造的。 那么如何学习格密码呢？ 应该从LWE加密算法开始学习，然后过渡到环LWE加密算法上。一定要把LWE 加密算法的过程搞清楚，这样学习全同态加密会轻松许多。 如何学习LWE加密算法呢？ 建议看Oded Regev的一篇综述文章：The Learning with Errors Problem 。这篇文章相对写的轻松一些。不过不要忘了，如果想一下看懂是不可能的。需要反复看。注意LWE加密中的各个参数的意义。 Oded Regev本身就是提出LWE归约问题的作者，也写过一个格密码讲义，但是非常理论，不适合初学者看。 全同态加密的学习
全同态加密释疑（一）：四个算法（1） 陈智罡 2009年全同态加密（Fully Homomorphic Encryption）的诞生，不仅是密码学界的一个大的突破（Breakthrough）,而且是计算机理论界的一个突破。自从2011年创建了全同态加密QQ群，从几十号人到现在的将近200人，来自各个大学，包括国外。可见人们对全同态加密研究的热情。 另外在网上有许多同学问我一些问题，有些问题很雷同，可能也是初学者必经之路。全同态加密的入门确实比较难。作为一个过来者，非常愿意分享我的一些心得，所以这里我会把一些共性的问题，用一种深入浅出的方法讲述，希望每个人都能看懂。 其实在全同态加密论文的背后，有许多可以说出来的秘密，只不过这个秘密在论文里没空间也不适合讲，那么这里就搞一个专题“全同态加密释疑”，细说从头每个让你困惑的秘密。如果有愿意加入的朋友，可以一起分享心得体会。 今天说说全同态加密的四个算法。可能有些人会说，这个谁不知道，但是知道并不意味着清楚，只有深刻理解了这四个算法的含义，尤其是第四个算法的含义，才能清楚什么是部分同态加密方案，什么是执行自己的解密电路等等概念。 通常一个公钥加密方案有三个算法：KeyGen算法（密钥生成），Enc算法（加密），Dec算法（解密）。但是在全同态加密中，除了上述三个算法之外，还包含第四个算法：Evaluate 算法（密文计算），这个算法的功能是对输入的密文进行计算。 首先说说KeyGen算法（密钥生成）。该算法用于生成公钥和密钥，公钥用于加密，私钥用于解密，这个地球人都知道。但是还可能生成另外一种公钥，即密文计算公钥，我们把它称之为Evk。
同态基本定理的应用 摘要：通过具体例子说明当所给的群(或环)是商群(或商环)时,利用同态基本定理可以简化同构问题的证明过程. 关键词：同态基本定理;同构;商群;商环 证明同构问题,一般是通过建立映射并证明该映射是同构映射来完成的,然而对商群(或商环)之间的同构关系却不容易用此种方法来证明.同态基本定理(简记为FHT)是代数学的一个重要定理:设G是一个群,H是G的不变子群,令5:a y aH,Pa I G,则5是G到GPH的满同态;反之,若5是G到Gc的同态满射,则GPker5μGc.类似可得到环同态基本定理.本文给出的证明实例表明,利用FHT证明商群(商环)的同构问题,可以使证明过程简化.这种方法只须建立一个同态满射,求出同态核,就可获得问题的证明. 本文约定:H A G表示H是G的子群(或子环) ; H ¨G 表示H 是G 的不变子群( 或理 想) ; G1 μG2表示G1与G2同构. 以下是同态基本定理的应用举例. 例1求证:如果H、K A G,且K¨G,那么(HK)PKμHP(H HK) . 证明由H、K A G]H H K A G,又由K¨G]H HK¨H]H P(H HK)有意义. ( ? ) 定义5: hk y h#H HK , 其中h、k 分别为H 、K 中的任意元. 若hk=hckc]kkc- 1=h- 1hc]h- 1hcI H HK]h#H HK=hc#H HK I H P(H HK) .即 5( hk ) 与5( hckc) 表示相同的陪集, 因此5 是HK 到HP( H HK ) 的映射. ( ? ) 对HP( H HK ) 中的任意元h#H H K ( 其中h I H ) , 由于e I K , 故至少存在HK 中的元he=h,使得5(he) =h#H HK,所以5是HK到HP(H H K)的满射. ( ? ) 因为K ¨G, 所以对任意hcI H 有Khc= hcK , 于是对任意的k I K , 存在kd I K , 使得khc= hckd, 从而5( hk#hckc) = 5( hhc#kdkc) = hhc#H HK . 但由于hhc#H HK = h#( H HK ) * hc#( H HK ) ] 5( hk#hckc) = 5( hk) * 5( hckc) , 所以5 是一个群同态. ( … ) 由于e#H HK = H HK 是H P( H HK ) 的单位元, 因此ker 5 = { hk I HK | 5 ( hk) = H H K } . 又由于5( hk ) = h#H HK , 因此应有h#H HK = H HK . 从而h I H HK ] ker 5= { hk I HK | 5( hk ) = H HK } = ( H HK ) #K = K , 于是, 根据FHT 得到( HK )PK μH PH H K . 例2求证:如果H、K¨G、K AH,那么GPHμ(GPK)P(H PK) . 证明( ? )定义5:g y gK#(H PK) .对所有的g I G,显然它是G到(GPK)P(H PK)的映 射,且容易看出5是满射. (? )对任意的x、y I G,5(xy) = (xy)K#(H PK) =[ ( xK ) #( yK ) ] ( H PK ) = [ ( xK ) #( HPK ) ] * [ ( yK ) #( H PK ) ] = 5 ( x ) *5 ( y ) , 所以5 保持群运算. (? )ker 5= { g I G | 5 ( g ) = e#( H PK ) , e 是GPK 中的单位元} , 即ker 5 = { g I G | 5 ( g) = H PK } = H , 因此根据FHT, GPker 5 = GPH μ( GPK )P( H PK ) . 例3设S是环R的子环,I是R的理想,求证:SP(S H I)μ(S+I)PI. 证明( ? )易知S+I是R的子环,I是S+I的理想,S H I是S的理想,因此(S+I)
?? ???↓ 映射集合线性空间的同构 直和和并子空间与子空间的运算与坐标变换过度矩阵线性空间的基变换坐标基线性空间的维数→→→→,,:)(, ,, 同构映射、同构映射的六个性质，两个线性空间同构 二．习题举例 例1：求线性空间的维数 1）数域P 上所有反对称矩阵组成的线性空间。 2 ) 1(-n n 2）数域P 上所有上三角形矩阵组成的线性空间。2 ) 1(+n n 例2：证明：P n 的任意一个真子空间都是若干个n-1维子空间的交。 证明：设V 是P n 的任意一个真子空间，不仿设 V=L(r ααα ,,21)， )(n r < 它是线性方程组?? ? ??? ?=++=+++=+++--,0,0, 0)(11)(22221211212111n n r n r n n n n n x b x b x b x b x b x b x b x b 的解空间， 记k W 为线性方程组02211=+++n kn k k x b x b x b ，k=1,2,…,n -r 的解向量空间,显然是P n 的n-1维子空间，且V 恰好是这n-r 个n-1维子空间的交。
例3设n ααα ,,21是n 维线性空间V 中的n 个向量，V 中的每个向量都可以由它们线性给出，求证：n ααα ,,21是V 的一组基。 证明：只须证明n ααα ,,21线性无关，事实上，如果rk r r ααα ,,21是 n ααα ,,21的一个极大线性无关组，则rk r r ααα ,,21是V 的一组基，所 以n k =，向量组rk r r ααα ,,21就是向量组n ααα ,,21，是线性无关。 例4：在5R 中求齐次线性方程组 ??? ??=-+-+=+-+-=+-+-0 220322402254321 5432154321x x x x x x x x x x x x x x x ， 的解空间的维数与一组基。 解：????? ??------=211213224111122A ??? ? ? ??------→533605336021121????? ? ??----→00 000351 12021 121 ??????? ? ? ?? ---→0000035 1120310001；解空间的维数是3，一组基是 ) 6,0,0,5,2()0,2,0,1,0(), 0,0,2,1,0(321=-==βββ 例5：设??? ? ??-=0110A ，证明：实数域上矩阵 A 的全体实系数多项式)(A f 组成的空间? ?? ? ?? ???? ??-==0110|)(A A f V 与 复数域C 作为实数域R 上的线性空间},|{R b a bi a V ∈+='同构。
第十四讲同态与同构 §14.1. 同态 §14.2. 同态基本定理 §14.1. 同态 在讲授半群和monoid时，我们已定义过它们的同态与同构，现定义群同态与群同构。 1.1.定义：设(G,*)与(H,?)为群，f: G→H为映射 (1)f为从群G到群H的同态，指(?a,b∈G)(f(a*b)=f(a)?f(b))， 记为G∽f H (2)f为从G到H的满同态指f为同态且f为onto (3)f为从G到H的同构指f为同态且f为1-1&onto，记为G ≌f H (4)f为从(G,*)到(G,*)的自同态指f(ab)=f(a)f(b) (5)f为从(G,*)到(G,*)的自同构(automorphism)指f为自同态且 1-1&onto 1.2.例： (1)(Z,+),(Z2,+2)为群， 令f(2n)=0,f(2n+1)=1,则f为从(Z,+)到(Z2,+2)的群满同态，但f非同构。 令g(n)=0，则g也为同态但不是满的。
(2)(R,+)为实数加群，(R*,*)为非零实数乘群，令f: R→R*为 f(x)=2x ∵2x+y=2x*2y,∴f为同态，但f不是满的。 (3)令R+为全体正实数，(R+,*)为群，令f: R→R+为f(x)=2x， 则f为从(R,+)到(R+,*)的同构。 1.3.命题：设(G,*),(H,?)为群， (1)令f: G→H，对?x∈G,f(x)=e H,则f为同态。 (2)令a∈G,f a: G→G为f a(x)=axa-1,则f a为自同构。 证明：∵f a(xy)=axya-1=axa-1aya-1=f a(x)f a(y) ∴f a为同态 又∵f a为1-1&onto ∴f a为同构. # 1.4.命题：(Z6,+6)恰有6个自同态，恰有2个自同构。 证明：(1)令f i: Z6→Z6,f I(x)=ix(mod 6)(=ix-[ix/6]*6),i=0,1, (5) ∵f i(x+6y)=i(x+6y)(mod 6)=ix(mod 6)+6iy(mod 6)=f i(x)+6f i(y) ∴f i为同态. ∵f i(1)=i ∴i≠j→f i≠f j,故(Z6,+6)至少有6个自同态。 (2)设f: Z6→Z6为自同态，则若i∈{0,…,5}， 则f(i)=f(1+61+6…+61)=f(1)+6f(1)+6…+6f(1)=if(1)(mod 6),
第 3 讲 §7—9 一一映射，同态及同构（2课时） (Bijection Homomorphism and Osomorphism ) 本讲教学目的和要求：通过了解双射，同态及同构的理论，为后继课程中学习群同态，群同构（群第一、二同构定理）环同态，环同构理论做准备。具体要求： 1、在第一讲的基础上，对各类映射再做深入的研究。 2、充分了解双射（一一映射）的特性以及由此引导出的逆映射。 3、两个代数系统的同态的概念，尤其是同态的满射所具有的性质。 4、掌握同构映射的实质，为以后教学内容奠定基础， 本讲的重点和难点：本讲的重点在于对同态映射定义的了解；由同态满射引导的一系列性质及同构映射本质的掌握。而对双射及自身的逆映射之间的关系学生不易把握，需要认真对待。 本讲的教法和教具：在多媒体教室使用投影仪。在教学活动中安排时间让学生展开讨论。 本讲思考题及作业：本讲思考题将随教学内容而适当地展开。作业布置在本讲结束之后。 一、一一映射 在第1讲中，已对各类映射作了系列性的介绍，这里只对重要的一一映射作重点的讨论。 定义1、设?是集合A到A的映射，且?既是单的又是满的，则称?是一个一
一映射（双射）。 例1：},4,2,0,2,4,{2},2,1,0,1,2,{: --=→--=Z Z ?， 其中Z n n n ∈?=,2)(?，可知?显然是一个双射。 注意：Z 与偶数集Z 2之间存在双射，这表明：Z 与它的一个真子集Z 2一样“大”。 思考题：从例1中得知：一个无限集与其的某个真子集一样“大”。这是否可作为无限集都有的特性？即我们是否有如下的结论：A 为无限集的充要条件是A 与其某个真子集之间存在双射。 定理1：设?是A 到A 的一个双射，那么由?可诱导出（可确定出）A 到A 的一个双射1-?（通常称1-?是?的逆映射） 证明：由于?是A 到A 的双射，那么就A 中任一个元素a ，它在A 中都有逆象a ，并且这个逆象a 是唯一的。利用?的这一特点，则可确定由A 到A 的映射1-?： a a A a A A =∈?→--)(,,:11??，如果a a =)(?，由上述说明，易知1-?是映射。 1-?是满射：A a ∈?，因?是映射a a A a =∈??)(,?使，再由1-?的定义知a a =-)(1?，这恰说明，a 是a 在1-?下的逆象。由a 的任意性，知1-?是满射。 1-?是单射：2121,,a a A a a ≠∈?若由?是满射21a a 及?的逆象分别是 22111121)(,)(,a a a a a a ==--??即及，又?是单射21a a ≠?， 这说明)()(2111a a --≠??，所以1-?是单射。 综合上述讨论知：1-?是A 到A 的一个双射。
同态映射、同态与同构之基本概念的重要性 这两天我又学习了同态映射、同态和同构这三个近世代数中最为基本的概念，由于在学习的时候同态映射跟其他两个概念不是在同一时间学的，所以竟然在小小的一段时间内对三个概念产生了一些误解，尤其是认为同态是同态映射的简称可以说是犯了一个很大的错误。刚刚我在学习同态的概念的时刻，授课的老师特别强调了这一点，我也对老师提出的这一点感到强烈的震惊，才发现自己的自我认为有时并非准确的。再加上，老师在证明同态的两个集合之间运算的结合律的时候又指出了我差一点就犯了的一个很严重的逻辑错误，而且这个错误的发生往往是伴随着对基本概念的掌握不够好。而且在上个学期的时候我在自学数学知识的时候已经明显地感觉到了无论研究什么首要做的事情就是要弄清楚研究对象里的基本概念才能做到有的放矢，在那个时候我也是这样去告诉我的好伙伴的，并且以如何证明两个集合相等这样的一个题目给他展示了掌握基本概念的好处。并且我们这学期的一位任课老师要求我们在课堂上为大家谈一下我们对数字图书馆的一些认识，当时我的第一意识就告诉要借这么一个机会把理解并掌握基本概念对我们学习、工作甚至是生活的重要性来传达给大家，希望对他们的学习生活有些许帮助，虽然因为种种原因我的这个想法可能没有办法实现，但是这许许多多的事情都已经充分在表明我已经开始对基本概念有了很高的重视。今天我写此文的目的也就是在于在弄清楚同态映射、同态和同构这三个概念以及一个定理的证明的同时来阐述体现其中基本概念的重要性，如果基本概念掌握不好就有可能会犯错，而掌握了概念做起事来就能达到事半功倍的效果。 1.基本概念 1.1 同态映射 对于集合A 到-A 映射-→A A :?,以及A 上的一个二元运算 和- A 上的一个二元运算- ，如果A b a ∈?,，都有 a b a = b （即)()()(b a b a ??? =） ，那么我们称?为A 与-A 的同态映射。（注：- A 在近世代数中只是一个普通的集合并非A 的补集，对于)(x ?我们也经常记作x 即x 的象，其他的映射函数也是如此。） 1.2 同态 对于A 上的一个二元运算 和-A 上的一个二元运算- ，如果存在一个满射- →A A :?是A 与-A 关于两种运算的同态映射，那么我们称A 与- A 同态。 1.3 同构 对于A 上的一个二元运算 和-A 上的一个二元运算- ，如果存在一个全射 -→A A :?是A 与-A 关于两种运算的同态映射，那么我们称A 与- A 同构。 由此我们可以看出同态映射跟同态、同构是完全不同的概念，同态映射是说两个集合之间的映射关系，而同态与同构则是直接描述两个集合之间的关系。因此我原来认为同态是同态映射的简称是一种完全错误的想法。 接下来通过关于同态的一个定理来阐述对于基本概念掌握的重要性。 2. 同态定理