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.

Culture independent analysis of greyback canegrub-associated microflora and microbial community comparison using subtractive hybridisation

Greyback canegrubs cost the Australian sugarcane industry around $13 million per annum in damage and control. A novel and cost effective biocontrol bacterium could play an important role in the integrated pest management program currently in place to reduce damage and control associated costs. During the course of this project, terminal restriction fragment length polymorphism (TRFLP), 16-S rDNA cloning, suppressive subtractive hybridisation (SSH) and entomopathogen-specific PCR screening were used to investigate the little studied canegrub-associated microflora in an attempt to discover novel pathogens from putatively-diseased specimens. Microflora associated with these soil-dwelling insects was found to be both highly diverse and divergent between individual specimens. Dominant members detected in live specimens were predominantly from taxa of known insect symbionts while dominant sequences amplified from dead grubs were homologous to putativelysaprophytic bacteria and bacteria able to grow during refrigeration. A number of entomopathogenic bacteria were identified such as Photorhabdus luminescens and Pseudomonas fluorescens. Dead canegrubs prior to decomposition need to be analysed if these bacteria are to be isolated. Novel strategies to enrich putative pathogen-associated sequences (SSH and PCR screening) were shown to be promising approaches for pathogen discovery and the investigation of canegrubsassociated microflora. However, due to inter- and intra-grub-associated community diversity, dead grub decomposition and PCR-specific methodological limitations (PCR bias, primer specificity, BLAST database restrictions, 16-S gene copy number and heterogeneity), recommendations have been made to improve the efficiency of such techniques. Improved specimen collection procedures and utilisation of emerging high-throughput sequencing technologies may be required to examine these complex communities in more detail. This is the first study to perform a whole-grub analysis and comparison of greyback canegrub-associated microbial communities. This work also describes the development of a novel V3-PCR based SSH technique. This was the first SSH technique to use V3-PCR products as a starting material and specifically compare bacterial species present in a complex community.

Multiple camera management using wide baseline matching

Camera calibration information is required in order for multiple camera networks to deliver more than the sum of many single camera systems. Methods exist for manually calibrating cameras with high accuracy. Manually calibrating networks with many cameras is, however, time consuming, expensive and impractical for networks that undergo frequent change. For this reason, automatic calibration techniques have been vigorously researched in recent years. Fully automatic calibration methods depend on the ability to automatically find point correspondences between overlapping views. In typical camera networks, cameras are placed far apart to maximise coverage. This is referred to as a wide base-line scenario. Finding sufficient correspondences for camera calibration in wide base-line scenarios presents a significant challenge. This thesis focuses on developing more effective and efficient techniques for finding correspondences in uncalibrated, wide baseline, multiple-camera scenarios. The project consists of two major areas of work. The first is the development of more effective and efficient view covariant local feature extractors. The second area involves finding methods to extract scene information using the information contained in a limited set of matched affine features. Several novel affine adaptation techniques for salient features have been developed. A method is presented for efficiently computing the discrete scale space primal sketch of local image features. A scale selection method was implemented that makes use of the primal sketch. The primal sketch-based scale selection method has several advantages over the existing methods. It allows greater freedom in how the scale space is sampled, enables more accurate scale selection, is more effective at combining different functions for spatial position and scale selection, and leads to greater computational efficiency. Existing affine adaptation methods make use of the second moment matrix to estimate the local affine shape of local image features. In this thesis, it is shown that the Hessian matrix can be used in a similar way to estimate local feature shape. The Hessian matrix is effective for estimating the shape of blob-like structures, but is less effective for corner structures. It is simpler to compute than the second moment matrix, leading to a significant reduction in computational cost. A wide baseline dense correspondence extraction system, called WiDense, is presented in this thesis. It allows the extraction of large numbers of additional accurate correspondences, given only a few initial putative correspondences. It consists of the following algorithms: An affine region alignment algorithm that ensures accurate alignment between matched features; A method for extracting more matches in the vicinity of a matched pair of affine features, using the alignment information contained in the match; An algorithm for extracting large numbers of highly accurate point correspondences from an aligned pair of feature regions. Experiments show that the correspondences generated by the WiDense system improves the success rate of computing the epipolar geometry of very widely separated views. This new method is successful in many cases where the features produced by the best wide baseline matching algorithms are insufficient for computing the scene geometry.

