runtime - SageMath中椭圆曲线上一点的求幂速度不合理
问题描述
我正在研究 sagemath 的椭圆曲线。我试图收集 NIST P-256 椭圆曲线上点的组运算和取幂的基准。当我尝试对曲线上的 2 个点执行组操作时,大约需要 2 微秒。当我尝试用随机指数对椭圆曲线中的一个点进行取幂时,只需要 3 微秒。这怎么可能?由于我使用 256 位值求幂,因此这至少需要 256 组操作所需的时间,即超过 0.5 毫秒。我担心我的代码是否错误!
p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
order = 115792089210356248762697446949407573529996955224135760342422259061068512044369
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
F = GF(p)
E = EllipticCurve(F, [-3,b])
runs = 10000
G = E.abelian_group()
F2 = GF(order)
exponent = [F2.random_element() for i in range(runs)]
e2 = [G.random_element() for i in range(runs)]
t1 = time()
for i in range(runs):
e = Integer(exponent[i])*e2[i]
t2 = time()
print "Time per operation = ", (t2 - t1)/runs , " seconds"
e1 = [G.random_element() for i in range(runs)]
e2 = [G.random_element() for i in range(runs)]
t1 = time()
for i in range(runs):
e = e1[i]+e2[i]
t2 = time()
print "Time per operation = ", (t2 - t1)/runs , " seconds"
解决方案
E.abelian_group()
如果您的目标是计算椭圆曲线标量乘法的时间,请不要使用:
sage: P = G.random_element()
sage: P.parent()
Additive abelian group isomorphic to Z/115792089210356248762697446949407573529996955224135760342422259061068512044369 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 115792089210356248762697446949407573530086143415290314195533631308867097853948*x + 41058363725152142129326129780047268409114441015993725554835256314039467401291 over Finite Field of size 115792089210356248762697446949407573530086143415290314195533631308867097853951
sage: P.__class__
<class 'sage.groups.additive_abelian.additive_abelian_wrapper.AdditiveAbelianGroupWrapper_with_category.element_class'>
sage: Q = E.random_element()
sage: Q.parent()
Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 115792089210356248762697446949407573530086143415290314195533631308867097853948*x + 41058363725152142129326129780047268409114441015993725554835256314039467401291 over Finite Field of size 115792089210356248762697446949407573530086143415290314195533631308867097853951
sage: Q.__class__
<class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>
E.abelian_group()
是 的离散对数表示E(_p)
:为组选择一个(或多个)生成器:
sage: G.gens()
((20722840521025081260844746572646324413063607211611059363846436737341554936251 : 92859506829486198345561119925850006904261672023969849576492780649068338418688 : 1),)
点表示为指数向量:
sage: P.vector()
(115792089210356248762697446949407573529996955224135760342422259061068512044368)
因此c*P
只需将指数乘以c
曲线的阶数并以模数形式减少。
用于E.random_element()
获取曲线的点并执行真正的椭圆曲线操作:
sage: c = 2^100
sage: %timeit c*Q
100 loops, best of 3: 3.88 ms per loop
sage: c = 2^1000
sage: %timeit c*Q
10 loops, best of 3: 32.4 ms per loop
sage: c = 2^10000
sage: %timeit c*Q
1 loop, best of 3: 321 ms per loop
推荐阅读
- python - Flask 应用程序:添加条件以检查 html 模板文件中的环境
- javascript - Firebase 身份验证后将用户重定向到特定 URL
- jmeter - (远程JMeter5.4.1):java.rmi.ConnectException:连接拒绝主机:127.0.0.1
- plot - 如何在 TradingView PineScript 中为特定日期时间添加箭头
- java - 使用 DELETE 语句截断不正确的 DOUBLE 值
- lstm - 编码器解码器 LSTM
- python - 如何使用美丽的汤提取此 HTML 数据?
- python - 如何在python中使用平均频率提取心电图特征?
- javascript - Socket.io 无法处理多个客户端 javascript
- floating-point - 无法打印截断值的十六进制