Elliptic curves, group law, and efficient computation

This thesis is about the derivation of the addition law on an arbitrary elliptic curve and efficiently adding points on this elliptic curve using the derived addition law. The outcomes of this research guarantee practical speedups in higher level operations which depend on point additions. In particular, the contributions immediately find applications in cryptology. Mastered by the 19th century mathematicians, the study of the theory of elliptic curves has been active for decades. Elliptic curves over finite fields made their way into public key cryptography in late 1980’s with independent proposals by Miller [Mil86] and Koblitz [Kob87]. Elliptic Curve Cryptography (ECC), following Miller’s and Koblitz’s proposals, employs the group of rational points on an elliptic curve in building discrete logarithm based public key cryptosystems. Starting from late 1990’s, the emergence of the ECC market has boosted the research in computational aspects of elliptic curves. This thesis falls into this same area of research where the main aim is to speed up the additions of rational points on an arbitrary elliptic curve (over a field of large characteristic). The outcomes of this work can be used to speed up applications which are based on elliptic curves, including cryptographic applications in ECC. The aforementioned goals of this thesis are achieved in five main steps. As the first step, this thesis brings together several algebraic tools in order to derive the unique group law of an elliptic curve. This step also includes an investigation of recent computer algebra packages relating to their capabilities. Although the group law is unique, its evaluation can be performed using abundant (in fact infinitely many) formulae. As the second step, this thesis progresses the finding of the best formulae for efficient addition of points. In the third step, the group law is stated explicitly by handling all possible summands. The fourth step presents the algorithms to be used for efficient point additions. In the fifth and final step, optimized software implementations of the proposed algorithms are presented in order to show that theoretical speedups of step four can be practically obtained. In each of the five steps, this thesis focuses on five forms of elliptic curves over finite fields of large characteristic. A list of these forms and their defining equations are given as follows: (a) Short Weierstrass form, y2 = x3 + ax + b, (b) Extended Jacobi quartic form, y2 = dx4 + 2ax2 + 1, (c) Twisted Hessian form, ax3 + y3 + 1 = dxy, (d) Twisted Edwards form, ax2 + y2 = 1 + dx2y2, (e) Twisted Jacobi intersection form, bs2 + c2 = 1, as2 + d2 = 1, These forms are the most promising candidates for efficient computations and thus considered in this work. Nevertheless, the methods employed in this thesis are capable of handling arbitrary elliptic curves. From a high level point of view, the following outcomes are achieved in this thesis. - Related literature results are brought together and further revisited. For most of the cases several missed formulae, algorithms, and efficient point representations are discovered. - Analogies are made among all studied forms. For instance, it is shown that two sets of affine addition formulae are sufficient to cover all possible affine inputs as long as the output is also an affine point in any of these forms. In the literature, many special cases, especially interactions with points at infinity were omitted from discussion. This thesis handles all of the possibilities. - Several new point doubling/addition formulae and algorithms are introduced, which are more efficient than the existing alternatives in the literature. Most notably, the speed of extended Jacobi quartic, twisted Edwards, and Jacobi intersection forms are improved. New unified addition formulae are proposed for short Weierstrass form. New coordinate systems are studied for the first time. - An optimized implementation is developed using a combination of generic x86-64 assembly instructions and the plain C language. The practical advantages of the proposed algorithms are supported by computer experiments. - All formulae, presented in the body of this thesis, are checked for correctness using computer algebra scripts together with details on register allocations.

Structural health monitoring : vibration-based damage detection and condition assessment of bridges

Structural health is a vital aspect of infrastructure sustainability. As a part of a vital infrastructure and transportation network, bridge structures must function safely at all times. However, due to heavier and faster moving vehicular loads and function adjustment, such as Busway accommodation, many bridges are now operating at an overload beyond their design capacity. Additionally, the huge renovation and replacement costs are a difficult burden for infrastructure owners. The structural health monitoring (SHM) systems proposed recently are incorporated with vibration-based damage detection techniques, statistical methods and signal processing techniques and have been regarded as efficient and economical ways to assess bridge condition and foresee probable costly failures. In this chapter, the recent developments in damage detection and condition assessment techniques based on vibration-based damage detection and statistical methods are reviewed. The vibration-based damage detection methods based on changes in natural frequencies, curvature or strain modes, modal strain energy, dynamic flexibility, artificial neural networks, before and after damage, and other signal processing methods such as Wavelet techniques, empirical mode decomposition and Hilbert spectrum methods are discussed in this chapter.

Axisymmetric shell structures for multi-use