The ecology of Bactrocera tryoni (Froggatt) (Diptera: Tephritdae) : what do we know to assist pest management?

The distribution, systematics and ecology of Bactrocera tryoni, the Queensland fruit fly are reviewed. Bactrocera tryoni is a member of the B. tryoni complex of species, which currently includes four named species, viz. B. tryoni s.s., B. neohumeralis, B. melas and B. aquilonis. The species status of B. melas and B. aquilonis are unclear (they may be junior synonyms of B. tryoni) and their validity, or otherwise, needs to be confirmed as a matter of urgency. While Queensland fruit fly is regarded as a tropical species, it cannot be assumed that its distribution will spread further south under climate change scenarios. Increasing aridity and hot dry summers, as well as more complex, indirect interactions resulting from elevated CO2, make predicting the future distribution and abundance of B. tryoni difficult. The ecology of B. tryoni is reviewed with respect to current control approaches (with the exception of Sterile Insect Technique which is covered in a companion paper). We conclude that there are major gaps in the knowledge required to implement most non-insecticide based management approaches. Priority areas for future research include host plant interactions, protein and cue-lure foraging and use, spatial dynamics, development of new monitoring tools, investigating the use of natural enemies and better integration of fruit flies into general horticultural IPM systems.

Preference among four Bactrocera species (Diptera: Tephritidae) by Diachasmimorpha kraussii (Fullaway) (Hymenoptera: Braconidae)

Diachasmimorpha kraussii is an endoparasitoid of larval dacine fruit flies. To date the only host preference study done on D. kraussii has used fruit flies from outside its native range (Australia, Papua New Guinea, Solomon Islands). In contrast, this paper investigates host preference for four fly species (Bactrocera cacuminata, B. cucumis, B. jarvisi and B. tryoni) which occur sympatrically with the wasp in the Australian component of the native range. Diachasmimorpha kraussii oviposition preference, host suitability (parasitism rate, number of progeny, sex ratio), and offspring performance measures (body length, hind tibial length, developmental time) were investigated with respect to the four fly species in the laboratory in both no-choice and choice situations. The parasitoid accepted all four fruit fly species for oviposition in both no-choice and choice tests; however, adult wasps only emerged from B. jarvisi and B. tryoni. Through dissection, it was demonstrated that parasitoid eggs were encapsulated in both B. cacuminata and B. cucumis. Between the two suitable hosts, measurements of oviposition preference, host suitability and offspring performance measurements either did not vary significantly, or varied in an inconsistent manner. Based on our results, and a related study by other authors, we conclude that D. krausii, at the point of oviposition, cannot discriminate between physiologically suitable and unsuitable hosts.

Is a mango just a mango? Testing within-fruit oviposition site choice and larval performance of a highly polyphagous fruit fly

For fruit flies, fully ripe fruit is preferred for adult oviposition and is superior for offspring performance over unripe or ripening fruit. Because not all parts of a single fruit ripen simultaneously, the opportunity exists for adult fruit flies to selectively choose riper parts of a fruit for oviposition and such selection, if it occurs, could positively influence offspring performance. Such fine scale host variation is rarely considered in fruit fly ecology, however, especially for polyphagous species which are, by definition, considered to be generalist host users. Here we study the adult oviposition preference/larval performance relationship of the Oriental fruit fly, Bactrocera dorsalis (Hendel) (Diptera: Tephritidae), a highly polyphagous pest species, at the “within-fruit” level to see if such a host use pattern occurs. We recorded the number of oviposition attempts that female flies made into three fruit portions (top, middle and bottom), and larval behavior and development within different fruit portions for ripening (color change) and fully-ripe mango, Mangifera indica L. (Anacardiaceae). Results indicate that female B. dorsalis do not oviposit uniformly across a mango fruit, but lay most often in the top (i.e., stalk end) of fruit and least in the bottom portion, regardless of ripening stage. There was no evidence of larval feeding site preference or performance (development time, pupal weight, percent pupation) being influenced by fruit portion, within or across the fruit ripening stages. There was, however, a very significant effect on adult emergence rate from pupae, with adult emergence rate from pupae from the bottom of ripening mango being approximately only 50% of the adult emergence rate from the top of ripening fruit, or from both the top and bottom of fully-ripe fruit. Differences in mechanical (firmness) and chemical (total soluble solids, titratable acidity, total non-structural carbohydrates) traits between different fruit portions were correlated with adult fruit utilisation. Our results support a positive adult preference/offspring performance relationship at within-fruit level for B. dorsalis. The fine level of host discrimination exhibited by B. dorsalis is at odds with the general perception that, as a polyphagous herbivore, the fly should show very little discrimination in its host use behavior.

