On the problem of algebraic completeness for the invariants of the Riemann Tensor: I

We present a new determining set, CZ, of Riemann invariants which possesses the minimum degree property. From an analysis on the possible independence of CZ, we are led to the division of all space-times into two distinct, invariantly characterized, classes: a general class M_G+, and a special, singular class M_S For each class, we provide an independent set of invariants (I_G+) ⊂ CZ and I_S ⊂ CZ, respectively) which, with the results of a sequel paper, will be shown to be algebraically complete.

On the problem of algebraic completeness for the invariants of the Riemann tensor. III.

We study the set CZ of invariants [Zakhary and Carminati, J. Math. Phys. 42, 1474 (2001)] for the class of space-times whose Ricci tensors possess a null eigenvector. We show that all cases are maximally backsolvable, in terms of sets of invariants from CZ, but that some cases are not completely backsolvable and these all possess an alignment between an eigenvector of the Ricci tensor with a repeated principal null vector of the Weyl tensor. We provide algebraically complete sets for each canonically different space-time and hence conclude with these results and those of a previous article [Carminati, Zakhary, and McLenaghan, J. Math. Phys. 43, 492 (2002)] that the CZ set is determining or maximal.

Algebraic attacks over GF(q)

Recent algebraic attacks on LFSR-based stream ciphers and S-boxes have generated much interest as they appear to be extremely powerful. Theoretical work has been developed focusing around the Boo- lean function case. In this paper, we generalize this theory to arbitrary finite fields and extend the theory of annihilators and ideals introduced at Eurocrypt 2004 by Meier, Pasalic and Carlet. In particular, we prove that for any function f in the multivariate polynomial ring over GF(q), f has a low degree multiple precisely when two low degree functions appear in the same coset of the annihilator of f ^{q – 1} – 1. In this case, many such low degree multiples exist.

Algebraic attacks on clock-controlled stream ciphers

We present an algebraic attack approach to a family of irregularly clock-controlled bit-based linear feedback shift register systems. In the general set-up, we assume that the output bit of one shift register controls the clocking of other registers in the system and produces a family of equations relating the output bits to the internal state bits. We then apply this general theory to four specific stream ciphers: the (strengthened) stop-and-go generator, the alternating step generator, the self-decimated generator and the step1/step2 generator. In the case of the strengthened stop-and-go generator and of the self-decimated generator, we obtain the initial state of the registers in a significantly faster time than any other known attack. In the other two situations, we do better than or as well as all attacks but the correlation attack. In all cases, we demonstrate that the degree of a functional relationship between the registers can be bounded by two. Finally, we determine the effective key length of all four systems.

Algebraic attacks on clock-controlled cascade ciphers

In this paper, we mount the first algebraic attacks against clock controlled cascade stream ciphers. We first show how to obtain relations between the internal state bits and the output bits of the Gollmann clock controlled cascade stream ciphers. We demonstrate that the initial states of the last two shift registers can be determined by the initial states of the others. An alternative attack on the Gollmann cascade is also described, which requires solving quadratic equations. We then present an algebraic analysis of Pomaranch, one of the phase two proposals to eSTREAM. A system of equations of maximum degree four that describes the full cipher is derived. We also present weaknesses in the filter functions of Pomaranch by successfully computing annihilators and low degree multiples of the functions.

An algebraic approach for delay-independent and delay-dependent stability of linear time-delay systems

This paper addresses the problem of asymptotic stability of a linear system with many delay units. A novel algebraic test is proposed for the delay-independent stability of the system, based on the root distribution of the system's characteristic equation. If the system is only stable dependent of delay, the whole stable regions of the system can be perfectly obtained. Two algorithms are derived to examine the delay-independent stability, and to compute the whole stable regions if the system is of delay-dependent stability. These algorithms are computationally efficient and applicable to both certain and uncertain systems. Some illustrative examples demonstrate the validity of the approach.

Mutually clock-controlled feedback shift registers provide resistance to algebraic attacks

Algebraic attacks have been applied to several types of clock-controlled stream ciphers. However, to date there are no such attacks in the literature on mutually clock-controlled ciphers. In this paper, we present a preliminary step in this direction by giving the first algebraic analysis of mutually clock-controlled feedback shift register stream ciphers: the bilateral stop-and-go generator, A5/1, Alpha 1 and the MICKEY cipher. We show that, if there are no regularly clocked shift registers included in the system, mutually clock-controlled feedback shift register ciphers appear to be highly resistant to algebraic attacks. As a demonstration of the weakness inherent in the presence of a regularly clocked shift register, we present a simple algebraic attack on Alpha 1 based on only 29 keystream bits.