Shell structures find use in many fields of engineering, notably structural, mechanical, aerospace and nuclear-reactor disciplines. Axisymmetric shell structures are used as dome type of roofs, hyperbolic cooling towers, silos for storage of grain, oil and industrial chemicals and water tanks. Despite their thin walls, strength is derived due to the curvature. The generally high strength-to-weight ratio of the shell form, combined with its inherent stiffness, has formed the basis of this vast application. With the advent in computation technology, the finite element method and optimisation techniques, structural engineers have extremely versatile tools for the optimum design of such structures. Optimisation of shell structures can result not only in improved designs, but also in a large saving of material. The finite element method being a general numerical procedure that could be used to treat any shell problem to any desired degree of accuracy, requires several runs in order to obtain a complete picture of the effect of one parameter on the shell structure. This redesign I re-analysis cycle has been achieved via structural optimisation in the present research, and MSC/NASTRAN (a commercially available finite element code) has been used in this context for volume optimisation of axisymmetric shell structures under axisymmetric and non-axisymmetric loading conditions. The parametric study of different axisymmetric shell structures has revealed that the hyperbolic shape is the most economical solution of shells of revolution. To establish this, axisymmetric loading; self-weight and hydrostatic pressure, and non-axisymmetric loading; wind pressure and earthquake dynamic forces have been modelled on graphical pre and post processor (PATRAN) and analysis has been performed on two finite element codes (ABAQUS and NASTRAN), numerical model verification studies are performed, and optimum material volume required in the walls of cylindrical, conical, parabolic and hyperbolic forms of axisymmetric shell structures are evaluated and reviewed. Free vibration and transient earthquake analysis of hyperbolic shells have been performed once it was established that hyperbolic shape is the most economical under all possible loading conditions. Effect of important parameters of hyperbolic shell structures; shell wall thickness, height and curvature, have been evaluated and empirical relationships have been developed to estimate an approximate value of the lowest (first) natural frequency of vibration. The outcome of this thesis has been the generation of new research information on performance characteristics of axisymmetric shell structures that will facilitate improved designs of shells with better choice of shapes and enhanced levels of economy and performance. Key words; Axisymmetric shell structures, Finite element analysis, Volume Optimisation_ Free vibration_ Transient response.

Obstacle-free range determination for rail track maintenance vehicles

Maintenance trains travel in convoy. In Australia, only the first train of the convoy pays attention to the track sig- nalization (the other convoy vehicles simply follow the preceding vehicle). Because of human errors, collisions can happen between the maintenance vehicles. Although an anti-collision system based on a laser distance meter is already in operation, the existing system has a limited range due to the curvature of the tracks. In this paper, we introduce an anti-collision system based on vision. The two main ideas are, (1) to warp the camera image into an image where the rails are parallel through a projective transform, and (2) to track the two rail curves simultaneously by evaluating small parallel segments. The performance of the system is demonstrated on an image dataset.

Predicting single-vehicle fatal crashes for two-lane rural highways in Southeastern United States

The rural two-lane highway in the southeastern United States is frequently associated with a disproportionate number of serious and fatal crashes and as such remains a focus of considerable safety research. The Georgia Department of Transportation spearheaded a regional fatal crash analysis to identify various safety performances of two-lane rural highways and to offer guidance for identifying suitable countermeasures with which to mitigate fatal crashes. The fatal crash data used in this study were compiled from Alabama, Georgia, Mississippi, and South Carolina. The database, developed for an earlier study, included 557 randomly selected fatal crashes from 1997 or 1998 or both (this varied by state). Each participating state identified the candidate crashes and performed physical or video site visits to construct crash databases with enhance site-specific information. Motivated by the hypothesis that single- and multiple-vehicle crashes arise from fundamentally different circumstances, the research team applied binary logit models to predict the probability that a fatal crash is a single-vehicle run-off-road fatal crash given roadway design characteristics, roadside environment features, and traffic conditions proximal to the crash site. A wide variety of factors appears to influence or be associated with single-vehicle fatal crashes. In a model transferability assessment, the authors determined that lane width, horizontal curvature, and ambient lighting are the only three significant variables that are consistent for single-vehicle run-off-road crashes for all study locations.

Experimental study of the concentration field of discharge from a boat propeller

Two-stroke outboard boat engines using total loss lubrication deposit a significant proportion of their lubricant and fuel directly into the water. The purpose of this work is to document the velocity and concentration field characteristics of a submerged swirling water jet emanating from a propeller in order to provide information on its fundamental characteristics. The properties of the jet were examined far enough downstream to be relevant to the eventual modelling of the mixing problem. Measurements of the velocity and concentration field were performed in a turbulent jet generated by a model boat propeller (0.02 m diameter) operating at 1500 rpm and 3000 rpm in a weak co-flow of 0.04 m/s. The measurements were carried out in the Zone of Established Flow up to 50 propeller diameters downstream of the propeller, which was placed in a glass-walled flume 0.4 m wide with a free surface depth of 0.15 m. The jet and scalar plume development were compared to that of a classical free round jet. Further, results pertaining to radial distribution, self similarity, standard deviation growth, maximum value decay and integral fluxes of velocity and concentration were presented and fitted with empirical correlations. Furthermore, propeller induced mixing and pollutant source concentration from a two-stroke engine were estimated.

