An isogeny provides a mapping from one elliptic curve to another. In this case we will take the mapping of \(E_2:y^2=x^3+1132 x+278\) to \(E_4:y^2=x^3+500 x+1005\) and using \(\mathbb{F}_{2003}\) for the first 50 possible points after a defined starting point. It follows the example defined by on Page 277 of [1].
Isogeny |
Background
An isogeny provides a mapping from one elliptic curve to another. In this case we will take the mapping of:
\(E_2:y^2=x^3+1132 x+278\)
to:
\(E_4:y^2=x^3+500 x+1005\)
and using \(\mathbb{F}_{2003}\). It follows the example defined by on Page 277 of [1].
The mapping from one curve to the next is then defined with:
\( \varphi (x,y) \mapsto \left( \frac{x^2+301x+527}{x+301},\frac{yx^2+602yx+1942y}{x^2+602x+466} \right)\)
In [1], we defined two points on \(E_2\) of \(P_2=(1120,1391)\) and \(Q_2=(894,1452)\). These then map to: \(P_4=(565,302)\) and \(Q_4=(1818,1002)\) on \(E_4\).
\(E_2\) and \(E_4\) are isogenous, but not isomorphic (and where we cannot reverse the mapping from \(E_4\) to \(E_2\).
Coding
The following is the coding required for this isogeny:
package main import "fmt" import "math/big" import "os" import "strconv" func power(a, b int) int { var result int = 1; for 0 != b { if 0 != (b & 1) { result *= a; } b >>= 1; a *= a; } return result; } func main() { q:=2003 argCount := len(os.Args[1:]) start:=1 if (argCount>0) {start,_= strconv.Atoi(os.Args[1])} fmt.Printf("Finite field: %d\n\n",q) a:=1132 b:=278 a2:=500 b2:=1005 fmt.Printf("y^2 = x^3 + 1132 x + 278 (mod %d)\t\ty^2 = x^3 + 500 x + 1005 (mod %d)\n",q,q) for x := start; x <= start+50; x++ { // y^2 = x^3 + 1132 x + 278 y2 := (power(x,3) +a*x+b) % q y := big.NewInt(int64(y2)) yres := y.ModSqrt(y, big.NewInt(int64(q))) if (yres!=nil) { fmt.Printf("(%d %s)",x,y) // x^3 + 500 x + 1005 xinv:=new(big.Int).ModInverse(big.NewInt(int64(x+301)),big.NewInt(int64( q))) z := int(xinv.Int64()) x3:= ((x*x+301*x+527)*z) % q y3 := (power(x3,3)+a2*x3+b2) % q y = big.NewInt(int64(y3)) y = y.ModSqrt(y, big.NewInt(int64(q))) fmt.Printf("\t\t\t\t(%d %s)",x3,y) x2inv:=new(big.Int).ModInverse(big.NewInt(int64(x*x+602*x+466)),big.NewInt(int64( q))) yval:=int(yres.Int64()) ycheck := ( yval* (x*x ) + 602*yval*x + 1942*yval ) * int(x2inv.Int64()) %q fmt.Printf("\tCheck (%d %d)\n",x3,ycheck) } } }
Sample run
A sample run is given next, and where the mapping of \((1120,1391)\) on \(E_2\) is seen to map to \((565,302)\) on \(E_4\):
Finite field: 2003 y^2 = x^3 + 1132 x + 278 (mod 2003) y^2 = x^3 + 500 x + 1005 (mod 2003) (1102 911) (1465 1312) Check (1465 691) (1103 536) (537 73) Check (537 73) (1105 442) (1651 655) Check (1651 655) (1108 1919) (807 1397) Check (807 606) (1109 404) (1125 541) Check (1125 1462) (1110 1804) (314 1163) Check (314 840) (1111 611) (1144 1245) Check (1144 1245) (1113 1931) (585 1278) Check (585 1278) (1114 655) (953 1501) Check (953 1501) (1116 1909) (1474 874) Check (1474 874) (1119 1498) (1417 1598) Check (1417 405) (1120 1391) (565 302) Check (565 302) (1123 1277) (1769 301) Check (1769 1702) (1124 1000) (1182 868) Check (1182 1135) (1125 227) (1256 1497) Check (1256 1497) (1127 147) (722 984) Check (722 984) (1128 711) (1989 776) Check (1989 776) (1130 850) (1973 681) Check (1973 681) (1133 903) (1903 1692) Check (1903 1692) (1134 770) (389 247) Check (389 1756) (1135 503) (152 256) Check (152 1747) (1136 463) (537 73) Check (537 1930) (1140 573) (1998 655) Check (1998 1348) (1143 786) (515 570) Check (515 1433) (1147 1089) (565 302) Check (565 1701)
References
[1] Cohen, H., Frey, G., Avanzi, R., Doche, C., Lange, T., Nguyen, K., & Vercauteren, F. (2005). Handbook of elliptic and hyperelliptic curve cryptography. Chapman and Hall/CRC.