BRICS RS-03-8 Damgård & Frandsen: gcd and Cubic Residuosity in the Ring of Eisenstein Integers BRICS

Basic Research in Computer Science

Efficient Algorithms for gcd and Cubic Residuosity in the Ring of Eisenstein Integers

Ivan B. Damgård Gudmund Skovbjerg Frandsen

BRICS Report Series RS-03-8 ISSN 0909-0878 February 2003 Copyright \begin{matrix}c \\ ◯ \end{matrix} 2003, Ivan B. Damgård & Gudmund Skovbjerg

Frandsen. BRICS, Department of Computer Science University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent BRICS Report Series publications. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK–8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@brics.dk

BRICS publications are in general accessible through the World Wide Web and anonymous FTP through these URLs:

http://www.brics.dk
ftp://ftp.brics.dk

This document in subdirectory RS/03/8/

Efficient algorithms for gcd and cubic residuosity in the ring of Eisenstein integers ^{∗}

Ivan Bjerre Damgård Gudmund Skovbjerg Frandsen
BRICS^{†}

Department of Computer Science University of Aarhus Ny Munkegade DK-8000 Aarhus C, Denmark

         {ivan,gudmund}@brics.dk

February, 2003

Abstract

We present simple and efficient algorithms for computing gcd and cubic residuosity in the ring of Eisenstein integers, Z[ζ], i.e. the integers extended with ζ, a complex primitive third root of unity. The algorithms are similar and may be seen as generalisations of the binary integer gcd and derived Jacobi symbol algorithms. Our algorithms take time O(n^{2}) for n bit input. This is an improvement from the known results based on the Euclidian algorithm, and taking time O(n · M(n)), where M(n) denotes the complexity of multiplying n bit integers. The new algorithms have applications in practical primality tests and the implementation of cryptographic protocols. The technique underlying our algorithms can be used to obtain equally fast algorithms for gcd and quartic residuosity in the ring of Gaussian integers, Z[i].

∗Partially supported by the IST Programme of the EU under contract number IST-1999-14186 (ALCOM-FT).

† Basic Research in Computer Science, Centre of the Danish National Research Foundation.

1 Introduction

The Eisenstein integers, Z[ζ] = {a + bζ | a, b ∈ Z}, is the ring of integers extended with a complex primitive third root of unity, i.e. ζ is root of x^{2} + x + 1. Since the ring Z[ζ] is a unique factorisation domain, a greatest common divisor (gcd) of two numbers is welldefined (up to multiplication by a unit). The gcd of two numbers may be found using the classic Euclidian algorithm, since Z[ζ] is an Euclidian domain, i.e. there is a norm N(·) : Z[ζ]\{0} ↦ N such that for a, b ∈ Z[ζ]\{0} there is q, r ∈ Z[ζ] such that a = qb + r with r = 0 or N(r) < N(b).

When a gcd algorithm is directly based on the Euclidian property, it requires a subroutine for division with remainder. For integers there is a very efficient alternative in the form of the binary gcd, that only requires addition/subtraction and division by two [10]. A corresponding Jacobi symbol algorithm has been analysed as well [9].

It turns out that there is a natural generalisations of these binary algorithms over the integers to algorithms over the Eisenstein integers for computing the gcd and the cubic residuosity symbol. The role of 2 is taken by the number 1 − ζ, which is a prime of norm 3 in Z[ζ].

We present and analyse these new algorithms. It turns out that they both have bit complexity O(n^{2}), which is an improvement over the so far best known algorithms by Scheidler and Williams [7], Williams [11], Williams and Holte [12]. Their algorithms have complexity O(nM(n)), where M(n) is complexity of integer multiplication.

1.1 Related work

Scheidler and Williams algorithms may be seen as generalisations of the classic Euclidian gcd and Jacobi algorithms rather than the binary algorithms. However, in the case of integer gcd and Jacobi symbol algorithms, both the Euclidian based and the binary versions have the same asymptotic complexity O(n^{2}) (in their simple versions - there is an asymptotically faster version [8, 1]). This raises the question of why the Scheidler-Williams generalisation does not seem to achieve the complexity O(n^{2}) as well.

For the classic Euclidian algorithm to be fast two observations about the division step (find remainder r from dividing a with b) are essential.