Numerical methods for second-order stochastic differential equations

We seek numerical methods for second‐order stochastic differential equations that reproduce the stationary density accurately for all values of damping. A complete analysis is possible for scalar linear second‐order equations (damped harmonic oscillators with additive noise), where the statistics are Gaussian and can be calculated exactly in the continuous‐time and discrete‐time cases. A matrix equation is given for the stationary variances and correlation for methods using one Gaussian random variable per timestep. The only Runge–Kutta method with a nonsingular tableau matrix that gives the exact steady state density for all values of damping is the implicit midpoint rule. Numerical experiments, comparing the implicit midpoint rule with Heun and leapfrog methods on nonlinear equations with additive or multiplicative noise, produce behavior similar to the linear case.

Machine recognition of hand-drawn circuit diagrams

An application of image processing techniques to recognition of hand-drawn circuit diagrams is presented. The scanned image of a diagram is pre-processed to remove noise and converted to bilevel. Morphological operations are applied to obtain a clean, connected representation using thinned lines. The diagram comprises of nodes, connections and components. Nodes and components are segmented using appropriate thresholds on a spatially varying object pixel density. Connection paths are traced using a pixel-stack. Nodes are classified using syntactic analysis. Components are classified using a combination of invariant moments, scalar pixel-distribution features, and vector relationships between straight lines in polygonal representations. A node recognition accuracy of 82% and a component recognition accuracy of 86% was achieved on a database comprising 107 nodes and 449 components. This recogniser can be used for layout “beautification” or to generate input code for circuit analysis and simulation packages

Using Fiber Bragg Grating (FBG) sensors for vertical displacement measurement of bridges

In many bridges, vertical displacements are one of the most relevant parameters for structural health monitoring in both the short and long terms. Bridge managers around the globe are always looking for a simple way to measure vertical displacements of bridges. However, it is difficult to carry out such measurements. On the other hand, in recent years, with the advancement of fiber-optic technologies, fiber Bragg grating (FBG) sensors are more commonly used in structural health monitoring due to their outstanding advantages including multiplexing capability, immunity of electromagnetic interference as well as high resolution and accuracy. For these reasons, using FBG sensors is proposed to develop a simple, inexpensive and practical method to measure vertical displacements of bridges. A curvature approach for vertical displacement measurement using curvature measurements is proposed. In addition, with the successful development of a FBG tilt sensors, an inclination approach is also proposed using inclination measurements. A series of simulation tests of a full-scale bridge was conducted. It shows that both the approaches can be implemented to determine vertical displacements for bridges with various support conditions, varying stiffness (EI) along the spans and without any prior known loading. These approaches can thus measure vertical displacements for most of slab-on-girder and box-girder bridges. Moreover, with the advantages of FBG sensors, they can be implemented to monitor bridge behavior remotely and in real time. Further recommendations of these approaches for developments will also be discussed at the end of the paper.

Turbulence characteristics of a small subtropical estuary during and after some moderate rainfall

In natural estuaries, scalar diffusion and dispersion are driven by turbulence. In the present study, detailed turbulence measurements were conducted in a small subtropical estuary with semi-diurnal tides under neap tide conditions. Three acoustic Doppler velocimeters were installed mid-estuary at fixed locations close together. The units were sampled simultaneously and continuously at relatively high frequency for 50 h. The results illustrated the influence of tidal forcing in the small estuary, although low frequency longitudinal velocity oscillations were observed and believed to be induced by external resonance. The boundary shear stress data implied that the turbulent shear in the lower flow region was one order of magnitude larger than the boundary shear itself. The observation differed from turbulence data in a laboratory channel, but a key feature of natural estuary flow was the significant three dimensional effects associated with strong secondary currents including transverse shear events. The velocity covariances and triple correlations, as well as the backscatter intensity and covariances, were calculated for the entire field study. The covariances of the longitudinal velocity component showed some tidal trend, while the covariances of the transverse horizontal velocity component exhibited trends that reflected changes in secondary current patterns between ebb and flood tides. The triple correlation data tended to show some differences between ebb and flood tides. The acoustic backscatter intensity data were characterised by large fluctuations during the entire study, with dimensionless fluctuation intensity I0b =Ib between 0.46 and 0.54. An unusual feature of the field study was some moderate rainfall prior to and during the first part of the sampling period. Visual observations showed some surface scars and marked channels, while some mini transient fronts were observed.

Turbulent measurements in a small subtropical estuary with semidiurnal tides