Archiving nature’s heartbeat using smart phones

The impact of urban development and climate change has created the impetus to monitor changes in the environment, particularly, the behaviour, habitat and movement of fauna species. The aim of this chapter is to present the design and development of a sensor network based on smart phones to automatically collect and analyse acoustic and visual data for environmental monitoring purposes. Due to the communication and sophisticated programming facilities offered by smart phones, software tools can be developed to allow data to be collected, partially processed and sent to a remote server over the network for storage and further processing. This sensor network which employs a client-server architecture has been deployed in three applications: monitoring a rare bird species near Brisbane Airport, study of koalas behaviour at St Bees Island, and detection of fruit flies. The users of this system include scientists (e.g. ecologists, ornithologists, computer scientists) and community groups participating in data collection or reporting on the environment (e.g. students, bird watchers). The chapter focuses on the following aspects of our research: issues involved in using smart phones as sensors; the overall framework for data acquisition, data quality control, data management and analysis; current and future applications of the smart phone-based sensor network, and our future research directions.

Aerial SLAM with a single camera using visual expectation

Micro aerial vehicles (MAVs) are a rapidly growing area of research and development in robotics. For autonomous robot operations, localization has typically been calculated using GPS, external camera arrays, or onboard range or vision sensing. In cluttered indoor or outdoor environments, onboard sensing is the only viable option. In this paper we present an appearance-based approach to visual SLAM on a flying MAV using only low quality vision. Our approach consists of a visual place recognition algorithm that operates on 1000 pixel images, a lightweight visual odometry algorithm, and a visual expectation algorithm that improves the recall of place sequences and the precision with which they are recalled as the robot flies along a similar path. Using data gathered from outdoor datasets, we show that the system is able to perform visual recognition with low quality, intermittent visual sensory data. By combining the visual algorithms with the RatSLAM system, we also demonstrate how the algorithms enable successful SLAM.

The complete mitochondrial genome of the gall-forming fly, Fergusonina taylori(Nelson and Yeates) (Diptera: Fergusoninidae)

The monogeneric family Fergusoninidae consists of gall-forming flies that, together with Fergusobia (Tylenchida: Neotylenchidae) nematodes, form the only known mutualistic association between insects and nematodes. In this study, the entire 16,000 bp mitochondrial genome of Fergusonina taylori Nelson and Yeates was sequenced. The circular genome contains one encoding region including 27 genes and one non-coding A þT-rich region. The arrangement of the proteincoding, ribosomal RNA (rRNA) and transfer RNA (tRNA) genes was the same as that found in the ancestral insect. Nucleotide composition is highly A þ T biased. All of the protein initiation codons are ATN, except for nad1 which begins with TTT. All 22 tRNA anticodons of F. taylori match those observed in Drosophila yakuba, and all form the typical cloverleaf structure except for tRNA-Ser (AGN) which lacks a dihydrouridine (DHU) arm. Secondary structural features of the rRNA genes of Fergusonina are similar to those proposed for other insects, with minor modifications. The mitochondrial genome of Fergusonina presented here may prove valuable for resolving the sister group to the Fergusoninidae, and expands the available mtDNA data sources for acalyptrates overall.

Wing shape as a potential discriminator of morphologically similar pest taxa within the Bactrocera dorsalis species complex (Diptera: Tephritidae)

