Затраты на программу (добавление баллов - формулы удвоения) - PullRequest
Новая
       29

Затраты на программу (добавление баллов - формулы удвоения)

0 голосов
/ 17 мая 2018

В настоящее время я работаю над формулами сложения в протоколе Биткойн, которые можно найти на веб-странице 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)

Мой вопрос таков: когда я теперь вычисляю количество точек в одной точке, сохраняет ли компьютер значение q2: = q [2] ** 2, когда я вычисляю q [2] ** 2, чтобы вычислить q [2] ** 3 стоит только умножение q2 на q [2], или он «забыл» это значение и ему нужно снова его вычислить?
Тогда было бы более эффективно определить заранее квадраты p [2] и q [2], чтобы программа могла считывать предварительно определенные значения без необходимости вычислять их два раза, нет?
И является ли H * H стоимостью возведения в квадрат или умножения точек?

Обычно это добавление к якобиану имеет стоимость: 4S (точечные сечения) + 12M (умножение на точки) + 6a (сложение на точки) + 1 * 2 (умножение на 2).

...