{{{id=1|
"""
title:Elliptic curves in Edwards parametrization
--------------------------------
Euler and Gauss studied the rational solutions of 
x^2+y^2=c^2(1+dx^2y^2)
where c and d are two parameters
"""
///
}}}

{{{id=2|
# the set of real solutions gives little information on the rational solutions except for the symetries:
var('x,y')
implicit_plot(x^2+y^2==1-100*x^2*y^2,(-2,2),(-2,2))
///
}}}

{{{id=3|
# Euler remarked that the following formulae allow to combine two solutions and hence to obtain a third one 
def add(c,d,x1,y1,x2,y2):
    x3 = (x1*y2+y1*x2)/(c*(1+d*x1*x2*y1*y2))
    y3 = (y1*y2-x1*x2)/(c*(1-d*x1*x2*y1*y2))
    return x3,y3

# Exercise: argue that the addition law is commutative.
///
}}}

{{{id=4|
# Exercise: explain why the following code testes that the addition law is an internal law, i.e. (x3,y3) belongs to the curve
K.<c,d,x1,y1,x2,y2,x3,y3>=QQ['c,d,x1,y1,x2,y2,x3,y3']
I=K.ideal([(x1^2+y1^2)-c^2*(1+d*x1^2*y1^2),\
         (x2^2+y2^2)-c^2*(1+d*x2^2*y2^2),\
         (x3^2+y3^2)-c^2*(1+d*x3^2*y3^2)])


# internal law
x12,y12=add(c,d,x1,y1,x2,y2);
assert (x12^2+y12^2-c^2*(1+d*x12^2*y12^2)).numerator() in I
///
}}}

{{{id=5|
# Exercise: explain why the folowing function tests if two points are equal
def are_equal(xy,x_y_):
    x,y    = xy
    x_,y_  = x_y_
    answer = ((x-x_).numerator() in I) and ((y-y_).numerator() in I)
    return answer
///
}}}

{{{id=6|
# The newt code checks that [0,c] is the neutral element
x1_,y1_=add(c,d,x1,y1,0,c)
assert are_equal([x1_,y1_] , [x1,y1] )

# Exercise: give a mathematical proof (on paper) of the same property
///
}}}

{{{id=7|
# The following code checks that the element [-x,y] is the inverse of [x,y]
x_,y_=add(c,d,x1,y1,-x1,y1)
assert are_equal( [x_,y_] , [0,c] )
# Exercise: by looking at the graph of real solutions, find the points of order 2.
///
}}}

{{{id=8|
# assossiativity: [x_l,y_l]=([x_1,y1]+[x_2,y_2])+[x_3,y_3]
x23,y23=add(c,d,x2,y2,x3,y3)
x_l,y_l=add(c,d,x12,y12,x3,y3)
x_r,y_r=add(c,d,x1,y1,x23,y23)
assert are_equal([x_l,y_l] , [x_r,y_r])

# Note that this completes the proof that add is a group law (although we gave no deep explanation why it is true)
///
}}}

{{{id=9|
# Weierstrass parametrization: y^2+a1*xy=x^3+a2*x^2+a4*x+a6
var('u,v')
# change of variables
x=c*u/v
y=c*(u-1)/(u+1)
(x^2+y^2-c^2*(1+d*x^2*y^2)).numerator().factor()

"""
Note that this shows that any Edwards curve transforms into an elliptic curve in Weierstrass equation.
Exercise: does it mean that every elliptic curve is isomorphic to an Edwards curve ? isogenous to an Edwards curve ? 
"""
///
}}}

{{{id=10|
# SAGE allows to define elliptic curves in Weierstrass parametrization
E=EllipticCurve([2,3])

# écrivez son équation
///
}}}

{{{id=11|
"""
The Mordell-Weil theorem states that any elliptic curve has a group structure isomorphic to T x Z^r,
where T is a finite group (called torsion subgroup) and an integer r (called rank)
"""
E.rank()

# Exercise: explain why T contains precisely the points of finite order
///
}}}

{{{id=12|
# In order to compute T we write:
E.torsion_subgroup()

# Exercise: how to compute the points of order 2?
///
}}}

{{{id=13|
# In order to find a system of generators one writes:
gs=E.gens()
P0=gs[0]
///
}}}

