Bachet replication formula with Python and SageMath

Aurore Guillevic (Inria Nancy Grand-Est)

February 3, 2022

Elliptic curves, number theory and cryptography

Tutorial 1

We will use SageMath, but if you don’t have SageMath, you can do this 1st tutorial with Python, just skip Exercises 1 and 2 and jump directly to exercise 3.

Create a folder on your disk for this course.

Do not use white spaces, dashes or non-ASCII characters (' ', '-' etc) in folder names or file names, instead you can use an underscore _.

Create a new file tutorial1.py where you will write your functions.

  1. Write a function that given a parameter c and an initial integer-valued solution to a Bachet equation of the form y^2 - x^3 = c, computes the next solution with Bachet’s replication formula:
def bachet_replication_rational(c, x, y):
    """
    returns the next solution to the equation y^2 - x^3 = c
    
    INPUT:
    - `c`: integer
    - `x`: rational number
    - `y`: rational number
    
    satisfying y^2 - x^3 = c
    
    RETURN: (X, Y)
    """
    # TODO below write your function with a return statement
  1. Write a test function for your answer to Exercise 1, uses the solution given in the Lecture: for c=-2, a solution is (3,5). Check that your function outputs a valid solution from these inputs.
def test_bachet_replication_rational():
    """
    Test bachet_replication function with c=-2
    Check that the next three solutions to y^2 - x^3 = -2 are
    correct, starting at (3,5)
    
    RETURN: True or False
    """
    # TODO below write your test with a return statement

SageMath in the prompt (the interpreter) converts automatically an expression x/y with integer x, y into a fraction, while Python performs an Euclidean division to get an integer. To obtain an exact rational number in a .py file (outside SageMath interpreter), one needs to tell explicitly SageMath to do so with

t = QQ(a/b)

where QQ (or Q) stands for the field of rationals QQ. Use

import_statements(QQ)

in SageMath prompt to find which library to import in your .py file. Hint: you want to write something like

from sage.xxx import QQ
  1. Now write a function that takes integers as inputs and deal with the numerators and the denominators separately. The inputs x and y change to xn, xd for the numerator and the denominator of x, and yn, yd for the numerator and denominator of y. You will need to be careful while handling the coefficients in the formula.
def bachet_replication_fraction(c, xn, yn, xd, yd):
    """
    returns the next solution to the equation Y^2 - X^3 = c
    
    INPUT:
    - `c`: integer
    - `xn`: integer, numerator of x
    - `yn`: integer, numerator of y
    - `xd`: integer, denominator of x
    - `yd`: integer, denominator of y
    
    satisfying (yn/yd)^2 - (xn/xd)^3 = c
    
    RETURN: (Xn, Yn, Xd, Yd)
    """
    # TODO below write your function with a return statement
  1. Write a test function like in Exercise 2.
def test_bachet_replication_fraction():
    """
    Test bachet_replication_rational function with c=-2
    Check that the next three solutions to y^2 - x^3 = -2 are
    correct, starting at (3,5)
    
    RETURN: True or False
    """
    # TODO below write your test with a return statement

  1. How can you give a default value to xd and yd so that the header is compatible with integers x,y like in exercise 1?

  2. Using from math import gcd, simplify the fractions. Check again with your test function.

  3. With c=1, a solution is (2, 3). With c=-432, a solution is (12,36). What happens with these solutions? Print the next three solutions.

    Later we will see that such points (x,y) on a Bachet elliptic curve y^2 = x^3 + c are torsion points.

If you succeeded in installing Sage, you can check with:

E1 = EllipticCurve([0,1])
E1.torsion_points()

E2 = EllipticCurve([0,-432])
E2.torsion_points()

Optional exercises

If you are done, you can then do the following optional exercises from Washington’s book. The numbers refer to the exercise numbers at the end of chapter 2 p. 71-76.