Более эффективный алгоритм ECDLP

[username1565]

Привет. Вот что я нашёл: https://catalog.lib.kyushu-u.ac.jp/opac_download_md/1434304/p145.pdf Субэкспоненциальный алгоритм, вроде как. Можешь запрограммировать его?

[username1565]

Nice your translated article here: https://habr.com/ru/post/335906/

Wanted to add next...

1. Baby-step-giant-step can working with k points in memory, and m=n/k iterations, because for Q=d*P each d can be writted as k*m+x, where x∈[0, k], k - number of points after baby-steps, m - multiplier for brute-force. When k = √n, then m = n/k = n/(√n) = √n, so O(√n) for Baby-step-giant-step. But, k can be lesser, and searching m=n/k in range [0, m] can be parallelized, using specified diapasons.

2. For Pollard-rho algorithm Brent method is faster than Floyd by 30-40 percent. Also, there is birthday paradox.

3. Points can be subtracted and divided. Q - P = Q + (-P), where -P is additive inverse of P. P(x, y) = -P(x, (-y mod p)) Q/2 = Q * modular_multiplicative_inverse(2, n) Q/k = Q * modular_multiplicative_inverse(k, n)

4. When odd point divided at 2, then the result there is in the second semigroup of the group the points on elliptic curve in finite field. Maybe, if the semigroup can be generated, and point exitsting there can be verified, then it will be possible to determine uniquely the parity of d, and the coefficients for all another points, and if Q = d*P, and d is even, then Q/2, else if d is odd - (Q-P)/2, and check parity of result again and again, and extract bits of d.