程序成本(加点倍增公式)

2024-04-23 20:22:26 发布

您现在位置:Python中文网/ 问答频道 /正文

我目前正在研究比特币协议中的加法公式,可以在Github网页https://github.com/vbuterin/pybitcointools/blob/aeb0a2bbb8bbfe421432d776c649650eaeb882a5/bitcoin/main.py上找到。我想将它的性能与“素数阶椭圆曲线的完全加法公式”一文中的公式进行比较。因此,我需要计算点加法、平方、乘法和整数运算的数量。(本着[http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html][2]的精神)。
不幸的是,我不是一个很好的有经验的程序员,因为我的背景是数学硕士,几乎没有编程经验。
代码是

def jacobian_add(p, q):
    if not p[1]:
        return q
    if not q[1]:
        return p
    U1 = (p[0] * q[2] ** 2) % P
    U2 = (q[0] * p[2] ** 2) % P
    S1 = (p[1] * q[2] ** 3) % P
    S2 = (q[1] * p[2] ** 3) % P
    if U1 == U2:
        if S1 != S2:
            return (0, 0, 1)
        return jacobian_double(p)
    H = U2 - U1
    R = S2 - S1
    H2 = (H * H) % P
    H3 = (H * H2) % P
    U1H2 = (U1 * H2) % P
    nx = (R ** 2 - H3 - 2 * U1H2) % P
    ny = (R * (U1H2 - nx) - S1 * H3) % P
    nz = (H * p[2] * q[2]) % P
    return (nx, ny, nz)

我的问题是:当我现在计算一个点的平方数时,当我计算q[2]**2时,计算机是否会保护q2:=q[2]**2的值,这样计算q[2]**3只需要q2与q[2]相乘,还是他“忘记”了这个值,需要重新计算?
那么事先定义p[2]和q[2]的平方会更有效,这样程序就可以读出预定义的值,而不需要计算两次,不是吗?
H*H是点平方或点乘法的代价吗?

通常这种雅可比点加法的代价是:4S(点平方)+12M(点乘法)+6a(点加法)+1*2(乘2)。你知道吗


Tags: returnifnoth2经验h3公式nx