Ask Your Question
2

Elliptic Curve: Python int too large to convert to C long

asked 2018-10-24 16:43:51 +0200

jbaczuk gravatar image

updated 2018-12-16 18:41:14 +0200

FrédéricC gravatar image

I'd like to plot the secp256k1 curve, but I get "Python int too large to convert to C long". Does sage have a built-in type to handle large numbers, or is there a recommended way to do this?

p=2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1
A=0
B=7
F=GF(p)

F=GF(p)
E = EllipticCurve( [A,B] )
show(graphics_array([plot(E,thickness=3), plot(E.change_ring(GF(p)))]), frame=True)

Traceback:

Traceback (most recent call last):    A=0
  File "", line 1, in <module>

  File "/private/var/folders/k6/lrb1z5jd7vx95c7lh05kq6v00000gn/T/tmpmwcLjo/___code___.py", line 14, in <module>
    exec compile(u'show(graphics_array([plot(E,thickness=_sage_const_3 ), plot(E.change_ring(GF(p)))]), frame=True)
  File "", line 1, in <module>

  File "/Users/Jbaczuk/Documents/Personal/SageMath/local/lib/python2.7/site-packages/sage/misc/decorators.py", line 567, in wrapper
    return func(*args, **options)
  File "/Users/Jbaczuk/Documents/Personal/SageMath/local/lib/python2.7/site-packages/sage/plot/plot.py", line 1941, in plot
    G = funcs.plot(*args, **original_opts)
  File "/Users/Jbaczuk/Documents/Personal/SageMath/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_finite_field.py", line 107, in plot
    G += plot.points([P[0:2] for P in self.points() if not P.is_zero()], *args, **kwds)
  File "/Users/Jbaczuk/Documents/Personal/SageMath/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_finite_field.py", line 208, in points
    v = self._points_via_group_structure()
  File "/Users/Jbaczuk/Documents/Personal/SageMath/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_finite_field.py", line 150, in _points_via_group_structure
    for m in range(1,ni[0]):
OverflowError: Python int too large to convert to C long
edit retag flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted
1

answered 2018-10-24 17:07:41 +0200

tmonteil gravatar image

updated 2018-10-24 17:33:01 +0200

Note that the problem is not in defining the elliptic curve, but only when plotting it:

sage: E.change_ring(F)
Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 115792089237316195423570985008687907853269984665640564039457584007908834671663
sage: E.plot()
Launched png viewer for Graphics object consisting of 1 graphics primitive
sage: E.change_ring(F).plot()
OverflowError: Python int too large to convert to C long

More precisely, the problem comes from the fact that the plot function iterates over the points of the curve:

sage: E = E.change_ring(F)
sage: E.points()
---------------------------------------------------------------------------
OverflowError                             Traceback (most recent call last)
<ipython-input-39-e168c98b87f8> in <module>()
----> 1 E.points()

/opt/sagemath/sage-source/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_finite_field.pyc in points(self)
    206         k = self.base_ring()
    207         if k.is_prime_field() and k.order()>50:
--> 208             v = self._points_via_group_structure()
    209         else:
    210             v =self._points_fast_sqrt()

/opt/sagemath/sage-source/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_finite_field.pyc in _points_via_group_structure(self)
    148         if ngens == 0:    # trivial group
    149             return H0
--> 150         for m in range(1,ni[0]):
    151             H0.append(H0[-1]+pts[0])
    152         if ngens == 1:    # cyclic group
OverflowError: Python int too large to convert to C long

Even if the loop was tuned so that it accepts such a large number (e.g. using xsrange instead of range), you will not get an error but, you will have to wait forever, there are just too many points:

sage: E.cardinality()
115792089237316195423570985008687907852837564279074904382605163141518161494337

So, you can think of making you own partial plot. Unfortunately, it seems currently not possible to look at the "first" points of the curve, since the iteration first computes all points:

sage: E.__iter__??
Source:   
    def __iter__(self):
        """
        Return an iterator through the points of this elliptic curve.

        EXAMPLES::

            sage: E = EllipticCurve(GF(11), [1,2])
            sage: for P in E:  print("{} {}".format(P, P.order()))
            (0 : 1 : 0) 1
            (1 : 2 : 1) 4
            (1 : 9 : 1) 4
            (2 : 1 : 1) 8
            ...
            (10 : 0 : 1) 2
        """
        for P in self.points():
            yield P

So, you can think of sampling some points using:

sage: E.random_element()
(5931825134738693147239085942431521905946451730071919123281591598082826125500 : 12327482641317859093710230640295762484447995871249429156192043444179262968436 : 1)
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2018-10-24 16:43:51 +0200

Seen: 1,275 times

Last updated: Oct 24 '18