Elliptic Curve Discrete Log Solver
Elliptic Curve Discrete Logarithm Solver finds the discrete logarithm \\( k \\) such that \\( Q = kP \\) on an elliptic curve \\( y^2 \equiv x^3 + ax + b \pmod{p} \\). Enter curve parameters (\\( a \\), \\( b \\), prime \\( p \\)), base point \\( P \\), and target point \\( Q \\). Note: For educational purposes only; use small parameters (\\( p < 100 \\)) due to computational limits.
Methodology Used in ECDLP Solver
The Elliptic Curve Discrete Logarithm Problem (ECDLP) involves finding an integer \\( k \\) such that \\( Q = kP \\) for points \\( P \\) and \\( Q \\) on an elliptic curve \\( E: y^2 \equiv x^3 + ax + b \pmod{p} \\). This solver uses the Baby-Step Giant-Step algorithm for small curves.
Algorithm Steps (Baby-Step Giant-Step):
1. Compute the order \\( n \\) of the base point \\( P \\) (number of points in the group generated by \\( P \\)).
2. Set \\( m = \lceil \sqrt{n} \rceil \\).
3. Compute baby steps: \\( \{ (iP, i) \mid i = 0, 1, \ldots, m-1 \} \\).
4. Compute giant steps: \\( \{ Q – jmP \mid j = 0, 1, \ldots, m-1 \} \\).
5. Find a collision between baby steps and giant steps to solve \\( i + jm = k \\).
Mathematical Formulation:
\\[ \text{Given } E: y^2 \equiv x^3 + ax + b \pmod{p}, \text{ points } P, Q \in E(\mathbb{F}_p) \\] \\[ \text{Find } k \text{ such that } Q = kP \\] \\[ \text{Complexity: } O(\sqrt{n}) \text{ group operations, where } n \text{ is the order of } P \\]Note: This solver is for educational purposes and only works for small curves (\\( p < 100 \\)) due to computational limits. Real-world ECDLP is infeasible for large curves.
Example
For curve \\( y^2 \equiv x^3 + 9x + 17 \pmod{23} \\), base point \\( P = (16, 5) \\), target point \\( Q = (4, 5) \\):
Step 1: Compute multiples of \\( P \\):
\\[ P = (16,5), 2P = (20,20), 3P = (14,14), \ldots, 9P = (4,5) = Q \\]Result: \\( k = 9 \\).