An isogeny provides a mapping from one elliptic curve to another. For example, \(y^2=x^3+x\) maps to \(y^2=x^3-4x\) with the mapping:
\(\phi(x,y) = \left(\frac{x^2+1}{x},y\frac{x^2-1}{x^2}\right)\)
IsogenyAn isogeny provides a mapping from one elliptic curve to another. For example, \(y^2=x^3+x\) maps to \(y^2=x^3-4x\) with the mapping: \(\phi(x,y) = \left(\frac{x^2+1}{x},y\frac{x^2-1}{x^2}\right)\) |
An isogeny provides a mapping from one elliptic curve to another. For example, \(y^2=x^3+x\) maps to \(y^2=x^3-4x\) with the mapping:
\(\phi(x,y) = \left(\frac{x^2+1}{x},y\frac{x^2-1}{x^2}\right)\)
In this case we will display the points on \(y^2=x^3+x\) up to \(x=50\) and then map to \(y^2=x^3-4x\), and with a check for the mapping of:
\(\phi(x,y) = \left(\frac{x^2+1}{x},y\frac{x^2-1}{x^2}\right)\)
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:=97 argCount := len(os.Args[1:]) if (argCount>0) {q,_= strconv.Atoi(os.Args[1])} fmt.Printf("Finite field: %d\n\n",q) fmt.Printf("y^2 = x^3 + x (mod 97)\t\ty^2 = x^3 - 4x (mod 97)\n") for x := 1; x <= 30; x++ { // y^2 = x^3 + x y2 := (power(x,3) + x) % q y := big.NewInt(int64(y2)) yres := y.ModSqrt(y, big.NewInt(int64(q))) if (yres!=nil) { fmt.Printf("(%d %s)",x,y) // y^2 = x^3 - 4x xinv:=new(big.Int).ModInverse(big.NewInt(int64(x)),big.NewInt(int64( q))) z := int(xinv.Int64()) x3:= ((x*x+1)*z) % q y3 := (power(x3,3) - 4*x3) % 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)),big.NewInt(int64( q))) ycheck := ( int(yres.Int64() ) * (x*x-1) * int(x2inv.Int64())) %q fmt.Printf("\tCheck (%d %d)\n",x3,ycheck) } } }
A sample run:
Finite field: 97 y^2 = x^3 + x (mod 97) y^2 = x^3 - 4x (mod 97) (1 83) (2 0) Check (2 0) (5 79) (44 91) Check (44 6) (8 61) (93 7) Check (93 7) (11 88) (64 52) Check (64 52) (12 73) (4 57) Check (4 57) (19 66) (65 7) Check (65 90) (20 39) (54 37) Check (54 60) (22 0) (0 0) Check (0 0) (23 68) (61 57) Check (61 40) (25 79) (91 83) Check (91 14) (30 89) (85 39) Check (85 39)