Created
June 17, 2022 09:36
-
-
Save Leowbattle/84f85548b6be5cc06cb3f6cb867e3adb to your computer and use it in GitHub Desktop.
Some code for adding rational points on elliptic curves.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Main { | |
public static void main(String[] args) throws Exception { | |
var p = new RationalEllipticCurve.Point(new Rational(1), new Rational(2)); | |
var a = new Rational(-7); | |
var b = new Rational(10); | |
var curve = new RationalEllipticCurve(a, b); | |
var r = curve.multiply(p, -10); | |
System.out.println(r); | |
System.out.println(r.x.floatValue()); | |
System.out.println(r.y.floatValue()); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.math.BigInteger; | |
import java.util.Objects; | |
public class Rational extends Number implements Comparable<Rational> { | |
public final BigInteger numerator; | |
public final BigInteger denominator; | |
public Rational(BigInteger numerator, BigInteger denominator) { | |
if (denominator.equals(BigInteger.ZERO)) { | |
throw new ArithmeticException("/ by zero"); | |
} | |
if (denominator.signum() == -1) { | |
numerator = numerator.negate(); | |
denominator = denominator.negate(); | |
} | |
BigInteger d = numerator.gcd(denominator); | |
this.numerator = numerator.divide(d); | |
this.denominator = denominator.divide(d); | |
} | |
public Rational(BigInteger numerator) { | |
this.numerator = numerator; | |
this.denominator = BigInteger.ONE; | |
} | |
public Rational(long numerator, long denominator) { | |
this(BigInteger.valueOf(numerator), BigInteger.valueOf(denominator)); | |
} | |
public Rational(long numerator) { | |
this(BigInteger.valueOf(numerator)); | |
} | |
public Rational add(Rational r) { | |
BigInteger n = numerator.multiply(r.denominator).add(r.numerator.multiply(denominator)); | |
BigInteger d = denominator.multiply(r.denominator); | |
return new Rational(n, d); | |
} | |
public Rational subtract(Rational r) { | |
BigInteger n = numerator.multiply(r.denominator).subtract(r.numerator.multiply(denominator)); | |
BigInteger d = denominator.multiply(r.denominator); | |
return new Rational(n, d); | |
} | |
public Rational multiply(Rational r) { | |
BigInteger n = numerator.multiply(r.numerator); | |
BigInteger d = denominator.multiply(r.denominator); | |
return new Rational(n, d); | |
} | |
public Rational divide(Rational r) { | |
BigInteger n = numerator.multiply(r.denominator); | |
BigInteger d = denominator.multiply(r.numerator); | |
return new Rational(n, d); | |
} | |
public Rational pow(int exponent) { | |
BigInteger n = numerator.pow(exponent); | |
BigInteger d = denominator.pow(exponent); | |
return new Rational(n, d); | |
} | |
public Rational negate() { | |
return new Rational(numerator.negate(),denominator); | |
} | |
public static Rational parse(String val) { | |
int index = val.indexOf('/'); | |
if (index == -1) { | |
BigInteger numerator = new BigInteger(val); | |
return new Rational(numerator); | |
} | |
String numeratorStr = val.substring(0, index); | |
String denominatorStr = val.substring(index + 1); | |
BigInteger numerator = new BigInteger(numeratorStr); | |
BigInteger denominator = new BigInteger(denominatorStr); | |
return new Rational(numerator, denominator); | |
} | |
public static final Rational ZERO = new Rational(0); | |
public static final Rational ONE = new Rational(1); | |
public static final Rational TWO = new Rational(2); | |
@Override | |
public boolean equals(Object o) { | |
if (this == o) return true; | |
if (o == null || getClass() != o.getClass()) return false; | |
Rational rational = (Rational) o; | |
return Objects.equals(numerator, rational.numerator) && | |
Objects.equals(denominator, rational.denominator); | |
} | |
@Override | |
public int hashCode() { | |
return Objects.hash(numerator, denominator); | |
} | |
@Override | |
public String toString() { | |
if (denominator.equals(BigInteger.ONE)) { | |
return numerator.toString(); | |
} | |
return String.format("%s/%s", numerator, denominator); | |
} | |
@Override | |
public int compareTo(Rational o) { | |
return this.subtract(o).numerator.signum(); | |
} | |
@Override | |
public int intValue() { | |
return numerator.divide(denominator).intValue(); | |
} | |
@Override | |
public long longValue() { | |
return numerator.divide(denominator).longValue(); | |
} | |
@Override | |
public float floatValue() { | |
return numerator.floatValue() / denominator.floatValue(); | |
} | |
@Override | |
public double doubleValue() { | |
return numerator.doubleValue() / denominator.doubleValue(); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class RationalEllipticCurve { | |
public final Rational a; | |
public final Rational b; | |
public RationalEllipticCurve(Rational a, Rational b) { | |
this.a = a; | |
this.b = b; | |
} | |
/** | |
* Given a constant a and a point p, calculate a constant b that guarantees that p lies on the elliptic curve defined by a and b. | |
* @param a | |
* @param p | |
* @return | |
*/ | |
public static Rational calculateB(Rational a, Point p) { | |
Rational b = p.y.pow(2).subtract(p.x.pow(3)).subtract(p.x.multiply(a)); | |
return b; | |
} | |
public static class Point { | |
public final Rational x; | |
public final Rational y; | |
public Point(Rational x, Rational y) { | |
this.x = x; | |
this.y = y; | |
} | |
public Point negate() { | |
return new Point(x, y.negate()); | |
} | |
@Override | |
public String toString() { | |
return String.format("(%s,%s)", x, y); | |
} | |
} | |
static final Rational THREE = new Rational(3); | |
public Point add(Point p, Point q) { | |
Rational m; | |
if (p.x.equals(q.x)) { | |
m = p.x.multiply(p.x).multiply(THREE).add(a).divide(p.y.multiply(Rational.TWO)); | |
} | |
else { | |
m = q.y.subtract(p.y).divide(q.x.subtract(p.x)); | |
} | |
Rational x = m.multiply(m).subtract(p.x).subtract(q.x); | |
Rational y = m.multiply(x.subtract(p.x)).add(p.y).negate(); | |
return new Point(x, y); | |
} | |
public Point multiply(Point p, int n) { | |
boolean negate = false; | |
if (n < 0) { | |
n = -n; | |
negate = true; | |
} | |
Point q = p; | |
for (int i = 0; i < n - 1; i++) { | |
q = add(p, q); | |
} | |
if (negate) { | |
return q.negate(); | |
} | |
return q; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment