I have read the wikipedia section related to HECC (Hyper Elliptic Curve Cryptography) and various questions opened in the current Cryptography Stackexchange site. But I need some help on the following questions, which confuse me.
What do they divide?
To be precise, they do not divide anything. Divisors are nothing but a formal sum of points on a curve done with each points appended with an arbitrary integer. Mathematically speaking, they do not provide to us any immediate meaning.
Before further explanation a formal sum is when something is being represented as being added using $+$ symbol but there is no real meaning to such a sum. For example adding apples to 3 (this is an over exaggerating example)
Why do we need Divisors and Reduced Divisors for HECC?
We need divisors because the calculations, precisely chord-tangent, we use to do on elliptic curve are not available to us anymore. This is because curve of genus 2 need to have odd degrees, say $deg$, greater than $3$. And we know that a line passing through any two point on such a curve would eventually pass through $deg - 2$ number of other points. This can be clearly seen in below image (a straight line, or chord, passing through a curve of genus 2) :
Hence at the end divisors are just formal sum of points on curve. They allow us to add points on the hyper elliptic curve in a formal way. This can be better understood in contrast with elliptic curves.
In elliptic curve when we are adding two points we are not only adding the points on the curve a similar addition is being done on jacobian of the elliptic curve. How this is so? The explanation can be found further.
We know that the Mumford representation of divisor $D$ is in form of polynomial $(u(x), v(x))$ such that $deg(v) < deg(u) \leq g$, where $g $ is genus of the curve. We know that genus of the elliptic curve is $1$ and thus $deg(u) = 1$ and $deg(v) = 0$ again we know that a polynomial of degree $1 $ has only one solution and a polynomial of deg $0$ simply would be a constant integer.
Thus the divisor $D $ on elliptic curve would have Mumford representation as $D = (ax+n, m) $ where $n, m \in \mathbb{Z}$
We know that:
Since our $v(x) $ is a constant integer this can be treated as input to $u(x) $ thus the coordinates associated with $D $ would be: $D = (ax+n, m) = (am+n, m) $
Observation: $D $ is corresponding to a single coordinate.
Similarly $D’ = (bx+p, q) = (bq+p, q)$
Now if we add these two divisors we would get another divisor which would, undoubtedly, correspond to another coordinate. Doing such operation we would find that doing so the result we would get would be similar to what we were getting by adding two points using addition formula on elliptic curve.
This means that there is an isomorphism from jacobian of elliptic curve to points on curve. This is also a corollary of Abel-Jacobi theorem.
(I would try to add a real example of divisor addition here later)
What I wanted to show from the description above is that divisors also exist for elliptic curve but they are not used as there is an isomorphic map from jacobian to point and understanding point addition is more simple than understanding divisors as pointed by kodlu that divisors are high level algebraic geometry concept. I don’t know whether point addition is more efficient to perform than divisor addition.
Owing to the fact that a chord to a curve of degree $5$ would meet the curve at 5 points, and the uniqueness of divisor addition over hyper elliptic curve. We use divisors to define addition law over these curves.
With this it finally gives us a set (of divisors) equipped with a binary operation (of divisor addition) and volla you have a group structure now over curves of genus greater than 1. (How divisors are related to points? That’s a different story using zeta functions)
Also why do we need the Hyperelliptic Curve to be defined in a Cyclic Group? What does the Cyclic Group offer specifically to the HECC?
See discussion here.