{{{id=14|
# Exercise: explain how to obtain all points of the curve ? does this procedure produce the same point several times ?
42*P0
///
(-1125531589759472249503724625690249221704536442540993981120652192338551014125129637930975809990243867052790344046942037931698368937731753725323785991608699443157261939420682765411418794626313719672741291731037446552905209914317167194513033847014916019360852583955802919196836163732251361213698981898059158260741309462669427763395418766159262993775545758914684827756388304142593516074531091195096850493922457065780157308972909221173340868925430805299656053770284295064207323037300833439094984082690187818541677204562620285256679266542115247397316971275876196467581183809983522202399053273552948321031455846307840950764418067798202144072441178149533850644930711373099460646602894935233042010832795406324251267953867529343536751963337714882455595860681015619175893524193956501454355169522706662480967273558539537704420543449394083372807065759108795378154520061139183579948895729802852610634253769251306484647203718023499419954278630529118583564048179369224724290404881451930053426150838405519641095836391421973538369682545048486722329840986710798181724100689943081286093746434834159718797166021410309421112272077399/1150222098849852436372310196376840695618689407131032936986178854232277061089951046440185526278224884472165852292785194464694793997780858912157007172241947185841083693280987056803917561908469066922040082722047206605341303791777073401068575905106728941356687932870179736447550413548603754608693408198450600846580807097510361912608982251324848819497064406525838497801334367997834781228650266220061920361653660545739559017773315468211833528649415805666769123376236813341035275403054881083685886826519779980938162561415164610396130387437093572685396707404568471917126914772429820124766236505923140747437715952434532171180609230366713246932644320244688419170103854338207777508871759453625251893430924638850689165365208604832569280415932112283255719928206388285743378492910744229804161152450129077752831863852137088950339009670299734598287065472470371920255131681247696635159298292338500266194528979360261781228985293173452777656637692963542872116818260880090751371789572213288728711148313807304244460091470246287033387205684135449938773984514935033645236396505481386792810122011457735047894729588507981491566058435600 : -401547646963833109431194958988156438472568806414494941588035749659202843116872529385169681767675693561822266335275825864660041391327352986468806075365743803348314647264527229296057012463596435647869414493951621925573314853399317584896753600323442378772962136055457273046993530473561954185297942251438652458778405540987804507787302540404470901600860929877613650945591060656731859837834021944376034602801368377273472256447535437064905331574890578300303434548629761087465719257682870708262518088442099038832822554335147351994211111211965728682077705869083626362158060379358849989877309710909750983176576721696739351857289986532208202253847302213936112646794033191291172342879297228382939111326126701251341523067042937723848298185542442220147491082512623038870018043469293788715804973155052560036242257582077927817182630386691380605672857420738019522272539784926075075788690182702134852399643490673143288578163312925118896685396464409816186813479399049460736201400752796354963179250098278565447171990418049972627765891220180667419020831980455859903434912137885314334662358416611954244909951377162472265830864590737877910470339451268650553902341609916656332832843978407614354120511198906682735008047766871543542789515592387637658314226520810561235655800378635755924777152052962375327584188026167949266243960391612070897232286932310285370611406903814313677482878185658537156453044734284009829386654456560515983580361910753613627157679441533349501567720831575339241319344297732234187588389463728862002198079661729809865524825957855995406197103240076846385336898938098753432517642820718911018297119479866832071905387604149586128232019536135783502738059520742421154989372651/1233594887869999697125561730010828914439631696646186478618263220832218444761750044483859470304518957528064338947507956426765025137160862457211082875589323795623620090177835759662478090540085225497279167549799075069409877508114902996595832249347159439251113050327482418742534661263646975612886874456557565596811844470272098832423538901160781373623824768643221286994756018705881058688774664129907949043059071757879541963527722544958085746516861982752795728517075904704809581356983547167157892569255092860073601267529345625375748037172172359480104858337688844922772895511171516123448538735160772296551594442146872134110982299762012774085582029658708762720203178803829180992487554943253128128566570116813990377920551025650269942846466099117297188457660947407318770265912930632820793975860725087878931184626872205082468380656613414603217671606772502086098620524503737601529206493582915599815012052728768028011634374304023603435372516890413948825925736700184008997538900493105637746005212535522650868490595187341636706970854347071679617468031309928794809286966305426611365697621881748030580811712229743632547150610466055955526142116400358670794007508635634218531076277876191322303047016911117091242304461563432093139334915168224408873515510924632026002527889280386053088056863496622441113175315152076746712503292719642096782968804171011863746670248672502969590037237815138865148018127318000864755099917525292663006223968210649686765749051524384218859638282832685380810736871082150468404837961789046939624085579048139329299694877006016159021884939040704908209685012839293257209444199207480434919688130598508265290380987060418515890617790569906323240366278567380858542504000 : 1)
}}}

{{{id=15|
"""
Complete law. Theorem: in all parametrizations there exist a finite set of points R1, R2, ..., Rk and a finite formulae so that 
-each formula is defined everywhere except for some Ri;
- one can add any two points (which can be equal) using at least one of the formulae. 

Example: in the Weierstrass parametrisation k=1 and R1=(0:1:0).
Exercise: prove that the points to be avoided in the case of Edwards curves have order 4. Solution in the articles:
[1] Dan Bernstein and Tanja Lange. A complete set of addition laws for incomplete edwards curves.
[2] H. Hisil, K. Wong, G. Carter and E. Dawson Twisted Edwards curves revised.  
Exercise: construct elliptic curves where the group law is unified. Solution in the article:
[3] Dan bernstein and Tanja Lange. Faster addition and doubling on elliptic curves.

"""
///
}}}