The number of iterations depends on finding a remainder r with a small norm in each step, preferably only a fraction of the dividend. Williams [11] obtained N(r) < \frac{3}{4}N(b), whereas Scheidler and Williams showed how to find r satisfying N(r) < \frac{1}{3}N(b). This was the basis for their algorithms for gcd and cubic residuosity taking time corresponding to O(log N(ab)) multiplications.

Each step in the Euclidian algorithm seems to require O(1) multiplications (divisions). Over the integers, however, the combined complexity of these arithmetic operations over all iterations sum up to only O(log a)(log b)), due to properties of integer division in the standard binary radix representation of the integers [1]. If one could have an analogue radix representation of elements in Z[ζ], a similar result might hold here. Both Knuth [3] and Penney [6] describe radix representations of the complex numbers (and hence the Gaussian integers, Z[i]). It seems their representations could be generalised to Z[ζ](see also [5]), but Knuth comments on the arithmetic in his representation that Examples of long division appear to require a stroke of genius when trial divisors are being picked. I.e. so far it is not clear how to obtain gcd and cubic residuosity algorithms for Z[ζ] that are based on the traditional Euclidian algorithm and yet obtains a time complexity comparable to our new algorithms.

1.2 Applications

Our algorithms may be used for the efficient computation of cubic residuosity in other rings than Z[ζ] when using an appropriate homomorphism. As an example, consider the finite field GF (p) for prime p ≡ 1 mod 3. A number z ∈ {1, …, p − 1} is a cubic residue precisely when z^{(p−1)/3} ≡ 1 mod p, implying that (non)residuosity may be decided by a (slow) modular exponentiation. However, it is possible to decide cubic residuosity much faster provided we make some preprocessing depending only on p. The preprocessing consists in factoring p over Z[ζ], i.e. finding a prime π ∈ Z[ζ] such that p = ππ̄. A suitable π may be found as π = gcd(p, r − ζ), where r ∈ Z is constructed as a solution to the quadratic equation x^{2} + x + 1 = 0 mod p. Following this preprocessing cubic residuosity of any z is decided using that z^{(p−1)/3} ≡ 1 mod p if and only if [z/π] = 1, where [·/·] denotes the cubic residuosity symbol.

When the order of the multiplicative group in question is unknown, modular exponentiation cannot be used, but it may still be possible to identify some nonresidues by computing residuosity symbols. In particular, the primality test of Damgård and Frandsen [2] uses our algorithms for finding cubic nonresidues in a more general ring.

Computation of gcd and cubic residuosity is also used for the implementation of cryptosystems by Scheidler and Williams [7], and by Williams [11].

Our fast algorithms are based on generalising the technique used in the binary gcd algorithm. The same generalisation does in fact also work for computing gcd and quartic residuosity in Z[i], the ring of Gaussian integers. The last section outlines this approach.

2 Preliminary facts about Z[ζ]

Z[ζ] is the ring of integers extended with a primitive third root of unity ζ (complex root of z^{2} + z + 1). We will be using the following definitions and facts [7].

Define the two conjugate mappings σ_{i} : Z[ζ] ↦ Z[ζ] by σ_{i}(ζ) = ζ^{i} for i = 1, 2. The rational integer N(α) = σ_{1}(α)σ_{2}(α) ≥ 0 is called the norm of α ∈ Z[ζ], and N(a + bζ) = a^{2} + b^{2} − ab. (Note that σ_{2}(·) and N(·) coincides with complex conjugation and complex norm, respectively).

A unit in Z[ζ] is an element of norm 1. There are 6 units in Z[ζ]: ±1, ±ζ, ±ζ^{2}. Two elements α, β ∈ Z[ζ] are said to be associates if there exists a unit ϵ such that α = ϵβ.

A prime π in Z[ζ] is a non unit such that for any α, β ∈ Z[ζ], if π|αβ, then π|α or π|β.

1 − ζ is a prime in Z[ζ] and N(1 − ζ) = 3. A primary number has the form 1 + 3β for some β ∈ Z[ζ]. If α ∈ Z[ζ] is not divisible by 1 − ζ then α is associated to a primary number. (This definition of primary is stronger than the usual one, which just requires the form ±1 + 3β, but our definition is more convenient in the present context).

If π is a prime in Z[ζ] and π is not associated to 1 − ζ then N(π) ≡ 1( mod 3), and the cubic residue symbol is defined by

[α/π] = α^{(N(π)−1)/3} mod π.

3 Computing gcd in Z[ζ]

