---

7 Divisor arithmetic

The divisor operations are addition, negation, subtraction and scalar multiplication.

The divisor arithmetic is implemented using the explicit formulas, which is supposed to be faster than the generic one via 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).

bool_t add_cantor(divisor& x, const divisor& a, const divisor& b):

This is the Cantor’s algorithm which computes x = a + b.

bool_t add((divisor& x, const divisor& a, const divisor& b),

divisor operator+(const divisor& a, const divisor& b):

compute x = a + b via explicit formulas; special cases handled by calling add_cantor().

bool_t sub((divisor& x, const divisor& a, const divisor& b),

divisor operator-(const divisor& a, const divisor& b):

compute x = a - b.

bool_t dnegate(divisor& x, const divisor& a),

divisor operator-(const divisor& a):

compute x = -a.

scalar_mul(divisor& x, const divisor& a, const ZZ& n, bool_t (*method)(divisor&, const divisor&, const ZZ&)),

scalar_mul(divisor& x, const divisor& a, long n, bool_t (*method)(divisor&, const divisor&, const ZZ&)):

compute x = [n]a using a method specified by method. Currently, three methods are provided by G2HEC:

1. SAM: sum-and-square method
2. NAF: method using non-adjacent forms
3. ML: method of the Montgomery’s ladder; used to resist side-channel attacks.

Setting method to NULL performs scalar multiplication via SAM.

divisor operator*(const ZZ& n, const divisor& a),

divisor operator*(const divisor& a, const ZZ& n),

divisor operator*(long n, const divisor& a),

divisor operator*(const divisor& a, long n):

return [n]a. SAM is used for scalar multiplication.