Initial GIT commit

[libg2hec.git] / doc / .svn / tmp / tempfile.tmp

\input texinfo @c -*-texinfo-*-
@c %** start of header 
@setfilename g2hecdoc.info
@settitle The Genus 2 Crypto C++ Library v0.1
@c %** end of header

@c %** Summary description and copyright. Appears only in info file.
@ifinfo
This is a help file for the g2hec library version 0.1.

Copyright @copyright{} 2008 N. Shang.
@end ifinfo
@c %** end of summary description and copyright

@c %** Titlepage, contents, copyright
@titlepage
@title The Genus 2 Crypto C++ Library v0.1
@author Ning Shang

@c The following comments start the copyright page.
@page
@vskip 0pt plus 1filll

Copyright @copyright{} 2008 N. Shang.

@ifnothtml
@c Output the table of contents
@contents
@end ifnothtml

@end titlepage

@c %** end of titlepage, contents, copyright

@c %** Top node and master menu
@c @ifnottex
@node Top, Overview, , 
@top Preface

This manual shows how to install and use the G2HEC (Genus 2 HyperElliptic 
Crypto) C++ Library.


@c @end ifnottex

@menu
* Overview::  Introduction to the g2hec library

* Installation:: Installation instructions

* Quick start::  A web demo of genus 2 scalar multiplication

* Tutorial::  Toy examples

* Genus 2 curve functions::  Curve-related functions

* Divisor functions::  Divisor-related functions

* Divisor arithmetic:: Arithmetic-related functions

* I/O:: Low-level input/output -- what mathematicians care

* Randomness functions:: Random curve, random divisor

* Some issues::
@end menu

@c %** end of top node and master menu

@c %** Body of the document
@node Overview, Installation, Top, Top
@chapter Overview
@section What is G2HEC?
The G2HEC (Genus 2 HyperElliptic Curve) library is a free portable C++ library 
providing divisor group operations in the Jacobian of genus 2 (imaginary) 
hyperelliptic curve.  Such curves can be used for discrete-logarithm-based 
cryptosystems with advantages over elliptic curves (genus 1 curves).  Divisor 
group operations are essential to using genus 2 curves for cryptography.

@c %** line break
@*
It is built on top of V. Shoup's NTL library, "a high performance, portable C++
library providing data structures and algorithms for arbitrary length integers;
for vectors, matrices, and polynomials over the integers and over finite
fields; and for arbitrary precision floating point arithmetic."  

@*
It is recommended to build NTL using GMP (the GNU Multi-Precision package) for
best performance.  However, the G2HEC library can be built and used with and
without the existence of GMP.  

@*
This library does not assume users' familiarity with any non-trivial math
background except basic concepts of finite fields and polynomials.  No prior 
knowledge of genus 2 curve is needed to used the library.

@*
The G2HEC library is released under the GNU General Public License.  See the
file COPYING for details.
 