It turns out that the wellknown binary integer gcd algorithm has a natural generalisation to a gcd algorithm for the Eisenstein integers. The generalised algorithm is best understood by relating it to the binary algorithm which we start by recalling:

A slightly nonstandard version of the binary gcd is the following. Every integer can be represented as (−1)^{i} · 2^{j} · (4m + 1). Without loss of generality, we may therefore assume that the numbers in question are of the form (4m+1). One iteration consists in replacing the numerically larger of the two numbers by their difference. If it is nonzero then the dividing 2-power (at least 2^{2}) may be removed without changing the gcd. If necessary the resulting odd number is multiplied with −1 to get a number of the form 4m + 1 and we are ready for the next iteration. It is fairly obvious that the product of the numeric values of the two numbers decreases by a factor at least 2 in each step until the gcd is found, and hence the gcd of two numbers a, b can be computed in time (log^{2} |ab|).

To make the analogue, we recall that any element of Z[ζ] that is not divisible by 1 − ζ is associated to a (unique) primary number, i.e. a number of the form 1 + 3α. This implies that any element in Z[ζ] \ {0} has a (unique) representation on the form (−ζ)^{i} · (1 − ζ)^{j} · (1 + 3α) where 0 ≤ i < 6, 0 ≤ j and α ∈ Z[ζ]. In addition, the difference of two primary numbers is divisible by (1 − ζ)^{2}, since 3 = −ζ^{2}(1 − ζ)^{2}. Now a gcd algorithm for the Eisenstein integers may be formulated as an analogue to the binary integer gcd algorithm. We may assume without loss of generality that the two input numbers are primary. Replace the (normwise) larger of the two numbers with their difference. If it is nonzero, we may divide out any powers of (1 − ζ) that divide the difference (at least (1 − ζ)^{2}) and convert the remaining factor to primary form by multiplying with a unit. We have again two primary numbers and the process may be continued. In each step we are required to identify the (normwise) larger of two numbers. Unfortunately it would be too costly to compute the relevant norm, but it suffices to choose the large number based on an approximation that we can afford to compute. By a slightly nontrivial argument one may prove that the product of the norms of the two numbers decreases by a factor at least 2 in each step until the gcd is found, and hence the gcd of two numbers α, β can be computed in time O(log^{2} N(αβ)).

Algorithm 1 describes the details including a start-up to bring the two numbers on primary form.

Theorem 1 Algorithm 1 takes time O(log^{2} N(αβ)) to compute the gcd of α, β, or formulated alternatively, the algorithm has bit complexity O(n^{2}).

Proof. Let us assume that a number α = a + bζ ∈ Z[ζ] is represented by the integer pair (a, b). Observe that since N(α) = a^{2} + b^{2} − ab, we have that log |a| + log |b| ≤ log N(α) ≤ 2(log |a| + log |b|) for a, b ≠ 0, i.e. the logarithm of the norm is proportional to the number of bits in the representation of a number.

Algorithm 1 Compute gcd in Z[ζ] Require: α, β ∈ Z[ζ] \ {0} Ensure: g = gcd(α, β) 1: Let primary γ, δ ∈ Z[ζ] be defined by α = (−ζ)^{i_{1}} · (1 − ζ)^{j_{1}} · γ and

β = (−ζ)^{i_{2}} · (1 − ζ)^{j_{2}} · δ. 2: g ← (1 − ζ)^{min{j_{1},j_{2}}} 3: Replace α, β with γ, δ. 4: while α ≠ β do 5: LOOP INVARIANT: α, β are primary 6: Let primary γ be defined by α − β = (−ζ)^{i} · (1 − ζ)^{j} · γ 7: Replace “approximately” larger of α, β with γ. 8: end while 9: g ← g · α

We may do addition, subtraction on general numbers and multiplication by units in linear time. Since (1 − ζ)^{−1} = (2 + ζ)/3, division by (and check for divisibility by) (1 − ζ) may also be done in linear time.

Clearly, the startup part of the algorithm that brings the two numbers on primary form can be done in time O(log^{2} N(αβ)). Hence, we need only worry about the while loop.

