how to avoid error " OverflowError: Python int too large to convert to C long

asked 2017-11-15 05:12:10 +0200

This post is a wiki. Anyone with karma >750 is welcome to improve it.

Here is the code:

import time  
p=101135929216614342638630785939670479796699743028362954839791101900457831250749
#p=115792089210356248762697446949407573530086143415290314195533631308867097853951
A=-3#4451685225093714772084598273548424
B=1#2061118396808653202902996166388514
K.<a>=GF(p^2);K.modulus()                    
#R.<z>=PolynomialRing(K);
R.<z> = PolynomialRing( K, sparse=True )
x= (33711976405538114212876928646556826598899914342787651613263700633485943750250*a + 67423952811076228425753857293113653197799828685575303226527401266971887500500)*z^101135929216614342638630785939670479796699743028362954839791101900457831250749 + (67423952811076228425753857293113653197799828685575303226527401266971887500499*a + 33711976405538114212876928646556826598899914342787651613263700633485943750250)*z

 y= (67423952811076228425753857293113653197799828685575303226527401266971887500500*a + 33711976405538114212876928646556826598899914342787651613263700633485943750250)*z^101135929216614342638630785939670479796699743028362954839791101900457831250749 + (33711976405538114212876928646556826598899914342787651613263700633485943750249*a + 67423952811076228425753857293113653197799828685575303226527401266971887500499)*z

f=(11237325468512704737625642882185608866299971447595883871087900211161981250083*a + 56186627342563523688128214410928044331499857237979419355439501055809906250416)*z^303407787649843027915892357819011439390099229085088864519373305701373493752247 + (67423952811076228425753857293113653197799828685575303226527401266971887500499*a + 33711976405538114212876928646556826598899914342787651613263700633485943750249)*z^202271858433228685277261571879340959593399486056725909679582203800915662501499 + 67423952811076228425753857293113653197799828685575303226527401266971887500499*z^202271858433228685277261571879340959593399486056725909679582203800915662501498 + (33711976405538114212876928646556826598899914342787651613263700633485943750250*a + 67423952811076228425753857293113653197799828685575303226527401266971887500499)*z^101135929216614342638630785939670479796699743028362954839791101900457831250751 + 67423952811076228425753857293113653197799828685575303226527401266971887500500*z^101135929216614342638630785939670479796699743028362954839791101900457831250750 + (a + 2)*z^101135929216614342638630785939670479796699743028362954839791101900457831250749 + (89898603748101637901005143057484870930399771580767070968703201689295850000666*a + 44949301874050818950502571528742435465199885790383535484351600844647925000333)*z^3 + 67423952811076228425753857293113653197799828685575303226527401266971887500499*z^2 + (101135929216614342638630785939670479796699743028362954839791101900457831250748*a + 1)*z + 101135929216614342638630785939670479796699743028362954839791101900457831250748
print"\n Elliptic Curve fE(z) = ",f 
#fE11 = fE.coefficients();fE11
start = time.time()

E = EllipticCurve(GF(p),[0,0,0,A,B]);
#print"EC=",E 
#print (E.points()[:4])                            



#print "\n Take Two point on Elliptic curve "       
P = E.random_point()#[2];E(0,2) 
print"\n point1=",P                           # select Random point P on elliptic Curve      
Q =E.random_point()#[4]; E(4,2)
print"\n point2=",Q
# P= E(59708,90244);P
# Q= E(108685,5812);Q

R1=P+Q;
print"\n Addition of two points Existing Approach (P+Q) =",R1 


if((P[0]!=Q[0]) and (P[1]!=Q[1]) or (P[0]!=Q[0]) and (P[1]==Q[1])):
    R.<z> = PolynomialRing( K, sparse=True )
    **g=(((Q[0]-P[0])*y)-((Q[1]-P[1])*x)-(P[1]*Q[0]-Q[1]*P[0])) ;g**#**error obtained at this point** 
    f1=( f % g ).monic()
    print "\n gcd=",f1
    #R2=fL.quo_rem(f1);R2
    #R3=fE.quo_rem(f1);R3
    f2= (z-P[0]-P[1]*a)*(z-Q[0]-Q[1]*a);
    print "\n point equation=",f2
    f3=f1//f2;
    print "\n f3=",f3;
    new4 = f3.coefficients();new4
    Result=new4[0];Result
    #R15=K(-Result);R15
    F.<a>=GF(p)
    R.<a>=PolynomialRing(F);
    R1.<z>=PolynomialRing(R);
    f=Result
    M=R(f).coefficients();#M
    M1= M[1];#M1
    M4=M[0];#M4
    M2=F(-M4);#M2
    M3=F(-M4)
    R=(M2*a+M[1]);#R
    R1=(M2,M1);#R1
    #load("example.sage")
    G = E.point((R1));#G
    print "\n Addition of two points New Approach(P+Q)=" ,G   
    end = time.time()
    print("the time taken for the existing approach is given by ", end - start)

edit retag flag offensive close merge delete

Comments

I can not reproduce your error on my machine. Could you please give us some informations so that someone can try to reproduce your problem:

which version of Sage did you use ?
which OS ?
did you install Sage from the binaries, and which ones ?
did you compile Sage yourself ?
which notebook did you use (Sage notebook or jupyter notebook) ?
did you use the command line ?
which commands did you type precisely to get the error ?
which error message did you get ?
... ?

tmonteil ( 2017-11-15 08:51:04 +0200 )edit

I couldn't reproduce it, either, for what that's worth.

John Palmieri ( 2017-11-15 18:05:19 +0200 )edit

i am working on sagemath cloud os is MAC no all by sagemath cloud .sagews files the error is overflow error . when i run the code on sagemath cloud error is obtained

santoshi ( 2017-11-16 12:53:34 +0200 )edit

sage math version is 7.3 on my macbook pro

santoshi ( 2017-11-16 12:55:06 +0200 )edit

add a comment

answered 2017-11-20 21:13:53 +0200

dan_fulea
5337 ●5 ●43 ●90

Try the following code instead:

import time
p = 101135929216614342638630785939670479796699743028362954839791101900457831250749

A = -3
B =  1
F = GF(p)
E = EllipticCurve( F, [A,B] );

S.<W> = PolynomialRing( F )
K.<a> = GF( p^2, modulus=W^2+W+1 )
print "Modulus of K is =", K.modulus()                    

R.<z> = PolynomialRing( K, sparse=True )

x = (a + 2  )/3 * (z^p-a*z)
y = (1 + 2*a)/3 * (z^p-  z)

f = y^2 - ( x^3 + A*x + B )
# print "\n Elliptic Curve fE(z) = ", f

P = E.random_point()
Q = E.random_point()

print "point1 =", P.xy()
print "point2 =", Q.xy()

start1 = time.time()
H      = P + Q;
end1   = time.time()
Hx, Hy = H.xy()
print "H = P + Q has the components:\nHx = %s\nHy = %s" % ( Hx, Hy )
print "Time for this operation (existing approach): %s" % ( end1 - start1 )


if P[0] != Q[0] :
    start = time.time()

    g = ( + ( Q[0] - P[0] ) * y
          - ( Q[1] - P[1] ) * x
          - ( P[1]*Q[0] - Q[1]*P[0] ) )
    print "g =", g

    f1 = ( f % g ).monic()
    print "f1 = gcd = ", f1

    f2 = ( z - P[0] - P[1]*a ) * ( z - Q[0] - Q[1]*a )
    print "\npoint equation =", f2

    f3 = f1 // f2
    print "f3 =", f3

    c = f3.constant_coefficient()
    M0, M1 = S(c).coefficients()

    G = E.point( ( -M0, M1 ) )
    end = time.time()

    Gx, Gy = G.xy()
    print "G = P + Q (?) has the components:\nGx = %s\nGy = %s" % ( Gx, Gy )
    print "Time for this operation (new approach): %s" % ( end - start )

Code is rewritten so that

it is clean and readable (at least for me), and hopefully will no longer lead to errors,
the reader has no overwhelming numbers combat to absolve,
there is no redefinition of R, and of a, and a "dirty" isolation of coefficients related to a, and the polynomial ring R1 does not become a point after some lines of code,
there is no hidden mathematical structure, for instance it is simple to see the formulas: $$x =\frac{a+2}3(z^p-az)\ ,$$ $$y =\frac{1+2a}3(z^p-z)\ ,$$ $$f=y^2-(x^3 +Ax+B)\ ,$$ so that the answerer can somehow "profit" from the invested work. (Why do you keep this information secret? Why do you not give a link, or a small comment for the "new addition formula"? Why do you use some fE and fL in the "private comments" and not explain what happens behind?)
note: some code was left "as it was" to see where the new code was changed / inserted. Just omit the prints between setting start and end to get the net time used for the computations.

The sage interpreter (on this old linux machine) gives me (among other information from the numerous prints) this time the following:

Modulus of K is = x^2 + x + 1

H = P + Q has the components:
Hx = 70583706647472158282446068656049767531471554371674207909734012354515559580768
Hy = 1539735264843042217709244891894727788602955406703432172905441025552368530057
Time for this operation (existing approach): 0.000148057937622

G = P + Q (?) has the components:
Gx = 70583706647472158282446068656049767531471554371674207909734012354515559580768
Gy = 1539735264843042217709244891894727788602955406703432172905441025552368530057
Time for this operation (new approach): 0.00576591491699

P.S. Please give a link to the related mathematical construction used above, this would be after all a fair gentle nice touch.

edit flag offensive delete link

Comments

is it possible to write down above code in C programming.

santoshi ( 2017-11-23 05:37:29 +0200 )edit

This is good piece of work, it mainly depends on available libraries. A possibility would be maybe to use the pari/gp libraries. The space and the space here is not suitable for this ramification of the discussion.

dan_fulea ( 2017-11-24 11:50:56 +0200 )edit

the above timing in sage is in us or ms

santoshi ( 2017-11-25 18:29:11 +0200 )edit

add a comment

how to avoid error " OverflowError: Python int too large to convert to C long

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

how to avoid error " OverflowError: Python int too large to convert to C long edit

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

how to avoid error " OverflowError: Python int too large to convert to C long