Skip to main content
Bumped by Community user
fixed typo in title
Link
Ella Rose
  • 19.9k
  • 6
  • 55
  • 103

Pattenrs Patterns in elliptic curve division polynomials

Source Link
irakliy
  • 989
  • 7
  • 16

Pattenrs in elliptic curve division polynomials

While looking at division polynomials of elliptic curves in relation to this and this questions, I noticed some patterns. I am wondering if anyone knows of general formulas the describe these patterns. First, an example:

Suppose we have an elliptic curve defined by $y^2 = x^3 + 2x + 10$ over $\mathbb{Z}_{q}$ where $q=53$. The order of this curve is $p = 59$. Suppose also that the generator $G = (7, 7)$.

For any value $a$ in $\mathbb{Z}_{p}$ we can build a sequence of a values generated by evaluating division polynomials such that:

$$ a_0 = \psi_a(G) $$

$$ a_1 = \psi_{a+p} (G) $$

$$ a_2 = \psi_{a + 2p}(G) $$

$$ a_i= \psi_{a+ip}(G) $$

The table below shows these sequences built for various values of $a$ (columns with values for $a$ between 4 and 16) and $i$ (rows with values for $i$ between 0 and 27):

enter image description here


My questions are:

  1. It seems like the sequence $a_0...a_i$ is periodic (in the example above, it repeats after every 26 values of $i$). It also seems like the length of the period depends only on values of $q$ and $p$ (and not on the equation of the curve). Is there a general formula that can be used to calculate the period of the sequence for arbitrary values of $q$ and $p$?
  2. It seems like within each period, there are two points of symmetry where the preceding value equals the following value. In the above table these points have light orange background (e.g. for $a = 4$ these points are $a_5 = 36$ and $a_{18} = 20$). Is there a general formula that can be used to find such points of symmetry?
  3. It also seems that these points of symmetry have some relation to quadratic residue modulo $q$. For example, in the table above, exactly one point of symmetry is a quadratic residue modulo $53$ (these points have borders around them). Is there a general formula that describes this relation?