We want to prove that the norm of the numbers decrease for each iteration. The challenge is to see that forming the number α − β does not increase the norm too much. In fact N(α−β) ≤ 4·max{N(α), N(β)}. This follows trivially from the equation N(α+β)+N(α−β) = 2(N(α)+ N(β)) that may be proven by an elementary computation when using that the norm is nonnegative. Hence, for the γ computed in the loop of the algorithm, we get N(γ) = 3^{−j}N(α − β) ≤ 3^{−2}4 · max{N(α), N(β)}. In each iteration, γ ideally replaces the one of α and β with the larger norm. However, we can not afford to actually compute the norms to find out which one is the larger. Fortunately, by Lemma 2, it is possible in linear time to compute an approximate norm that may be slightly smaller than the exact norm, namely up to a factor 9/8. When γ replaces the one of α and β with the larger approximate norm, we know that N(αβ) decreases by a factor at least 9/4 · 8/9 = 2 in each iteration, i.e. the total number of iterations is O(log N(αβ)).

Each loop iteration takes time O(log N(αβ)) except possibly for finding the exponent of (1−ζ) that divides α−β. Assume that (1−ζ)^{t_{i}} is the maximal power of (1−ζ) that divides α−β in the ith iteration. Then the combined time complexity of all loop iterations is O((∑_{i} t_{i}) log N(αβ)).

We also know that N(αβ) ≥ ∏_{i}(3^{t_{i}}/4). Since we already know that there is only O(log N(αβ)) iterations it follows that ∏_{i} 4 = N(αβ)^{O(1)} and hence ∑_{i} t_{i} = O(log N(αβ)).

Lemma 2 Given α = a + bζ ∈ Z[ζ] it is possible to compute an approximate norm Ñ(α) such that

\frac{8}{9}N(α) ≤ Ñ(α) ≤ N(α)

in linear time, i.e. in time O(log N(α)).

Proof. Note that

N(a + bζ) = \frac{(a − b)^{2} + a^{2} + b^{2}}{2} .

Given ϵ > 0, we let d̃ denote some approximation to integer d satisfying that (1 − ϵ)|d| ≤ d̃≤ |d|. Note that

(1 − ϵ)^{2}N(a + bζ) ≤ \frac{(ã − b)^{2} + ã^{2} + b̃^{2}}{2} ≤ N(a + bζ)

Since we may compute a − b in linear time it suffices to compute ˜ - approximations and square them in linear time for some ϵ < 1/18. Given d in the usual binary representation, we take d̃ to be |d| with all but the 6 most significant bits replaced with zeroes, in which case

(1 − \frac{1}{32})|d| ≤ d̃≤ |d|

and we can compute d̃^{2} from d in linear time.

4 Computing cubic residuosity in Z[ζ]

Just as the usual integer gcd algorithms may be used for constructing algorithms for the Jacobi symbol, so can our earlier strategy for computing the gcd in Z[ζ] be used as the basis for an algorithm for computing the cubic residuosity symbol.

We start by recalling the definition of the cubic residuosity symbol.

[·/·] : Z[ζ] × (Z[ζ] − (1 − ζ)Z[ζ]) ↦ {0, 1, ζ, ζ^{−1}}

is defined as follows:

• For prime π ∈ Z[ζ] where π is not associated to 1 − ζ:

[α/π] = (α^{\frac{N(π)−1}{3}} ) mod π

• For number β = ∏_{i=1}^{t} π_{i}^{m_{i}} ∈ Z[ζ] where β is not divisible by 1 − ζ:

[α/β] = ∏_{i=1}^{t}[α/π_{i}]^{m_{i}}

Note that these rules imply [α/ϵ] = 1 for a unit ϵ and [α/β] = 0 when gcd(α, β) ≠ 1. In addition, we will need the following laws satisfied by the cubic residuosity symbol (recall that β is primary when it has the form β = 1 + 3γ for γ ∈ Z[ζ]) [4]:

• Modularity:

[α/β] = [α′/β], when α ≡ α′( mod β).

• Multiplicity:

[αα′/β] = [α/β] · [α′/β].

• The cubic reciprocity law:

[α/β] = [β/α], when α and β are both primary.

• The complementary laws (for primary β = 1 + 3(m + nζ), where m, n ∈ Z)

[1 − ζ/β] = ζ^{m},
[ζ/β] = ζ^{−(m+n)},
[−1/β] = 1.

