【www.shanpow.com--数学试题】
篇一:[椭圆曲线]椭圆曲线入门详解
转载请注明http://blog.csdn.net/boksic 如有疑问欢迎留言
如果不知道数学上的群、循环群等概念，可以先了解ElGamal加密算法 后再回过来椭圆曲线加密
这两个算法有共通之处，都是在离散问题难解群上的加密算法，椭圆曲线是进一步的加深
首先，什么是椭圆曲线
椭圆曲线(Elliptic curve)
叫椭圆曲线只是因为方程跟椭圆的曲线积分比较相似
椭圆曲线方程可以统一为
当然还有要求
至于长什么样，绘个图看看
用matlab写了一个模拟程序，可以控制a,b变化，显示曲线的图像。
[cpp] view plain copy
clear;clc;figure(1);
a=0;
b=0;
h_text1=uicontrol("Style","text","String","a","Position",[50 20 50 20]);
h_text1=uicontrol("Style","text","String","b","Position",[50 0 50 20]);
ezplot(strcat("x+",num2str(a),"*y"));
h_slider1=uicontrol("Style","slider","Position",[100 20 200 20],...
"Max",10,"Min",-10,"callback",["a=num2str(get(gcbo,""value""));",...
"ezplot(strcat(num2str(b),""+x^3+"",num2str(a),""*x-y^2""))"]);
%h_text2=uicontrol("Style","text","String","b");
h_slider2=uicontrol("Style","slider","Position",[100 0 200 20],...
"Max",10,"Min",-10,"callback",["b=num2str(get(gcbo,""value""));",...
"ezplot(strcat(num2str(b),""+x^3+"",num2str(a),""*x-y^2""))"]);
再直观一点
（不得不说在这方面，Mathematica比Matlab要方便强力太多，用MATLAB做这个图像速度慢代码长步骤复杂效果烂）
b=0,a在[-20,20]上变动时的图像
a=-6,b在[-20,20]上变动时的图像
Plot3D[{(x^3+y*x)^0.5,-(x^3+y*x)^0.5},{x,-7,7},{y,-20,20}]
Plot3D[{(x^3-6x+y)^0.5,-(x^3-6x+y)^0.5},{x,-7,7},{y,20,-20}]
"受ElGamal密码启发，在其它离散对数问题难解的群中，同样可以构成ELGamal密码。于是人们开始寻找其它离散问题难解的群。研究发现，有限域GF（p）上的椭圆曲线的解点构成交换群，而且离散对数问题是难解的。于是可在此群上建立ELGamal密码，并称为椭圆曲线密码。"
解点交换群
为了构成加法交换群，需要定义元素、单位元、逆元素、加法
解点
设p是大于3的素数，且4a3+27b2 ≠0 mod p ，称
y^2 =x^3 +ax+b ，a,b∈GF(p)
为GF（p）上的椭圆曲线。
由椭圆曲线可得到一个同余方程：
y^2 =x^3 +ax+b mod p
其解为一个二元组<x,y>，x,y∈GF(p)，将此二元组描画到椭圆曲线上便为一个点，于是又称其为解点。
单位元
引进一个无穷点O（∞,∞），简记为0，作为0元素。
O（∞,∞）＋O（∞,∞）＝0＋0＝0 。
并定义对于所有的解点P（x ，y）有
P（x ,y）+O＝O+ P（x ,y）＝P（x ,y）
逆元素
任何解点R（x ,y）的逆就是 R（x ,-y）。
加法P（x1 ，y1）＋Q（x2 ，y2）＝R（x3 ，y3）
(提醒一下，这里的运算都是模运算，值都是整数，像除法是模逆运算)
定义s = (yP ? yQ)/(xP ?xQ)，即PQ线的斜率
总共3种情况
1.一般情况下 R = P + Q = (xR, ? yR)其中
2.如果xP = xQ,yP = ?yQ(包括yP =yQ = 0的情形)
结果R就是无穷远点0
3 尽管xP = xQ但yP = yQ ≠ 0那么R =P +P = 2P = (xR,?yR)有
加法的几何意义
设P和Q是椭圆曲线的两个点，则连接P和Q的直线与椭圆曲线的另一交点关于横轴的对称点即为R点。在该群中P + Q + R = 0
椭圆曲线交换群实例
对于标准方程y^2=x^3+ax+b (mod p) 设定基本参数
p=31,a=2,b=17
随便找一个在曲线上(即满足该方程)的点P=(10,13)
然后按照上面提到的公式来逐一计算2P,3P,4P.....
我用的Python来计算（调用的mod_inv是模下的除运算，代码可参看前面的文章）:
[python] view plain copy
px,py=10,13
x,y=px,py
a,b=2,17
p=31
for i in range(p+20):
if(x==px and y==py):
x3=(9*x**4-8*x*y**2+6*a*x**2+a**2)\
*mod_inv(4*y**2,p)%p
y3=((3*x**2+a)*(x-x3)*mod_inv(2*y,p)-y)%p
elif(x==px):
x3,y3=0,0
elif(x==0 and y==0):
x3,y3=px,py
else:
x3=(((y-py)*mod_inv(x-px,p))**2-x-px)%p
y3=((y-py)*(px-x3)*mod_inv(x-px,p)-py)%p
str = "%dP= (%d,%d)"%(i+2,x3,y3)
print str,
x,y=x3,y3
可以得到
[plain] view plain copy
2P= (21,19) 3P= (19,30) 4P= (27,10)
5P= (29,25) 6P= (24,1) 7P= (30,13)
8P= (22,18) 9P= (8,24) 10P= (20,11)
11P= (6,11) 12P= (23,27) 13P= (12,23)
14P= (3,22) 15P= (7,23) 16P= (1,19)
17P= (17,2) 18P= (9,12) 19P= (13,15)
20P= (5,11) 21P= (5,20) 22P= (13,16)
23P= (9,19) 24P= (17,29) 25P= (1,12)
26P= (7,8) 27P= (3,9) 28P= (12,8)
29P= (23,4) 30P= (6,20) 31P= (20,20)
32P= (8,7) 33P= (22,13) 34P= (30,18)
35P= (24,30) 36P= (29,6) 37P= (27,21)
38P= (19,1) 39P= (21,12) 40P= (10,18)
41P= (0,0) 42P= (10,13)
matlab显示一下，点的分布与顺序都是杂乱无章
篇二:[椭圆曲线]椭圆曲线：浅谈比特币的数学原理
作者，顾险峰，美国纽约州立大学石溪分校计算机系终身教授。
本文转自微信公众号老顾谈几何(conformalgeometry)
关注微信：哆嗒数学网 每天获得更多数学趣文
新浪微博：http://weibo.com/duodaa
2017年即将逝去，人类对于科技再度狂热，但是狂热所引发的思潮却指向了截然不同的方向。
一个爆炸性的突破是引力波被实验证实，从而验证了爱因斯坦广义相对论的预言。数十年前，韦伯的引力波实验就已经家喻户晓，但是其宣布的几次探测到的引力波没有得到世间公认。韦伯的历史角色一直在科学殉道者和江湖郎中之间徘徊。这次引力波探测成功，无疑将韦伯定义为历史先驱，使得他多舛的命运被赋予上悲剧英雄的色彩；同时，这也宣示着人类理性思维的巨大成功。爱因斯坦广义相对论的建立遵循了经典理论研究途径，从公理体系的建立，到严格数学推理，直至精确物理预言，最后由实验检验；数学推理中抽象的黎曼几何超越了人类直觉，真正指导爱因斯坦建立恢弘体系的是对理论体系内在和谐性的审美。
另一个颠覆性的进展是人工智能，特别是机器学习的热潮。特别是阿法狗和人类的对决，一方面令无数人欢欣鼓舞，狂热亢奋，另一方面也令人颤栗恐惧，迷茫绝望。柯洁的嚎啕大哭，令无数人心碎：人类苦心孤诣，皓首穷经，积累了数千年的经验，被机器瞬间超越，进而遗弃。这不仅令职业棋手心生幻灭，更令无数学者心生疑虑，对于自然界真理的追求是否真正具有崇高意义，还是人类为了虚荣而自欺欺人？这种思潮已经在大学校园之中泛滥开来，以往计算机科学专业的年轻人会花费大量的时间和经历学习经典数学理论，泛函分析、微分几何、偏微分方程、随机过程等等都是他们知识结构中不可或缺的组成部分；这几年来，机器学习的知识技巧铺天盖地而来，所有的学生每天都被各种学术广告所冲击，眼花缭乱、难以适从，终日处于被时代抛弃的焦虑之中。经过数年的学术训练后，依然无法对于问题进行数学建模、理论分析，取而代之的是“端到端”的训练技巧。这种基于经验统计的“炼金术”是否最终会被严格理论所阐发和提炼，目前仁者见，仁智者见智。静待泡沫散去，时光自会蒸馏出醇酒。
第三个狂潮却饶有兴味，比特币和区块链。年末比特币市场日趋狂热，日益脱离数字货币的初心，沦为豪赌的工具。虽然人类对于金钱的追求日益非理性，但是中本聪设计的比特币网络协议却是基于人类理性的假设。人类历史上，金融交易系统都是建立在信任基础之上的，一直存在可信赖的中心机构来认证个人拥有的财富值，来认证每笔交易的正确性。而比特币却颠覆了这两点：比特币系统不需要信任机构作为中心；比特币系统具有不可追踪性，无法从账户地址推断所有者。这种数字货币系统是基于如下的两个理性假设：首先，比特币网络上“好人”永远多于“坏人”；其次，基于椭圆曲线的加密算法是安全的，无法被轻易破解。
椭圆曲线理论的兴起得益于费马大定理（Fermat"s Last Theorem）的证明。费马猜测方程当n大于2时，不存在整数解。这一猜测犹如万丈绝壁，横亘在数论发展的历史道路上长达三百余年。最关键的突破来自于椭圆曲线。谷山丰提出的谷山-志村猜测建立了椭圆曲线和模形式（某种周期性全纯函数）之间的重要联系。谷山丰虽然洞察到了天机，但是无法证明，三十出头蹈海而逝，其新婚的妻子也殉情自杀。后来，安德鲁.怀尔斯（Andrew Wiles）证明了谷山-志村猜测的一部分，从而证明了费马大定理。费马定理的证明自然是人类思想史上的丰碑，谷山为数学殉道，终成千古绝唱；怀尔斯数十年如一日痴心追梦，令人景仰。但是，在那时，无人会预料费马定理证明所孕育的椭圆曲线理论会有一日成为比特币网络的基础；现如今，比特币、区块链如火如荼，抽象的代数几何理论已经成为无数比特币持有者在街头巷尾的谈资。纯粹数学以令人难以想象的方式颠覆着传统金融体系。
老顾一直倾向于认为中本聪是出于对谷山丰的致敬而发明了比特币协议。谷山壮志难酬而慷慨蹈海，中本聪为之扼腕痛惜，发愤将谷山的椭圆曲线理论在金融领域发挥得淋漓尽致，让整个人类为之痴狂。这两种截然不同的狂悖，终于在2017年底达到了病态的巅峰。
数学上愈是艰深的理论，转换成算法愈是难以破解，因此也是愈发安全。在有限域上，椭圆曲线所定义的代数簇（解的点集）是一个有限的离散点集。每条椭圆曲线和直线有三个交点，我们将其理解为三个点之和为0，如此在代数簇上定义了一个群结构。在这个群中，我们可以构造一些容易检验但是难以求解的问题，所谓单向函数，例如离散对数。这些单向函数用于数字签名，使得用户容易验证，但是无法伪造，由此构成了比特币协议的基础。数学上，对于椭圆曲线群结构的理解，对于比特币系统至关重要。这个群结构的特性越多，自然越容易破解。这里，我们简述一些众所周知的基本理论。如果我们固定一条椭圆曲线，变换数域，那么我们可以在相应的群之间建立同态，通过这些同态，我们可以降低破解难度。这是代数几何所特有的一种手法，优雅有力，富于美感。
椭圆曲线的加法群
椭圆曲线具有形式 ，多项式方程有相异根的充要条件是非零。我们考察代数簇
，
这里是无穷远点。
图1. 椭圆曲线上的加法。
如图1所示，我们考虑定义在实数域上的一条椭圆曲线，它和过点P，Q的直线交于第三个点R，过R做铅直线，铅直线和椭圆曲线交于第四个点。第四个点和R互反，记为。那么，我们定义加法 。经过简单代数运算，我们得到如此定义的加法使得椭圆曲线上所有的点构成一个加法群，无穷远点为单位元。
图2. 椭圆曲线上的乘法。
图2显示了椭圆曲线上的乘法。如果我们过点G做切线，切线交椭圆曲线于-2G，经过反射得到2G。如此，我们可以定义4G，8G等等。
以上的几何运算可以直接转换成代数运算。令，过两点的直线为，这里
,
那么。由此，我们看到如果椭圆曲线的系数A和B在某个域K中，的坐标也在域K中，那么和的坐标也在域K中。由此，庞加莱（Poincare）证明了实数域上椭圆曲线E(R)上所有坐标在K中的点E(K)（并上无穷远点）构成子群。
当我们变换椭圆曲线的域从实数域变成其他域时，我们依然遵照代数法则定义加法，椭圆曲线上的点依然成群。
复数域上的椭圆曲线-黎曼面
如果椭圆曲线的域为复数域，那么椭圆曲线的代数簇构成一张黎曼面，亏格为一的拓扑轮胎。首先我们定义一个格点，
,
那么轮胎是商空间。
图4. 复数域上的椭圆曲线。
我们定义威尔斯特拉斯p-函数，（Weierstrass p-function），
那么我们令
,
则。这里威尔斯特拉斯p-函数是双周期函数，满足周期性条件
。
这时，椭圆曲线群的结构为，即为拓扑轮胎。我们固定一个大于1的正整数N，定义子群
,
即椭圆曲线上所有秩可以整除N的点构成的子群。那么这个子群是两个循环子群的乘积。
有理数域上的椭圆曲线
如果椭圆曲线的域为有理数域，具有无穷多个点。Mordell于1922年证明了是有限生成的群，存在有限点集，任意一个点可以被表示为
，
更进一步，，这里是椭圆曲线的有限阶挠子群，r被称为是椭圆曲线的秩（rank）。1977年，Mazur证明了椭圆曲线的挠子群只有15种情况，和。但是椭圆曲线的秩却依然神秘，人们猜测对于任意大的r，都存在有理数域上的一条椭圆曲线，其秩等于r。这一点在有限域上的椭圆曲线中得以验证，对于任意大的正整数，都存在相应有限域上的椭圆曲线。
有限域上的椭圆曲线
令p是一个正整数，是模p的整数域。一条椭圆曲线，满足，其代数簇是离散点集，如图5所示，同一条椭圆曲线在不同的有限域上，其代数簇包含不同数目的离散点。
图5. 同一条椭圆曲线，在不同的有限域上具有不同数目的离散点。
Hasse在1922年证明了有限域上椭圆曲线代数簇点的个数和（p 1）的差不大于p的平方根的两倍 ：。特别的，如果p为2的指数，即所谓的Koblitz曲线，那么
。
令椭圆线E是定义在一个有限域上，，，令S和T是椭圆曲线上的两个点，找到整数m使得，这一问题被称为是离散对数问题。目前求解离散对数最为有效的是Pollar方法，其算法复杂度为，为k的指数级复杂度。比特币协议中数字签名的安全性就是离散对数问题的指数级复杂度。
一般而言，如果椭圆曲线群具有更加丰富的结构，那么离散对数问题的难度会被降低。数学上的常用手法是将有限域变换成另外一个域，尤其是有理数域，从而建立两个椭圆曲线群之间的同态，并且在特定情况下，同态可以被增强为同构。具体而言，固定一个有理数域上椭圆曲线E(Q)，将其系数模p，我们把它映射到有限域上的椭圆曲线E(Fp),每个E(Q)上的点P(x,y)被映射到E(Fp)上的点，假设x=a/b，那么。这一映射被称为是 Reduction Modulo p Map。如果E(Fp)非退化，那么这一映射给出群E(Q)和E(Fp)之间的同态。至关重要的是，如果我们选定一个正整数N，和p彼此互素，那么Reduction Modulo p Map是 之间的同构。这个定理的重要性，无论怎么强调都不会为过。例如假设我们在有限域的椭圆曲线上E(Fp)求解离散对数问题，通过这个Reduction Modulo p Map将E(Fp) 提升到有理数域的椭圆曲线E(Q)上，如果我们能够在E(Q)上找到对应点之间的代数关系，然后再投射回E(Fp)上，就可以减小求解难度。
这种变换代数曲线基本数域的方法非常优雅，本质上如果用有限域，我们得到的是数论问题，如果我们用复数域，我们得到的是黎曼面的复几何问题。如此，我们将数论问题几何化。例如，著名的椭圆曲线L序列问题，就是数论和代数几何的交叉点。令E是一个固定的椭圆曲线，其系数A，B为整数。对任意一个素数p，我们将E映射到模p域上，得到椭圆曲线E(Fp)，我们定义E(Fp)的迹为， 著名的L-序列(L-series) 将所有的迹编码至一个函数
,
Wile证明L(E,s）可以解析延拓到整个复平面上。s=1是L(E,s)的零点，著名的Brich-Swinnerton-Dyer猜测是说这一零点的指标，等于有理域上曲线E(Q)的生成元的个数。最近，华裔数学新星恽之玮和张伟赢得了2018数学“新视野奖”，这一大奖由谷歌创始人、FaceBook创始人、俄罗斯富翁米尔纳夫妇和马化腾等共同捐赠。他们的工作就是为L函数的泰勒展开的高阶项提供了几何解释。
小结
椭圆曲线连接着代数几何和数论，蕴含着自然的天机，其博大精深令无数的数学家心醉神迷，一往情深。从谷山丰的慷慨悲歌、到威尔斯的英雄史诗，再到中本聪的妙手神算， 从数学圣坛上的抽象理论到金融市场的数字货币，从数学家为自然真理的决绝殉道，到芸芸众生贪婪癫狂的拜金主义，这一切方向都是狂悖混乱，截然相反，却又顺理成章，天衣无缝。历史的发展总是超出想象，颠覆一切，却又天道循环，生生不息。我们深信， 人性中对真理的追求和对金钱的追求，亘古不变：会有更多的青年才俊，为追寻自然真理而苦心孤诣，呕心沥血；也会有更多的金融高手，闪转腾挪，翻手云雨。依随椭圆曲线理论的进一步突破，更多的金融创新会再度横空出世。
篇三:[椭圆曲线]ECC椭圆曲线详解(有具体实例)
前言
ECC英文全称"Ellipse Curve Cryptography"
与传统的基于大质数因子分解困难性的加密方法不同，ECC通过椭圆曲线方程式的性质产生密钥
ECC164位的密钥产生一个安全级，相当于RSA 1024位密钥提供的保密强度，而且计算量较小，处理速度更快，存储空间和传输带宽占用较少。目前我国居民二代身份证正在使用 256 位的椭圆曲线密码，虚拟货币比特币也选择ECC作为加密算法。
从射影平面讲起
古希腊数学家欧几里得的《几何原本》提出了五条公设。
1.由任意一点到任意一点可作直线。
2.一条有限直线可以继续延长。
3.以任意点为心及任意的距离可以画圆。
4.凡直角都相等。
5.同一平面内一条直线a和另外两条直线b.c相交，若在a某一侧的两个内角的和小于两直角，则b.c两直线经无限延长后在该侧相交。
《几何原本》只有在第29个命题
一条直线与两条平行直线相交,则所成的内错角相等,同位角相等,且同旁内角之和等于两直角
中才用到第五公设，即《几何原本》中可不依靠第五公设而推出前28命题。因此，一些数学家提出，第五公设能不能不作为公设，而作为定理？能不能依靠前四个公设来证明第五公设？这就是几何发展史上最著名的，争论了长达两千多年的关于“平行线理论”的讨论
1820年代，俄国喀山大学罗巴切夫斯基用“至少可以找到两条相异的直线，且都通过P点，并不与直线R相交”代替第五公设，然后与欧氏几何的前四个公设结合成一个公理系统，他经过细致深入的推理过程中，得出了一个又一个在直觉上匪夷所思，但在逻辑上毫无矛盾的几何体系。
这种几何学被称为罗巴切夫斯基几何，简称罗氏几何。从罗氏几何学中，可以得出这样一个结论：逻辑上不矛盾的一些公理都有可能提供一种几何学。现存非欧几何的类型可以概括如下：
1.坚持第五公设，引出欧几里得几何。
2.“可以引最少两条平行线”为公设，罗氏几何（双曲几何）。
3.“一条平行线也不能引”为公设，黎曼几何（椭圆几何）
左：双曲几何，即罗氏几何；中：欧几里德几何；右：椭圆几何，即黎曼几何
了解非欧式几何，就可以理解平行线的交点。
定义平行线相交于无穷远点P∞，使平面上所有直线都统一为有唯一的交点
性质：
1.一条直线只有一个无穷远点；一对平行线有公共的无穷远点
2.任何两条不平行的直线有不同的无穷远点（否则会造成有两个交点）
3.平面上全体无穷远点构成一条无穷远直线
射影平面：平面上全体无穷远点与全体平常点构成射影平面
射影平面点的定义
对普通平面上点(x,y)，令x=X/Z，y=Y/Z，Z≠0，则投影为射影平面上的点(X:Y:Z)
求点（1,2）在新的坐标体系下的坐标
∵X/Z=1 ，Y/Z=2（Z≠0）
∴X=Z，Y=2Z ∴坐标为（Z:2Z:Z），Z≠0
即（1:2:1）（2:4:2）（1.2:2.4:1.2）等形如（Z:2Z:Z），Z≠0的坐标都是（1,2）在新的坐标体系下的坐标
(2) 求平行线L1：X+2Y+3Z=0 与L2：X+2Y+Z=0 相交的无穷远点
∵ L1∥L2 所以有Z=0， X+2Y=0
∴坐标为（-2Y:Y:0），Y≠0
即（-2:1:0）（-4:2:0）（-2.4:1.2:0）等形如（-2Y:Y:0），Y≠0
椭圆曲线
一条椭圆曲线是在射影平面上满足威尔斯特拉斯方程（Weierstrass）所有点的集合
Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3
