<p>In Sage.</p>

<p>Let's first define a finite field of size 2^32 (over which exhaustively searching would be painful but doable, but Pollard-Rho should be pretty fast).</p>

<pre><code>sage F = GF(2^32 - 5)
</code></pre>

<p>And a prime-ordered elliptic curve over it (y^2 = x^3 + x + 13 happens to be prime)</p>

<pre><code>sage: E = EllipticCurve(F, [1, 13])
</code></pre>

<p>Let's call the order of the curve <code>n</code>:</p>

<pre><code>sage: n = E.order()
sage: n
4295040499
sage: n.is_prime()
True
</code></pre>

<p>Let's pick an arbitrary generator on that curve:</p>

<pre><code>sage: G = E.gen(0)
sage: G
(4022957561 : 1193765470 : 1)
sage: G.order() == n
True
</code></pre>

<p>Now let's pick a random multiple of that generator:</p>

<pre><code>sage: import random
sage: x = random.randrange(n)
sage: x
1334636724
sage: P = x * G
sage: P
(2051230087 : 1391923842 : 1)
</code></pre>

<p>And to find the discrete logarithm, simply use:</p>

<pre><code>sage: discrete_log(P, G, n, operation='+')
1334636724
</code></pre>

<p>The same as our random secret multiplier x.</p>

<p>Sage uses Pollard-Rho and other algorithms internally.</p>

CC BY-SA 4.0
2019-07-04T19:34:18.957Z
Thank you but I am looking for generating a small secret multiplier over the standard  secp256k1 curve parameters. Here is an example for `E=EllipticCurve(GF(modi), [0,7])` using the standard NIST (G=E) parameters. We know that for `P=E(69335761065767984070318781108127416310968753866933119760392423089576366173459, 113425617697416972613102767146321902225172329004525144463444008550345431352693)` when calculating `discrete_log(P, G, n, operation='+')` we get the small `x=24734216105351567` as a result of `P = x * G` - how do I update your code to calculate this example? I clarified the Question.
Robert
CC BY-SA 4.0
2019-07-08T02:44:20.850Z
If you're going to use Pollard's Rho over secp256k1, it'd need ~2^128 steps to complete. If you know the DL is very small perhaps the algorithm can be optimized using that information, but I'm not sure about the gains.
Pieter Wuille
CC BY-SA 4.0
2019-07-15T08:41:04.103Z
Yes, that was the advice I was looking for. Thanks a lot. Much appreciated :)
Robert
CC BY-SA 4.0
2019-07-04T18:27:42.253Z
2019-07-04T18:27:42.253Z
Pieter Wuille
<p>I am looking for a Python script or SageMath code implementation for testing the <code>Baby Step - Giant Step</code>and <code>Pollard Rho</code>algorithms on the <code>secp256k1</code> curve.</p>

<p>I have read that these algorithms are well known for solving the ECDL problem for small numbers but I haven't found any code to test this.</p>

<p>edit:</p>

<p>I am looking for generating a small secret multiplier over the standard  secp256k1 curve parameters. </p>

<p>Here is an example for <code>E=EllipticCurve(GF(modi), [0,7])</code> using the standard NIST parameters for <code>G</code>. </p>

<pre><code>G=E(55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424)
</code></pre>

<p>We know that for </p>

<p><code>P=E(69335761065767984070318781108127416310968753866933119760392423089576366173459, 113425617697416972613102767146321902225172329004525144463444008550345431352693)</code></p>

<p>when calculating <code>discrete_log</code> we get the small <code>x=24734216105351567</code> as a result of <code>P = x * G</code>  </p>

<p>Is there any such implementation that will calculate the small x?</p>

<p>Thanks! </p>

<python><secp256k1>
Is there a Python or SageMath implementation for solving the ECDL problem for small secret multiplier?
Robert
# Is there a Python or SageMath implementation for solving the ECDL problem for small secret multiplier?

(Asked by: username_0 on 2019-07-04)

I am looking for a Python script or SageMath code implementation for testing the `Baby Step - Giant Step`and `Pollard Rho`algorithms on the `secp256k1` curve.

I have read that these algorithms are well known for solving the ECDL problem for small numbers but I haven't found any code to test this.

edit:

I am looking for generating a small secret multiplier over the standard secp256k1 curve parameters.

Here is an example for `E=EllipticCurve(GF(modi), [0,7])` using the standard NIST parameters for `G`.

```
G=E(55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424)

```

We know that for

`P=E(69335761065767984070318781108127416310968753866933119760392423089576366173459, 113425617697416972613102767146321902225172329004525144463444008550345431352693)`

when calculating `discrete_log` we get the small `x=24734216105351567` as a result of `P = x * G`

Is there any such implementation that will calculate the small x?

Thanks!

**Tags:** python, secp256k1


---

## 1 answers

### Answer by username_1 on 2019-07-04. Score: 2 | Accepted answer

In Sage.

Let's first define a finite field of size 2^32 (over which exhaustively searching would be painful but doable, but Pollard-Rho should be pretty fast).

```
sage F = GF(2^32 - 5)

```

And a prime-ordered elliptic curve over it (y^2 = x^3 + x + 13 happens to be prime)

```
sage: E = EllipticCurve(F, [1, 13])

```

Let's call the order of the curve `n`:

```
sage: n = E.order()
sage: n
4295040499
sage: n.is_prime()
True

```

Let's pick an arbitrary generator on that curve:

```
sage: G = E.gen(0)
sage: G
(4022957561 : 1193765470 : 1)
sage: G.order() == n
True

```

Now let's pick a random multiple of that generator:

```
sage: import random
sage: x = random.randrange(n)
sage: x
1334636724
sage: P = x * G
sage: P
(2051230087 : 1391923842 : 1)

```

And to find the discrete logarithm, simply use:

```
sage: discrete_log(P, G, n, operation='+')
1334636724

```

The same as our random secret multiplier x.

Sage uses Pollard-Rho and other algorithms internally.

> **Comments:**
> **username_0**: Thank you but I am looking for generating a small secret multiplier over the standard  secp256k1 curve parameters. Here is an example for `E=EllipticCurve(GF(modi), [0,7])` using the standard NIST (G=E) parameters. We know that for `P=E(69335761065767984070318781108127416310968753866933119760392423089576366173459, 113425617697416972613102767146321902225172329004525144463444008550345431352693)` when calculating `discrete_log(P, G, n, operation='+')` we get the small `x=24734216105351567` as a result of `P = x * G` - how do I update your code to calculate this example? I clarified the Question.  
> **username_1**: If you're going to use Pollard's Rho over secp256k1, it'd need ~2^128 steps to complete. If you know the DL is very small perhaps the algorithm can be optimized using that information, but I'm not sure about the gains.  
> **username_0**: Yes, that was the advice I was looking for. Thanks a lot. Much appreciated :)  

---