The cubic residuosity algorithm will follow the gcd algorithm closely. In each iteration we will assume the two numbers α, β to be primary with Ñ(α) ≥ Ñ(β). We write their difference on the form α − β = (−ζ)^{i}(1 − ζ)^{j}γ, for primary γ = 1 + 3(m + nζ). By the above laws, [α/β] = ζ^{mj−(m+n)i}[γ/β]. If Ñ(α) < Ñ(β), we use the reciprocity law to swap γ and β before being ready to a new iteration. The algorithm stops, when the two primary numbers are identical. If the identical value (the gcd) is not 1 then the residuosity symbol evaluates to 0.

Algorithm 2 describes the entire procedure including a start-up to ensure that the numbers are primary.

Algorithm 2 Compute cubic residuosity in Z[ζ] Require: α, β ∈ Z[ζ] \ {0}, and β is not divisible by (1 − ζ) Ensure: c = [α/β] 1: Let primary γ, δ ∈ Z[ζ] be defined by α = (−ζ)^{i_{1}} · (1 − ζ)^{j_{1}} · γ and

β = (−ζ)^{i_{2}} · δ. 2: Let m, n ∈ Z be defined by δ = 1 + 3m + 3nζ. 3: t ← mj_{1} − (m + n)i_{1} mod 3 4: Replace α, β by γ, δ. 5: If Ñ(α) < Ñ(β) then interchange α, β. 6: while α ≠ β do 7: LOOP INVARIANT: α, β are primary and Ñ(α) ≥ Ñ(β) 8: Let primary γ be defined by α − β = (−ζ)^{i} · (1 − ζ)^{j} · γ 9: Let m, n ∈ Z be defined by β = 1 + 3m + 3nζ. 10: t ← t + mj − (m + n)i mod 3 11: Replace α with γ. 12: If Ñ(α) < Ñ(β) then interchange α, β. 13: end while 14: If α ≠ 1 then c ← 0 else c ← ζ^{t}

Theorem 3 Algorithm 2 takes time O(log^{2} N(αβ)) to compute [α/β], or formulated alternatively, the algorithm has bit complexity (n^{2}).

Proof. The complexity analysis from the gcd algorithm carries over without essential changes.

5 Computing gcd and quartic residuosity in the ring of Gaussian integers

We may construct fast algorithms for gcd and quartic residuosity in the ring of Gaussian integers, Z[i] = {a + bi | a, b ∈ Z}, in a completely analogous way to the algorithms over the Eisenstein integers.

Here is a sketch of the necessary facts (see [4]). There are 4 units in Z[i]: ±1, ±i. 1+i is a prime in Z[i] and N(1+i) = 2. A primary number has the form 1 + (2 + 2i)β for some β ∈ Z[i]. If α ∈ Z[i] is not divisible by 1 + i then α is associated to a primary number.

In particular, any element in Z[i] \ {0} has a (unique) representation on the form i^{j}·(1+i)^{k}·(1+(2+2i)α) where 0 ≤ j < 4, 0 ≤ k and α ∈ Z[i]. In addition, the difference of two primary numbers is divisible by (1+i)^{3}, since (2 + 2i) = −i(1 + i)^{3}. This is the basis for obtaining an algorithm for computing gcd over the Gaussian integers analogous to Algorithm 1. This new algorithm has also bit complexity O(n^{2}) as one may prove when using that N((1 + i)^{3}) = 8 and N(α − β) ≤ 4 · max{N(α), N(β)}.

For computing quartic residuosity, we need more facts [4]. If π is a prime in Z[i] and π is not associated to 1 + i then N(π) ≡ 1( mod 4), and the quartic residue symbol [·/·] : Z[i] × (Z[i] − (1 + i)Z[i]) ↦ {0, 1, −1, i, −i} is defined as follows:

• For prime π ∈ Z[i] where π is not associated to 1 + i:

[α/π] = (α^{\frac{N(π)−1}{4}} ) mod π

• For number β = ∏_{j=1}^{t} π_{j}^{m_{j}} ∈ Z[i] where β is not divisible by 1 + i:

[α/β] = ∏_{j=1}^{t}[α/π_{j}]^{m_{j}}

The quartic residuosity symbol satisfies in addition

• Modularity:

[α/β] = [α′/β], when α ≡ α′( mod β).

• Multiplicity:

[αα′/β] = [α/β] · [α′/β].

• The quartic reciprocity law:

[α/β] = [β/α]·(−1)^{\frac{N(α)−1}{4} · \frac{N(β)−1}{4}} , when α and β are both primary.

• The complementary laws (for primary β = 1 + (2 + 2i)(m + ni), where m, n ∈ Z)