Four morphologically cryptic species of the Bactrocera dorsalis fruit fly complex (B. dorsalis s.s., B. papayae, B. carambolae and B. philippinensis) are serious agricultural pests. As they are difficult to diagnose using traditional taxonomic techniques, we examined the potential for geometric morphometric analysis of wing size and shape to discriminate between them. Fifteen wing landmarks generated size and shape data for 245 specimens for subsequent comparisons among three geographically distinct samples of each species. Intraspecific wing size was significantly different within samples of B. carambolae and B. dorsalis s.s. but not within samples of B. papayae or B. philippinensis. Although B. papayae had the smallest wings (average centroid size=6.002 mm±0.061 SE) and B. dorsalis s.s. the largest (6.349 mm±0.066 SE), interspecific wing size comparisons were generally non-informative and incapable of discriminating species. Contrary to the wing size data, canonical variate analysis based on wing shape data discriminated all species with a relatively high degree of accuracy; individuals were correctly reassigned to their respective species on average 93.27% of the time. A single sample group of B. carambolae from locality 'TN Malaysia' was the only sample to be considerably different from its conspecific groups with regards to both wing size and wing shape. This sample was subsequently deemed to have been originally misidentified and likely represents an undescribed species. We demonstrate that geometric morphometric techniques analysing wing shape represent a promising approach for discriminating between morphologically cryptic taxa of the B. dorsalis species complex.

Host location by the fruit fly parasitoid Diachasmimorpha krausii : role of fruit fly species, life stage and host plant

1 Diachasmimorpha krausii is a braconid parasitoid of larval tephritid fruit flies, which feed cryptically within host fruit. At the ovipositor probing stage, the wasp cannot discriminate between hosts that are physiologically suitable or unsuitable for offspring development and must use other cues to locate suitable hosts. 2 To identify the cues used by the parasitoid to find suitable hosts, we offered, to free flying wasps, different combinations of three fruit fly species (Bactrocera tryoni, Bactrocera cacuminata, Bactrocera cucumis), different life stages of those flies (adults and larvae) and different host plants (Solanum lycopersicon, Solanum mauritianum, Cucurbita pepo). In the laboratory, the wasp will readily oviposit into larvae of all three flies but successfully develops only in B. tryoni. Bactrocera tryoni commonly infests S. lycopersicon (tomato), rarely S. mauritianum (wild tobacco) but never C. pepo (zucchini). The latter two plant species are common hosts for B. cacuminata and B. cucumis, respectively. 3 The parasitoid showed little or no response to uninfested plants of any of the test species. The presence of adult B. tryoni, however, increased parasitoid residency time on uninfested tomato. 4 When the three fruit types were all infested with larvae, parasitoid response was strongest to tomato, regardless of whether the larvae were physiologically suitable or unsuitable for offspring development. By contrast, zucchini was rarely visited by the wasp, even when infested with B. tryoni larvae. 5 Wild tobacco was infrequently visited when infested with B. cacuminata larvae but was more frequently visited, with greater parasitoid residency time and probing, when adult flies (either B. cacuminata or B. tryoni) were also present. 6 We conclude that herbivore-induced, nonspecific host fruit wound volatiles were the major cue used by foraging D. krausii. Although positive orientation to infested host plants is well known from previous studies on opiine braconids, the failure of the wasp to orientate to some plants even when infested with physiologically suitable larvae, and the secondary role played by adult fruit flies in wasp host searching, are newly-identified mechanisms that may aid parasitoid host location in environments where both physiologically suitable and unsuitable hosts occur.

A molecular phylogeny for the Tribe Dacini (Diptera: Tephritidae) : systematic and biogeographic implications

With well over 700 species, the Tribe Dacini is one of the most species-rich clades within the dipteran family Tephritidae, the true fruit flies. Nearly all Dacini belong to one of two very large genera, Dacus Fabricius and Bactrocera Macquart. The distribution of the genera overlap in or around the Indian subcontinent, but the greatest diversity of Dacus is in Africa and the greatest diversity of Bactrocera is in south-east Asia and the Pacific. The monophyly of these two genera has not been rigorously established, with previous phylogenies only including a small number of species and always heavily biased to one genus over the other. Moreover, the subgeneric taxonomy within both genera is complex and the monophyly of many subgenera has not been explicitly tested. Previous hypotheses about the biogeography of the Dacini based on morphological reviews and current distributions of taxa have invoked an out-of-India hypothesis; however this has not been tested in a phylogenetic framework. We attempted to resolve these issues with a dated, molecular phylogeny of 125 Dacini species generated using 16S, COI, COII and white eye genes. The phylogeny shows that Bactrocera is not monophyletic, but rather consists of two major clades: Bactrocera s.s. and the ‘Zeugodacus group of subgenera’ (a recognised, but informal taxonomic grouping of 15 Bactrocera subgenera). This ‘Zeugodacus’ clade is the sister group to Dacus, not Bactrocera and, based on current distributions, split from Dacus before that genus moved into Africa. We recommend that taxonomic consideration be given to raising Zeugodacus to genus level. Supportive of predictions following from the out-of-India hypothesis, the first common ancestor of the Dacini arose in the mid-Cretaceous approximately 80 mya. Major divergence events occurred during the Indian rafting period and diversification of Bactrocera apparently did not begin until after India docked with Eurasia (50–35 mya). In contrast, diversification in Dacus, at approximately 65 mya, apparently began much earlier than predicted by the out-of-India hypothesis, suggesting that, if the Dacini arose on the Indian plate, then ancestral Dacus may have left the plate in the mid to late Cretaceous via the well documented India–Madagascar–Africa migration route. We conclude that the phylogeny does not disprove the predictions of an out-of-India hypothesis for the Dacini, although modification of the original hypothesis is required.

Population structure of Bactrocera dorsalis s.s., B. papayae and B. philippinensis (Diptera: Tephritidae) in southeast Asia: evidence for a single species hypothesis using mitochondrial DNA and wingshape data

Background Bactrocera dorsalis s.s. is a pestiferous tephritid fruit fly distributed from Pakistan to the Pacific, with the Thai/Malay peninsula its southern limit. Sister pest taxa, B. papayae and B. philippinensis, occur in the southeast Asian archipelago and the Philippines, respectively. The relationship among these species is unclear due to their high molecular and morphological similarity. This study analysed population structure of these three species within a southeast Asian biogeographical context to assess potential dispersal patterns and the validity of their current taxonomic status. Results Geometric morphometric results generated from 15 landmarks for wings of 169 flies revealed significant differences in wing shape between almost all sites following canonical variate analysis. For the combined data set there was a greater isolation-by-distance (IBD) effect under a ‘non-Euclidean’ scenario which used geographical distances within a biogeographical ‘Sundaland context’ (r2 = 0.772, P < 0.0001) as compared to a ‘Euclidean’ scenario for which direct geographic distances between sample sites was used (r2 = 0.217, P < 0.01). COI sequence data were obtained for 156 individuals and yielded 83 unique haplotypes with no correlation to current taxonomic designations via a minimum spanning network. BEAST analysis provided a root age and location of 540kya in northern Thailand, with migration of B. dorsalis s.l. into Malaysia 470kya and Sumatra 270kya. Two migration events into the Philippines are inferred. Sequence data revealed a weak but significant IBD effect under the ‘non-Euclidean’ scenario (r2 = 0.110, P < 0.05), with no historical migration evident between Taiwan and the Philippines. Results are consistent with those expected at the intra-specific level. Conclusions Bactrocera dorsalis s.s., B. papayae and B. philippinensis likely represent one species structured around the South China Sea, having migrated from northern Thailand into the southeast Asian archipelago and across into the Philippines. No migration is apparent between the Philippines and Taiwan. This information has implications for quarantine, trade and pest management.

Fast power line detection and localization using steerable filter for active UAV guidance

In this paper we present a fast power line detection and localisation algorithm as well as propose a high-level guidance architecture for active vision-based Unmanned Aerial Vehicle (UAV) guidance. The detection stage is based on steerable filters for edge ridge detection, followed by a line fitting algorithm to refine candidate power lines in images. The guidance architecture assumes an UAV with an onboard Gimbal camera. We first control the position of the Gimbal such that the power line is in the field of view of the camera. Then its pose is used to generate the appropriate control commands such that the aircraft moves and flies above the lines. We present initial experimental results for the detection stage which shows that the proposed algorithm outperforms two state-of-the-art line detection algorithms for power line detection from aerial imagery.