Since predictions of scalar dispersion in small estuaries can rarely be predicted accurately, new field measurements were conducted continuously at relatively high frequency for up to 50 h (per investigation) in a small subtropical estuary with semidiurnal tides. The bulk flow parameters varied in time with periods comparable to tidal cycles and other large-scale processes. The turbulence properties depended upon the instantaneous local flow properties. They were little affected by the flow history, but their structure and temporal variability were influenced by a variety of parameters including the tidal conditions and bathymetry. A striking feature of the data sets was the large fluctuations in all turbulence characteristics during the tidal cycle, and basic differences between neap and spring tide turbulence.

An experimental study of a reactive plume in grid turbulence

Experimental results for a reactive non-buoyant plume of nitric oxide (NO) in a turbulent grid flow doped with ozone (O3) are presented. The Damkohler number (Nd) for the experiment is of order unity indicating the turbulence and chemistry have similar timescales and both affect the chemical reaction rate. Continuous measurements of two components of velocity using hot-wire anemometry and the two reactants using chemiluminescent analysers have been made. A spatial resolution for the reactants of four Kolmogorov scales has been possible because of the novel design of the experiment. Measurements at this resolution for a reactive plume are not found in the literature. The experiment has been conducted relatively close to the grid in the region where self-similarity of the plume has not yet developed. Statistics of a conserved scalar, deduced from both reactive and non-reactive scalars by conserved scalar theory, are used to establish the mixing field of the plume, which is found to be consistent with theoretical considerations and with those found by other investigators in non-reative flows. Where appropriate the reactive species means and higher moments, probability density functions, joint statistics and spectra are compared with their respective frozen, equilibrium and reaction-dominated limits deduced from conserved scalar theory. The theoretical limits bracket reactive scalar statistics where this should be so according to conserved scalar theory. Both reactants approach their equilibrium limits with greater distance downstream. In the region of measurement, the plume reactant behaves as the reactant not in excess and the ambient reactant behaves as the reactant in excess. The reactant covariance lies outside its frozen and equilibrium limits for this value of Vd. The reaction rate closure of Toor (1969) is compared with the measured reaction rate. The gradient model is used to obtain turbulent diffusivities from turbulent fluxes. Diffusivity of a non-reactive scalar is found to be close to that measured in non-reactive flows by others.

Planning most-likely paths from overhead imagery

This paper is about planning paths from overhead imagery, the novelty of which is taking explicit account of uncertainty in terrain classification and spatial variation in terrain cost. The image is first classified using a multi-class Gaussian Process Classifier which provides probabilities of class membership at each location in the image. The probability of class membership at a particular grid location is then combined with a terrain cost evaluated at that location using a spatial Gaussian process. The resulting cost function is, in turn, passed to a planner. This allows both the uncertainty in terrain classification and spatial variations in terrain costs to be incorporated into the planned path. Because the cost of traversing a grid cell is now a probability density rather than a single scalar value, we can produce not only the most-likely shortest path between points on the map, but also sample from the cost map to produce a distribution of paths between the points. Results are shown in the form of planned paths over aerial maps, these paths are shown to vary in response to local variations in terrain cost.

MRI study of the changes in crystalline lens shape with accommodation and ageing in humans

Magnetic Resonance Imaging was used to study changes in the crystalline lens and ciliary body with accommodation and aging. Monocular images were obtained in 15 young (19-29 years) and 15 older (60-70 years) emmetropes when viewing at far (6m) and at individual near points (14.5 to 20.9 cm) in the younger group. With accommodation, lens thickness increased (mean±95% CI: 0.33±0.06mm) by a similar magnitude to the decrease in anterior chamber depth (0.31±0.07mm) and equatorial diameter (0.32±0.04mm) with a decrease in the radius of curvature of the posterior lens surface (0.58±0.30mm). Anterior lens surface shape could not be determined due to the overlapping region with the iris. Ciliary ring diameter decreased (0.44±0.17mm) with no decrease in circumlental space or forward ciliary body movement. With aging, lens thickness increased (mean±95% CI: 0.97±0.24mm) similar in magnitude to the sum of the decrease in anterior chamber depth (0.45±0.21mm) and increase in anterior segment depth (0.52±0.23mm). Equatorial lens diameter increased (0.28±0.23mm) with no change in the posterior lens surface radius of curvature. Ciliary ring diameter decreased (0.57±0.41mm) with reduced circumlental space (0.43±0.15mm) and no forward ciliary body movement. Accommodative changes support the Helmholtz theory of accommodation including an increase in posterior lens surface curvature. Certain aspects of aging changes mimic accommodation.

Thomas Young’s contributions to geometrical optics

In addition to his work on physical optics, Thomas Young (1773-1829) made several contributions to geometrical optics, most of which received little recognition in his time or since. We describe and assess some of these contributions: Young’s construction (the basis for much of his geometric work), paraxial refraction equations, oblique astigmatism and field curvature, and gradient-index optics.