README.md 6.33 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
rrspace
=======

This software is distributed under LGPL-2.1+ (i.e., LGPL version 2.1 or later).

Please report bugs to <pierre-jean.spaenlehauer@inria.fr>.

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 <PROGRAM>
```

where `<PROGRAM>` 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  
39
./rrspace < example_rrspace_nodal_input  
40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
./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
65 66 67
   to a given divisor D on a smooth or nodal plane curve described by a
   bivariate polynomial q. It reads its input on the standard input, and it
   returns a basis of the Riemann-Roch space on the standard output.
68 69 70 71 72 73

   The format for its input (see next section for more details) is 

   ```
   <PRIME>  
   <CURVE>  
74
   <EFFECTIVEDIVISOR>
75 76 77 78
   <DIVISOR>
   ```

   where `<DIVISOR>` represents a divisor whose support does not contain any
79 80
   singular point of the curve, and `<EFFECTIVEDIVISOR>` represents the effective
   divisor of all the nodes of the curve.
81 82 83 84 85 86 87 88 89

   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.

SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
90
2.  `class_grp_arith`: this program takes as input two elements of the divisor
91 92 93 94 95 96
    class group of a nodal curve `C` of genus `g` with `r` nodes 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` such that its support
    contains no singular point of the curve: it represents the class of divisors
    equivalent to the degree-0 divisor `D1-g*O`.
97 98

   `class_grp_arith` reads its input on the standard input, and it returns an
99
   effective divisor of degree `g+r` on the standard output.
100 101 102 103 104 105
 
   The format for its input (see next section for more details) is

   ``` 
   <PRIME>  
   <CURVE>  
106
   <EFFECTIVEDIVISOR>
107 108 109 110 111 112 113
   <GENUS>  
   <DIVISOR>  
   <EFFECTIVEDIVISOR>  
   <EFFECTIVEDIVISOR>  
   ```

   The divisor provided on the 4th line must have degree 1. The two effective
114 115 116 117 118 119 120 121 122
   divisors `D1` and `D2` provided on the last two lines must have degree
   `<GENUS>`.  The first effective divisor describes all the nodes of the curve.
   The supports of the three last divisors must not contain any singular point of
   the curve.

   The program returns a representation of a degree-`(g+r)` effective divisor
   `D3 ≥ E` such that `(D1-g*O) + (D2-g*O) = (D3-E-g*O)` in the divisor class
   group of `C`, where `E` is the degree-`r` effective divisor representing the
   nodes of the curve.
123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176

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.

* `<PRIME>`: a prime number `p`

* `<CURVE>`: 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
  
  ```  
  [ <DEGREE> [ <q_0> <q_1> ... <q_d> ] ]
  ```
  
  where `<DEGREE>` is the degree of the curve and `<q_i>` 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 `<q_i>` should be
  
  ```  
  [ q_{i,0} q_{i,1} ... q_{i,r} ]
  ```

* `<GENUS>`: 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.
  
* `<EFFECTIVEDIVISOR>`: an effective divisor on `C` represented by two univariate
  polynomials
  
  ```
  < <POLY1> <POLY2> >
  ```
  
  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)`.
  
* `<DIVISOR>`: a divisor `D` on the curve `C` represented by two effective divisors `D_+`
  and `D_-` such that `D = D_+ - D_-`
  
  ```
  { <EFFECTIVEDIVISOR> <EFFECTIVEDIVISOR> }
  ```