Project topics and materials
Get Complete Project Material File(s) Now! »
Algebraic Complexity and duality
The complexity of algebraic algorithms is often more easily described in a non-Turing model where one assumes that any algebraic operation can be done in a unit of time and any other operation is free. Algebraic complexity studies precisely the computational models that behave this way.
For algorithms over finite rings, the algebraic complexity gives a precise esti-mate for the complexity in the Turing or RAM model (also called binary models). For other rings, the algebraic estimate may be way off target, but it can nevertheless give useful information.
In this chapter we study models that allow one to study the algebraic complex-ity of linear operators. We first present the arithmetic circuit, then the straight line program. Because of their algebraic structure, these models support some algebraic manipulations. Our principal interest will be the transposition theorem, stating that it is possible to apply classical duality (in the sense of Section 1.1.3) to programs, while preserving some complexity invariants. The interest for the transposition theorem comes from the applications we have seen in Section 2.2.8 and other more advanced applications that we will see in the next chapters.
Finally, in Section 3.4, we study the relationship between the transposition theorem and the classical theory of automatic differentiation.
Arithmetic circuits
In this section we briefly present the arithmetic circuit model. Since we have in mind applications to the theory of transposition, our presentation slightly deviates from textbooks; for a more classical and extensive treatment see [BCS97b, Vol99].
Basic definitions
In the whole chapter, by R we shall denote a (non necessarily commutative) ring with unit. Unless otherwise stated, we consider Rn with its natural structure of left R-module; when needed, we shall use kets jxi to remove any ambiguity about the fact that we are talking about elements of a left module. We set R0 = 0, the zero module, and we denote by ? (or j?i) its unique element.
The dual space (Rn) = hom(Rn, R) has a natural structure of right R-module (equivalently, of left Rop-module) by the assignment h‘j a : jxi 7!h‘jxi a, (3.1)
where we have used bras to denote elements of (Rn) and a bracket to denote the natural bilinear form that results by applying linear forms to elements.
Definition 3.1 (Arithmetic operator, arity) An arithmetic operator over R is a morphism of left modules f : Ri ! Ro for some i, o 2 N. Here i is called the in-arity of f or simply arity, o is called the out-arity of f.
Definition 3.2 (Arithmetic basis) An arithmetic R-basis is a (not necessarily finite) set of arithmetic operators over R. A basis is said to be commutative if all its opera-tors are invariant under the natural action of Sn over Rn (i.e. under permutation of coordinates).
Arithmetic circuits are directed acyclic multigraphs carrying information from an arithmetic basis; the formal definition follows.
Definition 3.3 (Arithmetic node) Let B be an R-basis. A node over (R, B) is a tuple v = (I, O, f) such that
• I and O are finite ordered sets,
• f is either an element of B or the special value ;.
• If f = ;, one of the two following conditions must hold:
– I is a singleton and O is empty, in this case we say that v is an input node;
– I is empty and O is a singleton, in this case we say that v is an output node.
• If f 6= ;, the cardinality of I matches the in-arity of f and the cardinality of O matches the out-arity of f; in this case we say that v is an evaluation node.
We call input ports the elements of I and output ports the elements of O, which we denote respectively by in(v) and out(v). The cardinalities of I and O are called, respectively, the in-degree and out-degree of v. We call f the value of v and write (v) for it.
Nodes over the linear basis are pictured in Figure 3.1.1. We do not explicitly represent the orderings on in(+) and out(&) because they are not relevant for the linear basis: in fact, all operators are commutative.
Definition 3.4 (Arithmetic circuit) Let B be an R-basis. A (linear) arithmetic circuit over (R, B) is a tuple C = (V, E, 6, 6i, 6o) such that
1. V is a finite set of nodes over (R, B);
2. < is a total order on V, <i is a total order on the input nodes in V, <o is a total order on the output nodes in V;
U implies U 2 2 0 0
3. let I = v2V in(v) and O = v2V out(v), then E is a bijection from O to I
such that E(o) = i that o out(v), i in(v ) and v v .
In practice, the definition says that C is a directed acyclic multigraph (also called multiDAG), where V are the vertices, E the edges, and where the degrees of each vertex are prescribed by the arities of the underlying arithmetic node. Moreover, we add an ordering on input nodes (vertices of in-degree 0) and on output nodes (vertices of out-degree 0).
In what follows, we shall call (V, E) the underlying graph of C, and use classic graph theoretic terms to refer to its properties. We shall often implicitly make this identification. Thus, we shall represent E as a set of edges (o, i), and make use of the classic concepts of incident edge, nodes connected by an edge, paths, etc.
Figure 3.2 shows two examples of arithmetic circuits. Input and output nodes are ordered from left to right; ports are not ordered because the basis is commuta-tive.
Definition 3.5 (Size, depth) Let C be a circuit over (R, B). The size of C, denoted by size(C) is the number of evaluation nodes in V; the depth of C, denoted by depth(C) is the length of the longest directed path –in a graph-theoretic sense– in (V, E).
Sometimes it is useful to only count certain nodes. Let X B, the X-weighted size of C, denoted by sizeX(C) is the number of nodes v 2 V such that (v) 2 X.
Semantic of a circuit
Circuits would be meaningless if they had no semantic attached to them. Intuitively the semantic corresponds to recursively feed inputs to the nodes, evaluate (v) at the inputs and collect the outputs.
Definition 3.6 (Evaluation of an arithmetic circuit) Let C be an arithmetic circuit with i inputs and o outputs, then its evaluation is a morphism evalC : Ri ! Ro.
In order to define it, we simultaneously define the evaluation evalv of each v 2 V and the evaluation evale of each e 2 E. We will denote by <v the orders on the input and the output ports of v.
• Let v 2 V have out-degree n, let its evaluation be evalv : Ri ! Rn and let 1, . . . , n be the canonical projections from Rn to R. Let o1 <v <v on
be the output ports of v and let ej = oj, E(oj) be the corresponding edges stemming from v, then evalej = j evalv for any j.
• Let x1 <i <i xi be the input nodes and let 1, . . . , i be the canonical projections from Ri to R, then evalxj = j for any j.
• For every evaluation node v with in-degree m, let i1 <v <v im be the input ports of v and let ej = E-1(ij), ij be the corresponding edges incident to v, then evalv = (v) (evale1 , , evalem ). (3.2)
• For every output node y, let e 2 E be the only edge incident to y, then evaly = evale.
We can finally define evalC : Ri ! Ro. Let y1 <o <o yo be the output nodes, then evalC = (evaly1 , , evalyo ) . (3.3)
We also say that C computes evalC.
It is immediate to verify that evalC is a morphism of left modules, because we only used compositions and direct sums to define it. The converse is partially true.
Proposition 3.7 Any morphism of free finite-dimensional R-modules can be computed by an arithmetic circuit over (R, L).
Proof. Take the matrix associated to such morphism and create a circuit that performs the matrix-vector product.
This also gives an upper bound of O(mn) on the circuit size of a linear operator Rm ! Rn.
We now define a way of substituting nodes, first syntactically, then semantically.
Definition 3.8 (Syntactic substitution) Let C = (V, E, 6, 6i, 6o) be a circuit over (R, B) and let C0 = (V 0, E0, 60, 6i0, 6o0) be a circuit over (R, B0). Let C0 have i inputs and o outputs and let v 2 V have in-degree i and out-degree o.
Let I and O be monotone bijections respectively from in(v) to in(C0) and from out(C0) to out(v). We denote by C[C0=v] the circuit (V 00, E00, 600, 6i00, 6o00) over
(R, B [ B0) defined as follows:
• V 00 = V ] (V 0 – in(C0) – out(C0));
• 6i00=6i, 6o00=6o;
• v0 6 v00 if and only if one of the following conditions hold:
– v0, v00 2 V and v0 6 v00;
– v0, v00 2 V 0 and v0 60 v00;
– v0 2 V and v00 2 V 0 and v0 6 v;
– v0 2 V 0 and
>E0(o0)
v00 2 V and v 6 v00;
if E(o) 2 in(v) and I(E(o)) = v0 and out(v0) = fo0g,
• E00(o) = >E(o0)if E0(o) 2 out(C0) and O(E0(o)) = o0, :(E ] E0)(o) otherwise.
Definition 3.9 (Semantic substitution) Let C be a circuit over (R, B [ ffg) and let F be a circuit over (R, B) such that evalF = f.
We denote by C[F=f] the circuit over (R, B) where any node v of C such that (v) = f has been syntactically substituted by F.
The proof of the following proposition is immediate.
Proposition 3.10 Under the conditions of the previous definition, evalC[F=f] = evalC .
As a shorthand notation, we will draw octogones to signify that a node has been syntactically substituted by a circuit, without giving the actual shape of the substituting circuit. Figure 3.1.2 shows an example.
Table of contents :
I Prerequisites
1 Algebra
1.1 Linear algebra
1.2 Basic Galois theory
1.3 Basic algebraic geometry
2 Algorithms and complexity
2.1 Asymptotic complexity
2.2 Fundamental algorithms
II The transposition principle
3 Algebraic Complexity and duality
3.1 Arithmetic circuits
3.2 Multilinearity
3.3 Straight Line Programs
3.4 Automatic differentiation
4 Automatic transposition of code
4.1 Inferring linearity
4.2 transalpyne
III Fast arithmetics using univariate representations
5 Trace computations zero-dimensional ideal
5.2 Trace formulas
5.3 Sitckelberger’s theorem
5.4 Rational Univariate Representation
5.5 The univariate case
5.6 Shoup’s algorithm
5.7 From univariate to bivariate and back again
6 Artin-Schreier towers
6.1 Introduction
6.2 Preliminaries
6.3 A primitive tower
6.4 Level embedding
6.5 Frobenius and pseudotrace
6.6 Arbitrary towers
6.7 Experimental results
IV Applications to isogenies and cryptography
7 Elliptic curves and isogenies
7.1 Definitions
7.2 Curves over C
7.3 Curves over finite fields
7.4 Modular polynomials
8 Computing isogenies over finite fields
8.1 Overview
8.2 Vélu formulas
8.3 BMSS
8.4 Lercier-Sirvent
8.5 Couveignes’ algorithm
8.6 The algorithm C2-AS
8.7 The algorithm C2-AS-FI
8.8 The algorithm C2-AS-FI-MC
8.9 Isogenies of unknown degree
9 Experimental results
9.1 Implementation of Couveignes’ algorithm
9.2 Implementation of C2-UD
9.3 Implementation of Lercier-Sirvent
9.4 Benchmarks
A Categorical considerations
A.1 Categorical semantics of arithmetic circuits
A.2 Coevaluation
A.3 The tranposition theorem
A.4 From circuits to function-level programming
A.5 Self-transposing polynomial multiplication
B Linearity inference of Karatsuba multiplication
C Proof of Vélu’s formulas
Conclusion
List of symbols
Index
Bibliography