On the problem of algebraic completeness for the invariants of the Riemann tensor. II

We study the set of invariants CZ [E. Zakhary and J. Carminati, J. Math. Phys. 42, 1474 (2001)] for the class of space-times whose Ricci tensors do not possess a null eigenvector. We show that all cases are completely backsolvable in terms of sets of invariants from CZ. We provide algebraically complete sets for each canonically different space-time.

An algebraic framework for multimodal image fusion

This thesis presents an algebraic framework for multimodal image fusion. The framework derives algebraic constructs and equations that govern the fusion process. The derived equations serve as objective functions according to which image fusion algorithms and metrics can be tuned. The equations also prove the duality between image fusion algorithms and metrics.

Primary teachers’ algebraic thinking: example from lesson study

Previous studies have reported on primary children’s algebraic thinking and generalising in a range of problem settings but there is little evidence of primary teachers’ knowledge of algebraic thinking. In this paper the development in algebraic thinking of one primary teacher who taught a research lesson in a Japanese Lesson Study project involving teachers from three primary schools is presented. The findings suggest the need for professional learning in algebra and reasoning and indicate the value of Lesson Study.

TensorPack : a Maple-based software package for the manipulation of algebraic expressions of tensors in general relativity

In this paper we: (1) introduce TensorPack, a software package for the algebraic manipulation of tensors in covariant index format in Maple; (2) briefly demonstrate the use of the package with an orthonormal tensor proof of the shearfree conjecture for dust. TensorPack is based on the Riemann and Canon tensor software packages and uses their functions to express tensors in an indexed covariant format. TensorPack uses a string representation as input and provides functions for output in index form. It extends the functionality to basic algebra of tensors, substitution, covariant differentiation, contraction, raising/lowering indices, symmetry functions and other accessory functions. The output can be merged with text in the Maple environment to create a full working document with embedded dynamic functionality. The package offers potential for manipulation of indexed algebraic tensor expressions in a flexible software environment.

GHP: a maple package for performing calculations in the Geroch-Held-Penrose formalism

We present a new symbolic algebra package, written for Maple, for performing computations in the Geroch-Held-Penrose formalism. We demonstrate the essential features and capabilities of our package by investigating Petrov-D vacuum solutions of Einstein's field equations.

Reduced-order output feedback controllers for discrete-time systems

This article considers the stabilization by output feedback controllers for discrete-time systems. The controller can place all of the closed-loop poles within a specified disk D(-α, 1/β), centred at (-α,0) with radius 1/β, where | - α|  + 1/β < 1. The design method involves the decomposition of the system into two portions. The first portion comprises of all of the poles that are lying outside of the specified disk. A reduced-order model is constructed for this portion. The second portion comprises of all of the remaining poles of the system and is characterized by an H_∞-norm bound. The controller design is then accomplished by using H_∞-control theory. It is shown that, subject to the solvability of an algebraic Riccati equation, output feedback controllers can be systematically derived. The order of the controller is low, and can be as low as the number of the open-loop poles that are lying outside of the specified disk. A step-by-step design algorithm is provided. Numerical examples are given to illustrate the attractiveness of the design method.

Constrained pole placement for linear systems using low-order output feedback controllers

The paper presents a simple approach to the problem of designing low-order output feedback controllers for linear continuous systems. The controller can place all of the closed-loop poles within a circle, C(- , 1/ β) , with centre at - and radius of 1/ β in the left half s-plane. The design method is based on transformation of the original system and then applying the bounded-real-lemma to the transformed system. It is shown that subjected to the solvability of an algebraic Riccati equation (ARE), output feedback controllers can then be systematically derived. Furthermore, the order of the controller is low and equals only the number of the open-loop poles lying outside the circle. A step-by-step design algorithm is given. Numerical examples are given to illustrate the design method.

The GHP II package with applications

We present an advanced version of the Maple package GHP called GHPII. In it we provide a number of additional sophisticated tools to assist with problems formulated in the Geroch-Held-Penrose (ghp) formalism. The first part of this article discusses these new tools while in the second part we shall apply the ghp formalism, using the GHPII routines, to vacuum Petrov type D spacetimes and shear-free perfect fluids. We prove that for all shear-free perfect fluids with a barotropic equation of state, where two of the principal null directions are coplanar with the fluid four-velocity and vorticity then either the expansion or vorticity of the fluid must be zero.