Skip to content

Instantly share code, notes, and snippets.

@Leowbattle
Created June 17, 2022 09:36
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Leowbattle/84f85548b6be5cc06cb3f6cb867e3adb to your computer and use it in GitHub Desktop.
Save Leowbattle/84f85548b6be5cc06cb3f6cb867e3adb to your computer and use it in GitHub Desktop.
Some code for adding rational points on elliptic curves.
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());
}
}
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();
}
}
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