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?
  • 1
    $\begingroup$ Have a look at Theorems 1 and 8 of this paper. $\endgroup$
    – yyyyyyy
    Jan 25, 2019 at 1:42
  • $\begingroup$ Thanks! I think this addresses the first question (though, the formula there is not given in terms $p$ and $q$). $\endgroup$
    – irakliy
    Jan 25, 2019 at 5:12
  • 2
    $\begingroup$ There's no crypto there; it should be on math.se. $\endgroup$
    – fkraiem
    Jan 25, 2019 at 5:30


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.