This PR fixes the small_a_twist in complex multiplication.
For the new curve to be isogenous to the original curve, it is important that there is a mapping between old points and the new points.
The current algorithm tries to find "d" such that, for the original curve:
y^2 = x^3 + ax + b
we have:
v^2 = u^3 + (d^2)au + (d^3)b
The two curves have a one-one mapping (x, y) -> (dx, d\sqrt{d}y) if \sqrt{d} exists, i.e., d is a quadratic residue.
The previous algorithm did not check that d is a quadratic residue. When d is not, the curve being constructed will be different. Here is an example.
The original curve:
Elliptic Curve defined by y^2 = x^3 + 41505661548631025023673322108391240347281592162182316256750735980266071156670*x + 40336978353161653342630956714884788320200642545308267522653729451383620675813 over Finite Field of size 57896044618658097711785492504343953927116110621106131396339151912985063395361
has order 57896044618658097711785492504343953926634992332820282019728792003956564819949.
The new curve using the old code, with a = 3, is, in fact, not isogenous.
Elliptic Curve defined by y^2 = x^3 + 3*x + 56381510977082522969977449251114157576175385487557978089110428960941283458373 over Finite Field of size 57896044618658097711785492504343953927116110621106131396339151912985063395361
has order 57896044618658097711785492504343953927597228909391980772949511822013561970775.
The new curve using the new code (fixed), with a = 6, is now correct.
Elliptic Curve defined by y^2 = x^3 + 6*x + 7277470329389939148381533754641607518092114590371880995609984561067837624798 over Finite Field of size 57896044618658097711785492504343953927116110621106131396339151912985063395361
has order 57896044618658097711785492504343953926634992332820282019728792003956564819949.
This PR fixes the small_a_twist in complex multiplication.
For the new curve to be isogenous to the original curve, it is important that there is a mapping between old points and the new points.
The current algorithm tries to find "d" such that, for the original curve: y^2 = x^3 + ax + b we have: v^2 = u^3 + (d^2)au + (d^3)b
The two curves have a one-one mapping (x, y) -> (dx, d\sqrt{d}y) if \sqrt{d} exists, i.e., d is a quadratic residue.
The previous algorithm did not check that d is a quadratic residue. When d is not, the curve being constructed will be different. Here is an example.
The original curve:
has order 57896044618658097711785492504343953926634992332820282019728792003956564819949.
The new curve using the old code, with a = 3, is, in fact, not isogenous.
has order 57896044618658097711785492504343953927597228909391980772949511822013561970775.
The new curve using the new code (fixed), with a = 6, is now correct.
has order 57896044618658097711785492504343953926634992332820282019728792003956564819949.