rrspace
=======
This software is distributed under LGPL-2.1+ (i.e., LGPL version 2.1 or later).
Please report bugs to .
I - Installation
----------------
This software can be compiled using GNU make with g++.
Running the command
```
make
```
in the directory containing the source files builds three executable files:
`rrspace`, `class_grp_arith` and `tests`.
In order to build only one of these programs, use the command
```
make
```
where `` is `rrspace`, `class_grp_arith` or `tests`.
Compiling this software requires the [NTL library](https://www.shoup.net/ntl/).
In order to compile the program "tests", the
[cppunit library](https://freedesktop.org/wiki/Software/cppunit/) is also required.
After compiling, the three following commands should succeed without any error:
```
./tests
./rrspace < example_rrspace_input
./class_grp_arith < example_class_grp_div_input
```
II - Usage
----------
Examples of inputs for `rr_space` and `class_grp_arith` are provided in the files
`example_rrspace_input` and `example_class_grp_div_input`. The formats for the
mathematical objects are detailed in the next section.
Disclaimer: The algorithms implemented in this software are probabilistic, and
they have a probability of failure. Also, they rely on some genericity
assumptions (such as generic coordinates). Finally, some problems may arise in
small characteristic, for instance if the characteristic divides the degree of
the curve. In case of failure, the most probable situation is that just
starting again the software with the same input will work. In the unlikely
situation that it still fails, changing the system of coordinates by doing a
random linear change of projective coordinates and by computing the curve
equation and the divisors in this new coordinate system may work. Finally, if
none of this works, this means that we are in the very unlikely case where all
the possible denominators which could be returned by the interpolation function
vanish at singular points of the curve (this case cannot occur if the curve is
smooth). In this case, please use another model of the curve.
1. `rrspace`: the program `rrspace` computes the Riemann-Roch space associated
to a given divisor D on a curve q. It reads its input on the standard input,
and it returns a basis of the Riemann-Roch space on the standard output.
The format for its input (see next section for more details) is
```
```
where `` represents a divisor whose support does not contain any
singular point of the curve.
It outputs the following data:
* the dimension D of the Riemann-Roch space;
* a denominator h, which is a bivariate polynomial;
* a list of D bivariate polynomials `f_1, ..., f_D`.
The set of rational functions `{f_1/h, ..., f_D/h}` is a basis of the
Riemann-Roch space.
2. `class_grp_arith`: this program takes as input two elements of the divisor
class group of a curve `C` of genus `g` and it returns a representation of the sum. Here, we
are given a curve, together with a degree 1 divisor on `C`. A class of divisors
(modulo principal divisors) is represented by an effective divisor `D1` of degree
`g`: it represents the class of divisors equivalent to the degree-0 divisor `D1 -
g*O`.
`class_grp_arith` reads its input on the standard input, and it returns an
effective divisor of degree at most `g` on the standard output.
The format for its input (see next section for more details) is
```
```
The divisor provided on the 4th line must have degree 1. The two effective
divisors `D1` and `D2` provided on the last two lines must have degree ``.
The supports of all the divisors must not contain any singular point of the
curve.
The program returns a representation of a degree-g effective divisor `D3` such that
`(D1-g*O) + (D2-g*O) = (D3-g*O)` in the divisor class group of `C`.
3. `tests`: this software does not take any input. It just runs two tests: one
for the computation of Riemann-Roch spaces, and one for the arithmetic in the
divisor class group of a smooth quartic curve. It should output the string
`OK`.
III - Data structures
---------------------
This section details the data structures for the input of the programs
described in Section II.
* ``: a prime number `p`
* ``: a bivariate polynomial `q = sum_{i=0}^d q_i(x)*y^i`, where for all `i`,
`q_i` is a polynomial of degree at most `d-i`. The program requires that `q_d(x) = 1`.
The polynomial `q` is encoded as follows
```
[ [ ... ] ]
```
where `` is the degree of the curve and `` is the list of coefficients
of the polynomial `q_i`. For instance if `q_i(x) = sum_{j=0}^{r} q_{i,j} x^j`,
then `` should be
```
[ q_{i,0} q_{i,1} ... q_{i,r} ]
```
* ``: the genus of the curve `C` described by the polynomial `q`. We decline all
responsability on the behavior of the programs if `g` is not the genus of the
curve.
* ``: an effective divisor on `C` represented by two univariate
polynomials
```
< >
```
Each polynomial is described by the list of its coefficients `[ f_0 f_1 ... f_l ]`
These two polynomials (referred to as `f(X)`, `g(X)`) should satisfy the following
equality: `q(X, g(X)) mod f(X) = 0`.
They represent the effective divisor which is the sum of points `(\alpha, \beta)`
with multiplicity `\gamma` where `\alpha` is a root of multiplicity `\gamma` of `f(X)`
and `\beta = g(\alpha)`.
* ``: a divisor `D` on the curve `C` represented by two effective divisors `D_+`
and `D_-` such that `D = D_+ - D_-`
```
{ }
```