[1 + i/β] = i^{−n−(n+m)^{2}},
[i/β] = i^{n−m}.

This is the basis for obtaining an algorithm for computing quartic residuosity analogous to Algorithm 2. This new algorithm has also bit complexity O(n^{2}).

References

[1] Eric Bach and Jeffrey Shallit. Algorithmic number theory. Vol. 1. Foundations of Computing Series. MIT Press, Cambridge, MA, 1996. Efficient algorithms.

[2] Ivan B. Damgård and Gudmund Skovbjerg Frandsen. An extended quadratic Frobenius primality test with average and worst case error estimates. Research Series RS-03-9, BRICS, Department of Computer Science, University of Aarhus, February 2003.

[3] Donald E. Knuth. An imaginary number system. Comm. ACM 3 (1960), 245–247.

[4] Franz Lemmermeyer. Reciprocity laws. Springer Monographs in Mathematics. Springer-Verlag, Berlin, 2000. From Euler to Eisenstein.

[5] Asger Munk Nielsen and Peter Kornerup. Redundant radix representations of rings. IEEE Trans. Comput. 48(11) (1999), 1153–1165.

[6] Walter Penney. A “binary” system for complex numbers. J. Assoc. Comput. Mach. 12 (1965), 247–248.

[7] Renate Scheidler and Hugh C. Williams. A public-key cryptosystem utilizing cyclotomic fields. Des. Codes Cryptogr. 6(2) (1995), 117–131.

[8] A. Schönhage. Schnelle Berechnung von Kettenbruchentwicklungen. Acta Informat. 1 (1971), 139–144.

[9] Jeffrey Shallit and Jonathan Sorenson. A binary algorithm for the jacobi symbol. ACM SIGSAM Bull. 27(1) (1993), 4–11.

[10] J. Stein. Computationals problems associated with Racah algebra. J. Comput. Phys. 1 (1967), 397–405.

[11] H. C. Williams. An M^{3} public-key encryption scheme. In Advances in cryptology—CRYPTO ’85 (Santa Barbara, Calif., 1985), Vol. 218 of Lecture Notes in Comput. Sci., pp. 358–368. Springer, Berlin, 1986.

[12] H. C. Williams and R. Holte. Computation of the solution of x^{3}+Dy^{3} = 1. Math. Comp. 31(139) (1977), 778–785.

Recent BRICS Report Series Publications

RS-03-8 Ivan B. Damgård and Gudmund Skovbjerg Frandsen. Efficient Algorithms for gcd and Cubic Residuosity in the Ring of Eisenstein Integers. February 2003. 11 pp.

RS-03-7 Claus Brabrand, Michael I. Schwartzbach, and Mads Vanggaard. The METAFRONT System: Extensible Parsing and Transformation. February 2003. 24 pp.

RS-03-6 Giuseppe Milicia and Vladimiro Sassone. Jeeg: Temporal Constraints for the Synchronization of Concurrent Objects. February 2003. 41 pp. Short version appears in Fox and Getov, editors, Joint ACM-ISCOPE Conference on Java Grande, JGI ’02 Proceedings, 2002, pages 212–221.

RS-03-5 Aske Simon Christensen, Anders Møller, and Michael I. Schwartzbach. Precise Analysis of String Expressions. February 2003. 15 pp.

RS-03-4 Marco Carbone and Mogens Nielsen. Towards a Formal Model for Trust. January 2003.

RS-03-3 Claude Crépeau, Paul Dumais, Dominic Mayers, and Louis Salvail. On the Computational Collapse of Quantum Information. January 2003. 31 pp.

RS-03-2 Olivier Danvy and Pablo E. Martínez López. Tagging, Encoding, and Jones Optimality. January 2003. To appear in Degano, editor, Programming Languages and Systems: Twelfth European Symposium on Programming, ESOP ’03 Proceedings, LNCS, 2003.

RS-03-1 Vladimiro Sassone and Pawel Sobocinski. Deriving Bisimulation Congruences: 2-Categories vs. Precategories. January 2003. To appear in Gordon, editor, Foundations of Software Science and Computation Structures, FoSSaCS ’03 Proceedings, LNCS, 2003.

RS-02-52 Olivier Danvy. A New One-Pass Transformation into Monadic Normal Form. December 2002. 16 pp. To appear in Hedin, editor, Compiler Construction, 12th International Conference, CC ’03 Proceedings, LNCS, 2003.