@*
The G2HEC library homepage: @uref{http://www.math.purdue.edu/~nshang/g2hec/}.

@*
The NTL library homepage: @uref{http://www.shoup.net/ntl/}.

@*
The GMP library homepage: @uref{http://www.swox.com/gmp/}.

@section Genus 2 curve basics
Our object of interest, a genus 2 curve, is a nonsingular algebraic curve 
@center @math{C: y^2 + h(x)y = f(x)}
over a finite field @math{GF(q)}, where @math{f(x)} is monic (i.e., 
has leading coefficient 1) of degree 5, @math{h(x)} has degree not greater
than 2, @math{q} is a prime or a power of a prime.

@*
Currently (version 0.1) G2HEC only supports odd prime @math{q} by default. 
You can ``hack'' the header file in @code{include/g2hec_nsfieldtype.h} to 
switch its support to @math{q} as a power of an odd prime.  However, we do not 
recommend to do so and it should be avoided except in extreme cases. So far 
the library is tested only for odd prime numbers @math{q}.

@*
There is currently no ``hack'' to have field types @code{GF2} and @code{GF2E}
supported (curve singularity test does not work for characteristic 2 yet).  
Support for characteristic 2 maybe added in the future.

@*
A pair @math{(x_0, y_0)} with @math{x_0, y_0\in GF(q)} such that 
@math{x = x_0} and @math{y = y_0} give a solution to the curve equation of
@math{C} is called a @b{@math{GF(q)}-rational point of the genus 2 curve 
@math{C}}.
Obviously, @math{C} has only finitely many @math{GF(q)}-rational points.  
Unlike the case of elliptic curves, the set of @math{GF(q)}-rational points 
of the curve @math{C} does not naturally hold a group structure, therefore they
cannot be used directly to do discrete-logarithm-based cryptography. 
Instead, we choose to use the @b{@math{GF(q)}-rational points of the Jacobian} 
of the curve
@math{C}, which is a finite group, to achieve our (cryptographic) goal. 
It is not necessary for the users of the G2HEC library know how the Jacobian
of a genus 2 curve is defined, given the following two facts:
@enumerate
@item
The @math{GF(q)}-rational points of the Jacobian of a genus 2 curve @math{C},
@math{Jac(C, GF(q))}, is a finite group of size approximately @math{q^2}.

@item
An element of @math{Jac(C, GF(q))} is called a @b{divisor class} (@b{divisor}
in short) over @math{GF(q)}. A divisor (class) @math{D} is represented by a 
pair of polynomials @math{[u(x), v(x)]} over @math{GF(q)}. Several conditions
need to be satisfied for a pair @math{[u(x), v(x)]} to be a divisor of 
@math{C}.
@end enumerate

@*
The unit element of @math{Jac(C, GF(q))} is @math{[1, 0]}.

@*
By convention, the group operation in the Jacobian of the curve @math{C} is 
written additively. We shall write 
@center @math{D=D_1+D_2, D=D_1-D_2, D=[n]D_1}
for @b{divisor addition, divisor subtraction} and @b{divisor scalar 
multiplication}, respectively, where @math{D=[n]D_1} means 
@math{D=D_1+D_1+...+D_1} for @math{n} times.
 
@*
More information about the math background of the Jacobian of genus 2 curves 
can be found in the book ``Handbook of Elliptic And Hyperelliptic Curve 
Cryptography'' by Cohen et al.

@* 
In addition to the high-level functions that operates on curves and divisors, 
the G2HEC library also exports low-level functions that allow knowledgeable 
users to take control of mathematical factors of curves and divisors. Our 
intent is to make the library useful for both mathematicians and cryptographers
(or the ones who play both roles).


@node Installation, Quick start, Overview, Top
@chapter Installation

The G2HEC library is dependent of V. Shoup's NTL library, which can be found at
@uref{http://www.shoup.net/ntl/, NTL: A Library for doing Number Theory}.

@*
The following procedure should work on Unix and Unix-like platforms. The 
installation has been tested on Linux and Solaris.

@*
To obtain the source code and documentation for G2HEC, download 
@uref{http://www.math.purdue.edu/~nshang/g2hec/, g2hec-lib-xxx.tar.gz}. 
Here ``xxx'' denotes the current version number.

@section General installation instructions
If the NTL library is installed in a standard system directory, then do the
following:

@example
% gunzip g2hec-lib-xxx.tar.gz
% tar xvf g2hec-lib-xxx.tar
% cd g2hec-lib-xxx
% ./configure --prefix=$HOME/nssw
% make
% make check
% make install
@end example

@*
This will build, test and install G2HEC in @code{$HOME/nssw}.  You can change 
to a different location by specifying it with the  @code{--prefix=} option (the
default is @code{/usr/local}).  After installation, you will find the G2HEC 
header files in 
@code{$HOME/nssw/include} and the compiled static library @code{libg2hec.a} in 
@code{$HOME/nssw/lib/}.

@section NTL not in default location
If you have installed the NTL/GMP libraries into locations which require
special include or library paths, you can pass them to @code{LDFLAGS} and 
@code{CXXFLAGS} variables for the configure script.
For example (for bash)

@example
% env LDFLAGS=-L$HOME/nssw/lib CXXFLAGS=-I$HOME/nssw/include ./configure
--prefix=$HOME/nssw
@end example

@*
Depending on whether GMP is found in the search path or not, the G2HEC library 
is configured to build with or without GMP.

@section After G2HEC is built
After the library is built, executing @code{make check} runs some test 
programs.

@*
It is highly recommended to do this to make sure things went well.

@*
Executing @code{make install} copies a number of files to a directory 
@code{<prefix>} 
that you specify by passing @code{--prefix=<prefix>} as an argument 
to @code{configure} at configuration time, or as an argument to 
@code{make install} at installation time.  Recall that the default is
@code{/usr/local}.

@*
To uninstall the library, execute @code{make uninstall}.

@*
To remove object files, execute @code{make clean}.

@*
Note that this installation process is almost standard.

@*
Assuming you have installed G2HEC as above, to compile program @code{myprog.C}
that uses G2HEc, do

@example
% g++ -I<prefix>/include -I<ntl_prefix>/include -L<prefix>/lib \
-L<ntl_prefix>/lib myprog.c -o myprog -lg2hec -lntl -lm
@end example

@*
The binary file @code{myprog} is created.

@*
If you built NTL using GMP, do

@example
% g++ -I<prefix>/include -I<ntl_prefix>/include -L<prefix>/lib \
-L<ntl_prefix>/lib -L<gmp_prefix>/lib myprog.c -o myprog -lg2hec \
-lntl -lgmp -lm
@end example

@*
Of course, there is no need to duplicate the flags if some of the locations are
the same, and you may leave out the corresponding flags if the locations are
standard directories.

@node Quick start, Tutorial, Installation, Top
@chapter Quick start

@section A web demo of divisor scalar multiplication
You can play around with divisor scalar multiplication on the following demo
page:
@center @uref{http://www.math.purdue.edu/~nshang/g2hec/demo.html}.

@*
This demo page shows an application built on top of the G2HEC library.  
Although you may smell a bit of mathematics from this demo, in general
programmers can build cryptographic algorithms/protocols without knowing
any college-level math.

@node Tutorial, Genus 2 curve functions, Quick start, Top
@chapter Tutorial
We shall walk you through several cryptographic applications of G2HEC.

@section HEC-Diffie-Hellman key exchange
The basic Diffie-Hellman key exchange protocol works as follows:

@*
Alice and Bob wish to agree on a secret random element over an insecure channel
without having to exchange any information previously.  

@*
They agree on an element @math{P} in the Jacobian of the genus 2 curve 
@math{C} with a large (known or unknown) order @math{G}.
@enumerate
@item
Alice generates a random integer @math{a \in @{1, \ldots, \#G - 1@}}, then
sends to Bob the element (divisor) 
@center @math{Q_1 = [a] P}.

@item
Bob generates a random integer @math{b \in @{1, \ldots, \#G - 1@}}, then
sends to Alice the element (divisor)
@center @math{Q_2 = [b] P}.

@item
Alice then computes
@center @math{[ab] P = [a] Q_2}.

@item
Similarly, Bob computes
@center @math{[ab] P = [b] Q_1}.
@end enumerate

@*
This element @math{[ab] P} now serves as the secret that only Alice and Bob 
know.

@*
We illustrate a local version of this protocol using a genus 2 curve over a 
prime field @math{GF(p)}, for an educational purpose.

@*
First we include the header file g2hec_Genus2_ops.h:
@example
#include <g2hec_Genus2_ops.h>
@end example

@*
Then we define the maximum length (in decimal digits) of the prime number
@math{p} to be 300:
@example
#undef MAX_STRING_LEN
#define MAX_STRING_LEN 300
@end example

@*
The following statement invokes the namespace used by the G2HEC library, and
must be present for every client program.
@example
NS_G2_CLIENT
@end example 

@* 
In the main function, we first set the pseudo-random number generator seed, and
allocate a string buffer for receiving a prime number
input by the user:
@example
SetSeed(to_ZZ(1234567890));
char p[MAX_STRING_LEN];

cin.getline(p, MAX_STRING_LEN);
@end example

@*
We declare and initialize an NTL big integer object @code{pZZ} to store this
prime number:
@example
ZZ pZZ = to_ZZ(p);
@end example

@*
Now we initialize the underline prime field @math{GF(p)}:
@example
field_t::init(pZZ);
@end example

@* 
We shall declare and initialize several elements to hold the genus 2 curve,
system parameters, keys and so on:
@example
ZZ a, b;
g2hcurve curve;
divisor P, Q1, Q2;
@end example

@*
Generate a random valid genus 2 curve:
@example
curve.random();
@end example

@*
Set curve for the divisors.  A curve needs only to be set once in a program
to work for all divisors.
@example
P.set_curve(curve);
@end example

@*
To perform Diffie-Hellman key exchange, it is not necessary to know the order 
of @math{P}.  A fact is that this order is close to  @math{p^2}. So we choose
@math{a} and @math{b} to be two random number bounded by @math{p^2}.
@example
RandomBnd(a, pZZ*pZZ);
RandomBnd(b, pZZ*pZZ);
@end example

@*
We generate a random base point @math{P}:
@example
P.random();
@end example

@*
Alice computes
@example
Q1 = a * P;
@end example

@*
Bob computes
@example
Q2 = b * P;
@end example

@*
A successful key exchange should yield the shared secret 
@center @math{[ab]P = [a] Q_2 = [b] Q_1}:
@example
if ( b * Q1 == a * Q2)
  cout << "DH key exchange succeeded!" << endl;
else
  cout << "DH key exchange failed!" << endl;
@end example

@*
A complete source file for this example can be found in @code{example/dh.C}.

@section HEC-ElGamal encryption
This example is similar to the Diffie-Hellman key exchange example.  Please 
refer to the source file in @code{examples/elgamal_enc.C} for details.

@section HEC-ElGamal digital signature
We shall use G2HEC to build a digital signature scheme: the ElGamal digital 
signature.

@*
Recall how this signature scheme works:

@*
Bob chooses a genus 2 curve @math{C} and a prime number @math{p} so that the
number of @math{GF(p})-rational points of the Jacobian of @math{C} has a large
prime factor @math{N} -- preferably the number itself is prime. He then chooses
a divisor @math{g} of order @math{N}, a secret private key @math{x\in\{1, 
\ldots, N - 1\}}, then computes a divisor @math{h = [x] g}. Bob publishes 
@math{g} and @math{h} as his public key.

@*
To sign a message @math{m \in Z/(N)}, Bob first generates a random integer
@math{i \in @{1, \ldots, N - 1@}}, and computes
@center @math{a = [k] g}.

@*
Bob then computes a solution, @math{b \in Z/(N)} to the congruence
@center @math{m @equiv{} x f(a) + b k (mod N) }.
Here @math{f} is a map from the Jacobian of @math{C} to @math{Z/(N)} which
is almost injective.

@*
Bob sends the signature @math{(a, b)} together with the message @math{m} 
to Alice.

@*
Upon receiving the message and signature from Bob, Alice verifies the signature
by checking that 
@center @math{[f(a)] h + [b] a = [m] g}
holds.

@*
It needs to be point out that a technical aspect of this algorithm involves
the choice of the curve @math{C} and the prime number @math{p} so that its
Jacobian has an order divisible by a large prime number.  This is not a 
trivial task -- it involves quite amount of mathematics.  Fortunately, there
are published data that users can use directly to avoid this difficulty.
According to the paper ``Construction of Secure Random Curves of Genus 2
over Prime Fields'' by Gaudry and Schost, we choose to use in our example
the curve
@tex
$$C: y^2 =  x^5 + 2682810822839355644900736 x^3 
 + 226591355295993102902116 x^2
$$
$$ + 2547674715952929717899918 x 
+ 4797309959708489673059350$$
@end tex
with @math{p =  5 \cdot 10^{24} + 850349}.  The order of the Jacobian of the
curve is a prime number
@center @math{N = 2499999999999413043860099940220946396619751607569,}
which is to our best interest.  In this case, we can pick any random non-unit
divisor @math{g} as our base point.

@*
At this point, we are able present a local version of this signature scheme.

@*
As usual we include the header file @code{g2hec_Genus2_ops.h}:
@example
#include <g2hec_Genus2_ops.h>
@end example

@*
Then we define some macros that we are going to use, including the values of
coefficients of the polynomial @math{f}, the prime number @math{p}, the group 
order of the Jacobian, and a function that maps a suitable value to an NTL 
@code{ZZ_p} object.

@example
#define f3 "2682810822839355644900736"
#define f2 "226591355295993102902116"
#define f1 "2547674715952929717899918"
#define f0 "4797309959708489673059350"
#define ps "5000000000000000008503491"
#define N "24999999999994130438600999402209463966197516075699"

#define str_to_ZZ_p(x) to_ZZ_p(to_ZZ(x))
@end example

@*
Also we issue the statement
@example
NS_G2_CLIENT
@end example

@*
Recall that we need an almost bijection that maps elements in the Jacobian to
an element in @math{@{1, \ldots, N - 1@}}.  This map can be chosen as follows:
@example
static ZZ from_divisor_to_ZZ(const divisor& div, const ZZ& n)
@{
  poly_t u = div.get_upoly();
  ZZ temp = AddMod(sqr(rep(u.rep[0])), sqr(rep(u.rep[1])), n);
  return ( IsZero(temp) ? to_ZZ(1) : temp );
@}
@end example
We just mention that we choose this function to take a divisor 
@center @math{[u(x), v(x)]} 
to the value defined by the sum of the squares of the degree 0 and degree 1
coefficients modulo the group order @math{N} of the Jacobian.  Users can 
define their own such function to use.  Security might be affected by bad
choice of this almost injective function.

@*
We start working on the @code{main} function by initializing the PRNG seed and
declaring and define several values:
@example
  SetSeed(to_ZZ(1234567890));

  ZZ p = to_ZZ(ps);

  field_t::init(p); 

  ZZ order = to_ZZ(N);

  ZZ x, k, b, m; 
  // Private key x, random number k, parameter b, message m

  ZZ f_a;

  g2hcurve curve;

  divisor g, h, a;

  poly_t f;
@end example

@*
Then we manually assign values of polynomial @math{f} and define the 
corresponding genus 2 curve:
@example
  SetCoeff(f, 5, 1);
  SetCoeff(f, 4, 0);
  SetCoeff(f, 3, str_to_ZZ_p(f3));
  SetCoeff(f, 2, str_to_ZZ_p(f2));
  SetCoeff(f, 1, str_to_ZZ_p(f1));
  SetCoeff(f, 0, str_to_ZZ_p(f0));
  curve.set_f(f);
@end example

@*
Then you update the curve information:
@example
curve.update();
@end example
This will update some flags related to properties of the curve, and needs to 
be done immediately after manual assignments to the curve's defining elements
(e.g., the polynomial @math{f}).

@*
Now we are ready to set the curve as the underlying curve of the divisors.
@example
g.set_curve(curve);
@end example

@*
We randomly choose the base point @math{g}, message @math{m} to be signed, the 
private key @math{x}, and the public key @math{h}:
@example
  do @{
    g.random();
  @} while (g.is_unit());

  RandomBnd(m, order);

  do @{
    RandomBnd(x, order);
  @} while (IsZero(x));

  h = x * g;
@end example
Note that we want the base point @math{g} to be any divisor except the unit 
divisor, and we do not allow the private key @math{x} to be 0.  This is what
the @math{do...while} statements do.

@*
Now we shall generate the ElGamal signature @math{(a, b)}:
@example
  do @{
    RandomBnd(k, order);
  @} while (IsZero(k));

  a = k * g;

  f_a = from_divisor_to_ZZ(a, order);

  /* b = (m - x*f(a))/k mod N */
  b = MulMod(m - x * f_a, InvMod(k, order), order);
@end example
The element @code{f_a} holds the value @math{f(a)} given by the almost 
injection applied to the divisor @math{a}.

@* 
Alright!  Now the most exciting moment has arrived -- signature verification:
@example
  if ( f_a * h + b * a == m * g )
    cout << "ElGamal signature verification succeeded!" << endl;
  else
    cout << "ElGamal signature verification failed!" << endl;
@end example


@* 
The complete source file can be found in @code{examples/elgamal_sig.C}.

@*
**************************************************************@*
In the following chapters, we will give a general overview of the G2HEC's 
programming interface. This includes:
@itemize
@item
Functions related to genus 2 curve generation and manipulation

@item
Functions related to divisor generation and manipulation

@item
Divisor arithmetic functions

@item
Input and output functions

@item
Randomness functions

@c @item
@c Miscellaneous functions
@end itemize

All these interfaces are exported by @code{include/g2hec_Genus2_ops.h} unless
otherwise specified.
@noindent
**************************************************************

@node Genus 2 curve functions, Divisor functions, Tutorial, Top
@chapter Genus 2 curve functions
We only consider the so-called ``imaginary'' genus 2 curves, i.e., curves given
by the equation
@center @math{C: y^2 + h(x) y = f(x),}
with @math{\deg{h}\le 2} and @math{\deg{f} = 5}.  We also require that 
@math{C} 
be nonsingular and the leading coefficient of @math{f(x)} be 1. 

@*
Types @code{field_t} and @code{poly_t} are for the field element 
type and the corresponding polynomial type, respectively. They are defined 
in the header file @code{include/g2hec_nsfieldtype.h}. Type @code{poly_tc}
is the type @code{const poly_t}.

@*
A genus 2 curve is stored in the @code{g2hcurve} class.

@*
Below are some of the class's public member functions. They are exported in
the file @code{include/g2hec_Genus2_ops.h}.

@*
@code{g2hcurve()}: @*
default constructor; set curve to @math{y^2 = 0}.

@*
@code{g2hcurve(const poly_tc& poly1, const poly_tc& poly2)}: @*
constructor; sets curve to @math{y^2 + @code{poly2}*y = @code{poly1}}.

@*
@code{g2hcurve(const g2hcurve& hcurve)}: @*
copy constructor.

@*
@code{void set_f(const poly_tc& poly)}: @*
sets @math{f(x)} to @code{poly}.

@*
@code{void set_h(const poly_tc& poly)}: @*
sets @math{h(x)} to @code{poly}.

@*
@code{void update()}: @*
checks and set internal flags to determine whether
the curve is nonsingular and of genus 2.  This function MUST be called 
immediately after the curve has been changed by @code{set_f()},
@code{set_h()}, or/and assignment, and before any further operations 
related to the curve. This is very important to remember, otherwise error 
may occur.

@*
@code{const poly_tc& get_f()}: @*
returns reference to polynomial @math{f(x)}.

@*
@code{const poly_tc& get_h()}: @*
returns reference to polynomial @math{h(x)}.

@*
@code{bool_t is_valid_curve()}: @*
returns TRUE is curve is nonsingular, genus 2, and @math{f(x)} is monic.

@*
You can also write @code{curve1 = curve2} naturally to set the value of 
@code{curve1} to be the same as @code{curve2}. It is not needed that 
@code{curve2} be valid for this assignment.

@*
You can do comparisons like
@code{curve1 == curve2} or @code{curve1 != curve2} to test if two curves
are the same.  Curves do not need to be valid for these comparisons.

@node Divisor functions, Divisor arithmetic, Genus 2 curve functions, Top
@chapter Divisor functions
A divisor (class) is a pair of polynomials @math{[u(x), v(x)]} over 
@math{GF(q)}
with @math{\deg{v}<\deg{u}\le 2} so that they satisfy certain conditions 
related to the curve @math{C}.  Therefore, every divisor (class) has a 
curve to associate with.  G2HEC use a C++ class @code{divisor} to hold
a divisor.

@*
For cryptographic purposes, G2HEC does not support the existence of divisors 
associated with different curves in the same running process. It implements
the associated genus 2 curve as a static data member of the @code{divisor} 
class.  The client program only needs to set the curve once for a divisor, and
it works for all divisors.  A curve change for one divisor in a program will
cause all divisors in the same program to switch to the new curve.  This is
another important convention of G2HEC.

@*
We list some of the @code{divisor} class's public member functions as follows.

@*
@code{divisor()}: @*
default constructor; sets @math{u(x) = 1, v(x) = 0}, and associated curve
as @math{y^2 = 0}. A divisor is not valid by default.

@*
@code{divisor(const poly_tc& polyu, const poly_tc& polyv, const g2hcurve& curve)}: @*
constructor; set @math{u(x) = }@code{polyu}, @math{v(x) = }@code{polyv}, and 
associated curve to @code{curve}.

@*
@code{divisor(const divisor& div)}:@*
copy constructor.

@*
@code{void set_upoly(poly_tc& poly)}: @*
sets @math{u(x)} to @code{poly} for the divisor.

@*
@code{void set_vpoly(poly_tc& poly)}: @*
sets @math{v(x)} to @code{poly} for the divisor.

@*
@code{void set_curve(const g2hcurve& curve)}: @*
sets the associated curve to @code{curve} for divisor.  The curve does
not need to be a valid genus 2 curve.

@*
@code{void update()}: @*
This function checks and updates information related to the divisor.  It must 
be called by a client program after any @code{set_} routine is called. 
Otherwise error make occur when operations on divisor are performed.

@*
@code{const poly_tc& get_upoly()}: @*
returns @math{u(x)} of the divisor.

@*
@code{const poly_tc& get_vpoly()}: @*
returns @math{v(x)} of the divisor.

@*
@code{const g2hcurve& get_curve()}: @*
returns the associated curve of the divisor.

@*
@code{bool_t is_valid_divisor()}: @*
returns @code{TRUE} is the representation of the divisor is valid, @code{FALSE}
otherwise.

@*
@code{bool_t is_unit()}: @*
tests if the divisor is the unit divisor @math{[1, 0]}.

@*
@code{set_unit()}: @*
sets the divisor to the unit divisor @math{[1, 0]}.

@*
You can write @code{divisor1 = divisor2} to assign the value of @code{divisor2}
to @code{divisor1}.  @code{divisor2} can be either valid or invalid.

@*
You can do comparisons like @code{divisor1 == divisor2} or 
@code{divisor1 != divisor2} to test if two divisors are the same. Divisors
do not need to be valid for such comparisons.

@*
There is also a non-member function 
@center @code{bool_t on_same_curve(const divisor& a, const divisor& b)}
that tests if two divisors @code{a} and @code{b} have the same associated
curve.  According to the way G2HEC implements the @code{divisor} class,
this function always returns @code{TRUE}. Therefore this test is redundant.

@node Divisor arithmetic, I/O, Divisor functions, Top
@chapter Divisor arithmetic
The divisor operations are @b{addition, negation, subtraction} and 
@b{scalar multiplication}.

@*
The divisor arithmetic is implemented using the @b{explicit formulas}, which 
is supposed to be faster than the generic one via @b{Cantor's algorithm}, for
the most common cases of the divisor operations.  The Cantor's algorithm is
also implemented in G2HEC and used to handle special cases that rarely happen
in cryptographic applications.

@*
The interfaces for divisor arithmetic are strait-forward.  We list them in 
below in both their procedure and operator version (if both version exist).

@*
@code{bool_t add_cantor(divisor& x, const divisor& a, const divisor& b)}:@*
This is the Cantor's algorithm which computes @code{x = a + b}.

@*
@code{bool_t add((divisor& x, const divisor& a, const divisor& b)},@*
@code{divisor operator+(const divisor& a, const divisor& b)}: @*
compute @code{x = a + b} via explicit formulas; special cases handled by 
calling @code{add_cantor()}.

@*
@code{bool_t sub((divisor& x, const divisor& a, const divisor& b)},@*
@code{divisor operator-(const divisor& a, const divisor& b)}: @*
compute @code{x = a - b}.

@*
@code{bool_t dnegate(divisor& x, const divisor& a)}, @*
@code{divisor operator-(const divisor& a)}: @*
compute @code{x = -a}.

@*
@code{scalar_mul(divisor& x, const divisor& a, const ZZ& n,  bool_t (*method)(divisor&, const divisor&, const ZZ&))}, @*
@code{scalar_mul(divisor& x, const divisor& a, long n,  bool_t (*method)(divisor&, const divisor&, const ZZ&))}: @*
compute @code{x = [n]a} using a method specified by @code{method}.  Currently,
three methods are provided by G2HEC:
@enumerate
@item
@code{SAM}: sum-and-square method

@item
@code{NAF}: method using non-adjacent forms

@item
@code{ML}: method of the @b{Montgomery's ladder}; used to resist side-channel 
attacks.
@end enumerate
@*
Setting @code{method} to @code{NULL} performs scalar multiplication via 
@code{SAM}.


@*
@code{divisor operator*(const ZZ& n, const divisor& a)}, @*
@code{divisor operator*(const divisor& a, const ZZ& n)}, @*
@code{divisor operator*(long n, const divisor& a)}, @*
@code{divisor operator*(const divisor& a, long n)}: @*
return @code{[n]a}. @code{SAM} is used for scalar multiplication.

@node I/O, Randomness functions, Divisor arithmetic, Top
@chapter I/O
G2HEC exports several functions to output of polynomials, curves and divisors.
They might be more useful for mathematics research on genus 2 curves over 
finite fields than for implementation of cryptographic protocols.  For sake of 
completeness, we briefly introduce them here.

@*
@code{void print_poly(poly_t& poly, std::ostream *s)}: @*
directs a natural representation of polynomial @code{poly} to @code{s}. 

@* 
For example, calling @code{print_poly(f, cout)} will display in the standard
output
@example
x^5 + 3*x^2 + x
@end example
if @code{f} is a @code{poly_t} object representing 
@math{f(x) = x^5 + 3 x^2 + x}.

@*
Calling @code{cout << curve; } will display in the standard output 
something like
@example
Curve: y^2 + h(x)*y = f(x)
       h(x) = 0
       f(x) = x^5 + 1
       Genus 2 curve is nonsingular

@end example
if @code{curve} is a valid genus 2 curve, or 
@example
Curve: y^2 + h(x)*y = f(x)
       h(x) = 0
       f(x) = x^2
       Curve is singular, or not genus 2, or f(x) is not monic

@end example
if @code{curve} is not valid.

@*
Calling @code{cout << divisor; } will display in the standard output
something like
@example
###
Divisor [u(x), v(x)] for Jacobian group of curve y^2 + h(x)*y = f(x).
Curve: y^2 + h(x)*y = f(x)
       h(x) = 0
       f(x) = x^5 + 1
       Genus 2 curve is nonsingular
[u(x), v(x)]:
       u(x) = 1
       v(x) = 0
       Divisor is valid
###

@end example
if @code{divisor} is a valid divisor, or
@example
###
Divisor [u(x), v(x)] for Jacobian group of curve y^2 + h(x)*y = f(x).
Curve: y^2 + h(x)*y = f(x)
       h(x) = 0
       f(x) = x^5 + 1
       Genus 2 curve is nonsingular
[u(x), v(x)]:
       u(x) = 1
       v(x) = x
       Divisor is invalid
###

@end example
if @code{divisor} is not valid.

@node Randomness functions, Some issues, I/O, Top
@chapter Randomness functions
The G2HEC library uses NTL's pseudo-random number generator for generating
functions that output random values.  It is recommended to override the 
default seed by calling
@center @code{NTL::SetSeed( seed )} 
to set the PRNG seed using a @code{ZZ} object @code{seed} if you are to
do serious cryptographic applications which use the G2HEC's randomness 
functions.

@*
The G2HEC library exports in @code{include/g2hec_rand.h} a function 
@center @code{ZZ g2hec_rand()},
which obtains a random @code{ZZ} object of 128-bit integer by trying
to use the file /dev/urandom as a source of random bits; if it fails, 
then 0 is returned.

@*
User can set its own random seed, or call 
@center @code{NTL::SetSeed(g2hec_rand())}
to generate one.

@*
The class @code{g2hcurve} has a member function to generate a random 
valid genus 2 curve.

@*
@code{g2hcurve& random()}: @*
generates a random valid genus 2 curve.

@*
The class @code{divisor} has two member functions to generate random
valid divisors, if the associated curve is valid.

@*
@code{divisor& random()}: @*
If the associated curve is valid, sets the divisor to a random valid
divisor of degree 2, i.e., @math{\deg{u} = 2}.

@*
@code{divisor& random(divdeg_t dgr)}: @*
If the associated curve is valid, sets divisor to a random valid divisor
of degree @code{dgr}, where @code{dgr} takes values 1 (DEGREE_1) or
2 (DEGREE_2).

@*
Note that @code{divisor.random()} never returns a unit divisor @math{[1, 0]}.

@node Some issues, , Randomness functions, Top
@chapter Some issues

Most functions in the G2HEC are reentrant, with exception of functions
that set the associate curve for a divisor, such as
@code{divisor::set_curve} and a constructor of the @code{divisor} class.
It is considered an unchecked programming error to change the associated
curve when performing divisor operations.

@c %** end of body of the document

@c %** End of the document

@c %** end of end of the document


@bye