1、Q=BAP/2 AP L2可设想L1上有一点P,它为L2和L1的交点,称之为。直线L1上的无穷远点只能有一个。(因为过因为过A点只能有一条平行于点只能有一条平行于L1的直线的直线L2,而两直线的,而两直线的交点只能有一个交点只能有一个。)结论:结论:1*.平面上一组相互平行的直线,有公共的无穷远点。(为与无穷远点相区别,把原来平面上的点叫做)2*.平面上任何相交的两直线L1,L2有不同的无穷远点。原因:若否,则L1和L2有公共的无穷远点P,则过两相异点A和P 有相异两直线,与公理相矛盾。3*.全体无穷远点构成一条无穷远直线无穷远直线。:欧式平面添加上无穷远点和无穷远直线,自然构成射射。(2)齐
2、次坐标齐次坐标 解析几何中引入坐标系,用代数的方法研究欧氏空间。这样的坐标法也可推广至摄影平面上,建立平面摄影平面摄影坐标系坐标系。平面上两相异直线L1,L2,其方程分别为:L1:a1x+b1y+c1=0 L2:a2x+b2y+c2=0AL1L2P其中a1,b1不同时为0;a2,b2也不同时为0。设 D=a1 b1 Dx=b1 c1 Dy=c1 a1 a2 b2 b2 c2 c2 a2若D0,则两直线L1,L2相交于一平常点P(x,y),其坐标为x=Dx/D,y=Dy/D.这组解可表为:x/Dx=y/Dy=1/D(约定:分母分母Dx,Dy有为有为0时,对应的分子也要为时,对应的分子也要为0)上
3、述表示可抽象为(Dx,Dy,D).若 D=0,则L1L2,此时L1和L2交于一个无穷远点P。这个点P可用过原点O且平行于L2的一条直线L来指出他的方向,而这条直线L的方程就是:a2x+b2y=0.为把平常点和无穷远点的坐标统一起来,把点的坐标用(X,Y,Z)表示,X,Y,Z不能同时为0,且对平常点(x,y)来说,有Z0,x=X/Z,y=Y/Z,于是有:i.e.X/Dx=Y/Dy=Z/D,有更好的坐标抽象,X,Y,Z),这样对于无穷远点则有Z=0,也成立。注:注:a).若实数p0,则(pX,pY,pZ)与(X,Y,Z)表示同一个点。实质上用(X:Y:Z)表示。3个分量中,只有两个是独立的,具有这
4、种特征的坐标就叫。i.e.DDZYDZXyx1b).设有欧氏直线L,它在平面直角坐标系Oxy上的方程为:则L上任一平常点(x,y)的齐次坐标为(X,Y,Z),代入得:给L添加的无穷远点的坐标(X,Y,Z)应满足;平面上无穷远直线方程自然为:!(3)任意域上的椭圆曲线任意域上的椭圆曲线K为域,K上的摄影平面P2(K)是一些等价类的集合(X:Y:Z)。考虑下面的Weierstrass方程(次数为3的齐次方程):Y2Z+a1XYZ+a3YZ2=X3+a2X2z+a4XZ2+a6Z3(其中系数aiK,或aiK为K的代数闭域)Weierstrass方程被称为光滑的或非奇异的是指对所有适合以下方程的射影点
5、P=(X:Y:Z)P2(K)来说,F(X,Y,Z)=Y2Z+a1XYZ+a3YZ2-X3-a2X2Z-a4XZ2-a6Z3=0在P点的三个偏导数 之中至少有一个不为 0若否称这个方程为奇异的。的定义:椭圆曲线E是一个光滑的Weierstrass方程在P2(K)中的全部解集合。Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3注:注:a)在椭圆曲线E上恰有一个点,称之为无穷远点。即(0:1:0)用表示。ZFYFXF,b)可用非齐次坐标非齐次坐标的形式来表示椭圆曲线的Weierstrass方程:设 x=X/Z,y=Y/Z,于是原方程转化为:y2+a1xy+a3y=x3+a2x2
6、+a4x+a6 (1)此时,椭圆曲线E就是方程(1)在射影平面P2(K)上的全部平常点解,外加一个无穷远点组成的集合。c)若a1,a2,a2,a4,a6K,此时椭圆曲线E被称为定义在K上,用E/K表示。如果E能被限定在K上,那么E的K有理点集合表示为E(K),它为E中的全体有理坐标点的集合外加无穷远点.(4)实域实域R上的椭圆曲线上的椭圆曲线 设K=R,此时的椭圆曲线可表为平面上的通常曲线上的点,外加无穷远点。:设L P2(R)为一条直线。因为E的方程是三次的,所以L可与E在P2(R)恰有三个交点,记为P,Q,R(注意注意:如果L与E相切,那么P,Q,R可以不是相异的)。按下述方式定义E上运算
7、:设P,Q E,L为联接P,Q的直线(若P=Q,则L取过P点的切线);设R为L与E的另一个交点;再取连接R与无穷远点的直线L。则L与E的另一个交点定义为P Q。PQP=QLLLL(P Q)R=T T=(P=Q=R)P QP QRRT 上页的实际图像为椭圆曲线y2=x3-x的一般化。来自对具体曲线的抽象。对运算更具体一些:设 P=(x1,y1),Q=(x2,y2),P Q=(x3,y3),由P Q的定义,设y=x+为通过P,Q两点直线L的方程,可算出:=(y2-y1)/(x2-x1),=y1-x1 易见,直线L上的一个点(x,x+)是在椭圆曲线E上,当且仅当(x+)2=x3 x。P Q=(x1,
8、y1)(x2,y2)=(x3,y3)=(x3,-(x3+)其中,x3=2-x1-x2=(y2-y1)/(x2-x1)2-x1-x2;y3=-y1+(y2-y1)/(x2-x1)(x1-x3)当P=Q时:P Q=(x3,y3)算得:x3=(3x12-1)/2y1)2-2x1;y3=-y1+(3x12-1)/2y1)(x1-x3)注:注:a)如果直线L与E相交与三点P,Q,R(不一定相异),那么(P Q)R=(从图中可见)。b)任给PE,P =P (此时设Q=,易见L=L)c)任给P,QE有:P Q=Q Pd)设PE,那么可以找到-PE使P -P=e)任给P,Q,RE,有(P Q)R=P (Q R
9、)综上所述,知E对 运算形成一个Abel群。f)上述规则可开拓到任意域上,特别是有限域上。假定 椭圆曲线是定义在有限域Fq上(q=pm),那么 E(Fq)=(x,y)FqFq|y2+a1xy+a3y=x3+a2x2+a4x+a6 它对“”形成一个群,为Abel群。2 有限域上椭圆曲线的有限域上椭圆曲线的 运算运算 令Fq表示q个元素的有限域,用E(Fq)表示定义在Fq上的一个椭圆曲线E。(1)Fp(素域,(素域,p为素数)上椭圆曲线为素数)上椭圆曲线 令p3,a,bFp,满足4a3+27b20,由参数a和b定义的Fp上的一个椭圆曲线方程为:y2=x3+ax+b (2)它的所有解(x,y),(x
10、Fp,yFp),连同一个称为“无穷远点”(记为)的元素组成的集合记为E(Fp),由Hass定理知:知:p+1-2p1/2#E(Fp)p+1+2p1/2 集合E(Fp)对应下面的加法规则,且对加法 形成一个Abel群:(i)=(单位元素)(ii)(x,y)=(x,y),任给(x,y)E(Fp)(iii)(x,y)(x,-y)=,任给(x,y)E(Fp),即点(x,y)的逆元 为(x,-y).(iv)令(x1,y1),(x2,y2)为E(Fp)中非互逆元,则 (x1,y1)(x2,y2)=(x3,y3),其中 x3=2-2x1,y3=(x1-x3)-y1 且=(y2-y1)/(x2-x1)(3)(
11、v)(倍点运算规则)设(x1,y1)E(Fp),y10,则2(x1,y1)=(x3,y3),其中 x3=2-2x1,y3=(x1-x3)-y1 这里=(3x12+a)/(2y1)(4)注:注:若#E(Fp)=p+1,曲线E(Fp)称为超奇异的超奇异的,否则称为 非超奇异的非超奇异的。例子例子:F23上的一个椭圆曲线上的一个椭圆曲线 令y2=x3+x+1是F23上的一个方程(a=b=1),则该椭圆曲线方程在F23上的解为(y2=x3+x+1的点):(0,1),(0,22),(1,7),(1,16),(3,10),(3,13),(4,0),(5,4),(5,19),(6,4),(6,19),(7,
12、11),(7,12),(9,7),(9,16),(11,3),(11,20),(12,4),(12,19),(13,7),(13,16),(17,3),(17,20),(18,3),(18,20),(19,5),(19,18);。群E(F23)有28个点(包括无穷远点)。(2)F2m上的椭圆曲线上的椭圆曲线 F2m上由参数a,bF2m,b0定义的一个非超奇异椭圆曲线E(F2m)是方程 y2+xy=x3+ax2+b (5)的解集合(x,y),其中x,yF2m,连同。(i)+=(ii)任给(x,y)E(F2m),则(x,y)=(x,y)(iii)任给(x,y)E(F2m),则(x,y)+(x,x+
13、y)=,即点(x,y)的逆为(x,x+y).(iv)两个相异且不互逆的点的加法规则:令(x1,y1),(x2,y2)E(F2m)且有x1x2则 (x1,y1)(x2,y2)=(x3,y3),其中 x3=2+x1+x2+a;y3=(x1+x3)+x3+y1.其中 =(y2+y1)/(x2+x1)(v)倍点规则令(x1,y1)E(F2m),其中x10。则 2(x1,y1)=(x3,y3),其中 x3=2+a,y3=x12+(+1)x3,这里=(x1+y1/x1)易见,群E(F2m)为Abel群。例:例:F24上的一个椭圆曲线上的一个椭圆曲线f(x)=x4+x+1为F2上的一个不可约多项式,易见 F
14、24=F2x/(f(x)=(k0,k1,k2,k3)|(k0,k1,k2,k3)=k0+k1+k22+k33,为为f(x)的零点,的零点,kiF2假定F24上的非超奇异椭圆曲线有下述方程定义:y2+xy=x3+4x2+1,注意注意f()=0。方程应表为:(1000)y2+(1000)xy=(1000)x3+(1100)x2+(1000)3 椭圆曲线密码体制椭圆曲线密码体制 1985年,N.Koblitz和V.Miller分别独立提出了椭圆曲线密码体制(ECC),其依据就是定义在椭圆曲线点群定义在椭圆曲线点群上的离散对数问题的难解性上的离散对数问题的难解性。(1)知)知E(Fq)对点的对点的“”
15、运算形成一个运算形成一个Abel群群设pE(Fq),若p的周期很大,即使 p p p=(共有 t个p相加)成立的最小正整数 t,希望 t 很大。(t=p的周期,表示为(p)=t)。并且对QE(Fq),定有某个正整数m使 Q=mp=p p (共有t个p相加)定义 m=pQ (m为以p为底Q的对数)。椭圆曲线上的点形成的群E(Fq),相关它的离散对数问题是难处理的。(2)建立椭圆曲线密码体制建立椭圆曲线密码体制 选取基域Fq,Fq的椭圆曲线具体给定为确定的形式。在E(Fq)中选一个周期很大的点,如选了一个点P=(xp,yp),它的周期为一个大的素数n,记(P)=n(素数)。注意:注意:在这个密码体
16、制中,具体的曲线及点P和它的n都是公开信息。密码体制的形式采用EIGamal体制,是完全类比过来。Bob(使用者)执行了下列计算:i)在区间1,n-1中随机选取一个整数d。ii)计算点Q:=dP(d个P相)iii)Bob公开自己的公开密钥 (E(Fq),p,n,Q)iv)Bob的私钥为整数d!Alice要发送消息要发送消息m给给Bob,Alice执行执行:i)查找Bob的公钥(E(Fq),p,n,Q),ii)将m表示成一个域元素mFq,iii)在区间1,n-1内选取一个随机数k,iv)依据Bob的公钥计算点(x1,y1):=kP(k个P相 )v)计算点(x2,y2):=kQ,如果x2=0,则回到第iii)步.精品课件精品课件!精品课件精品课件!)计算C:=mx2)传送加密数据(x1,y1,C)给BobBob收到Alice的密文(x1,y1,C)后,执行 i)使用私钥d,计算点(x2,y2):=d(x1,y1),再计算Fq中x2-1=?Ii)通过计算m:=Cx2-1,恢复出明文数据m。