README.md 5.84 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 39 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 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 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
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  
./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 

   ```
   <PRIME>  
   <CURVE>  
   <DIVISOR>
   ```

   where `<DIVISOR>` 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

   ``` 
   <PRIME>  
   <CURVE>  
   <GENUS>  
   <DIVISOR>  
   <EFFECTIVEDIVISOR>  
   <EFFECTIVEDIVISOR>  
   ```

   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 `<GENUS>`.
   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.

* `<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> }
  ```