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.

两栖机器人控制系统研究与实现

轮桨腿一体化两栖机器人是一种既可以在陆地、滩涂、海底爬行，又可以在 极浅水海域浮游的特种机器人。它巧妙地将水下机器人常用的螺旋桨推进器与陆 地爬行机器人的驱动轮结合为一体、将水下方向舵与陆地爬行腿结合为一体，实 现在水下浮游与陆地爬行运动模式之间自动的切换，从而能够在普通陆地爬行机 器人和水下浮游机器人无法进入的极浅水、碎浪带和海滩区域进行考察作业。 这种新型两栖机器人作业环境复杂、运动模式多样，其运行机理、控制策略 和建模方法等关键技术与传统的陆地或水下机器人有所不同。本文对轮桨腿一体 化两栖机器人控制系统进行研究，针对机器人具有的模块化、可重构和可扩展等 特性，采用开放式设计思想，完成了具有混合体系结构特点的控制系统设计，并 从硬件和软件两个方面对控制系统的实现进行了阐述。 在体系结构设计上，整个控制系统分为三层：慎思层、序列层和行为层。其 中慎思层负责基于推理的计算与决策，实现两栖机器人高层智能性；行为层负责 两栖机器人基于反应的反馈控制，其包容结构实现了两栖机器人对动态环境的快 速响应能力和适应能力；连接慎思层和行为层的序列层根据两栖机器人自身状态， 将慎思层的决策结果转化为行为层的执行序列。 在硬件设计上，控制系统由水面控制台子系统和载体控制子系统组成。水面 控制台子系统接收人的使命指令，分解成任务序列，通过CAN 总线或无线电下载 到载体控制子系统，实现慎思层的功能。载体控制子系统是由嵌入式主控计算机 节点、6 个驱动装置控制器节点、故障诊断与应急处理节点构成的基于高速CAN 总线的分布式控制系统，它根据接受到的任务目标，以及环境状态和机器人内部 状态，完成对机器人的实时控制，实现了整个系统序列层和行为层的功能。 在软件设计上，使用ANSI C 语言完成了各种硬件驱动设计、部分功能模块设 计工作。分布式控制系统各嵌入式节点在μC/OS-II 嵌入式实时操作系统的基础上 完成软件设计，并实现与其他节点之间的CAN 通信。 实验表明，本文设计的控制系统能够可靠、稳定工作，并具有良好的模块化 结构和开放性，为轮桨腿一体化两栖机器人样机的实现和各项关键技术的研究奠 定了良好的基础。

Efficient FPGA Hardware Development: A Multi-Language Approach

This paper presents a multi-language framework to FPGA hardware development which aims to satisfy the dual requirement of high-level hardware design and efficient hardware implementation. The central idea of this framework is the integration of different hardware languages in a way that harnesses the best features of each language. This is illustrated in this paper by the integration of two hardware languages in the form of HIDE: a structured hardware language which provides more abstract and elegant hardware descriptions and compositions than are possible in traditional hardware description languages such as VHDL or Verilog, and Handel-C: an ANSI C-like hardware language which allows software and hardware engineers alike to target FPGAs from high-level algorithmic descriptions. On the one hand, HIDE has proven to be very successful in the description and generation of highly optimised parameterisable FPGA circuits from geometric descriptions. On the other hand, Handel-C has also proven to be very successful in the rapid design and prototyping of FPGA circuits from algorithmic application descriptions. The proposed integrated framework hence harnesses HIDE for the generation of highly optimised circuits for regular parts of algorithms, while Handel-C is used as a top-level design language from which HIDE functionality is dynamically invoked. The overall message of this paper posits that there need not be an exclusive choice between different hardware design flows. Rather, an integrated framework where different design flows can seamlessly interoperate should be adopted. Although the idea might seem simple prima facie, it could have serious implications on the design of future generations of hardware languages.

PLUMED 2: New feathers for an old bird

Enhancing sampling and analyzing simulations are central issues in molecular simulation. Recently, we introduced PLUMED, an open-source plug-in that provides some of the most popular molecular dynamics (MD) codes with implementations of a variety of different enhanced sampling algorithms and collective variables (CVs). The rapid changes in this field, in particular new directions in enhanced sampling and dimensionality reduction together with new hardware, require a code that is more flexible and more efficient. We therefore present PLUMED 2 here a,complete rewrite of the code in an object-oriented programming language (C++). This new version introduces greater flexibility and greater modularity, which both extends its core capabilities and makes it far easier to add new methods and CVs. It also has a simpler interface with the MD engines and provides a single software library containing both tools and core facilities. Ultimately, the new code better serves the ever-growing community of users and contributors in coping with the new challenges arising in the field.

Program summary

Program title: PLUMED 2

Catalogue identifier: AEEE_v2_0

Program summary URL: http://cpc.cs.qub.ac.uk/summaries/AEEE_v2_0.html

Program obtainable from: CPC Program Library, Queen's University, Belfast, N. Ireland

Licensing provisions: Yes

No. of lines in distributed program, including test data, etc.: 700646

No. of bytes in distributed program, including test data, etc.: 6618136

Distribution format: tar.gz

Programming language: ANSI-C++.

Computer: Any computer capable of running an executable produced by a C++ compiler.

Operating system: Linux operating system, Unix OSs.

Has the code been vectorized or parallelized?: Yes, parallelized using MPI.

RAM: Depends on the number of atoms, the method chosen and the collective variables used.

Classification: 3, 7.7, 23. Catalogue identifier of previous version: AEEE_v1_0.

Journal reference of previous version: Comput. Phys. Comm. 180 (2009) 1961.

External routines: GNU libmatheval, Lapack, Bias, MPI. (C) 2013 Elsevier B.V. All rights reserved.

Controle vetorial de velocidade de uma máquina de indução sem mancais trifásica com bobinado dividido utilizando estimação neural de fluxo

This work describes the study and the implementation of the vector speed control for a three-phase Bearingless induction machine with divided winding of 4 poles and 1,1 kW using the neural rotor flux estimation. The vector speed control operates together with the radial positioning controllers and with the winding currents controllers of the stator phases. For the radial positioning, the forces controlled by the internal machine magnetic fields are used. For the radial forces optimization , a special rotor winding with independent circuits which allows a low rotational torque influence was used. The neural flux estimation applied to the vector speed controls has the objective of compensating the parameter dependences of the conventional estimators in relation to the parameter machine s variations due to the temperature increases or due to the rotor magnetic saturation. The implemented control system allows a direct comparison between the respective responses of the speed and radial positioning controllers to the machine oriented by the neural rotor flux estimator in relation to the conventional flux estimator. All the system control is executed by a program developed in the ANSI C language. The DSP resources used by the system are: the Analog/Digital channels converters, the PWM outputs and the parallel and RS-232 serial interfaces, which are responsible, respectively, by the DSP programming and the data capture through the supervisory system

Controle vetorial de velocidade de um motor de indução trifásico com estimação neural de fluxo

This work describes the study and the implementation of the speed control for a three-phase induction motor of 1,1 kW and 4 poles using the neural rotor flux estimation. The vector speed control operates together with the winding currents controller of the stator phasis. The neural flux estimation applied to the vector speed controls has the objective of compensating the parameter dependences of the conventional estimators in relation to the parameter machine s variations due to the temperature increases or due to the rotor magnetic saturation. The implemented control system allows a direct comparison between the respective responses of the speed controls to the machine oriented by the neural rotor flux estimator in relation to the conventional flux estimator. All the system control is executed by a program developed in the ANSI C language. The main DSP recources used by the system are, respectively, the Analog/Digital channels converters, the PWM outputs and the parallel and RS-232 serial interfaces, which are responsible, respectively, by the DSP programming and the data capture through the supervisory system

Simulation environment of distance protection with ATP and foreign models

This paper presents an interactive simulation environment for distance protection, developed with ATP and foreign models based on ANSI C. Files in COMTRADE format are possible to generate after ATP simulation. These files can be used to calibrate real relays. Also, the performance of relay algorithms with real oscillography events is possible to assess by using the ATP option for POSTPROCESS PLOT FILE (PPF). The main purpose of the work is to develop a tool to allow the analysis of diverse fault cases and to perform coordination studies, as well as, to allow the analysis of the relay's performance in the face of a real event. © 2011 IEEE.

Algoritmos de detecção de bordas implementados em FPGA

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Análise de proteção de linhas de transmissão através de relés numéricos e uso de models externos no ATP (Alternative Transient Program)

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Desarrollo de aplicaciones de comunicaciones inalámbricas en sistemas de monitorización estructural desarrollados en aeronáutica.

Los Sistemas de SHM o de monitorización de la integridad estructural surgen ante la necesidad de mejorar los métodos de evaluación y de test no destructivos convencionales. De esta manera, se puede tener controlado todo tipo de estructuras en las cuales su correcto estado o funcionamiento suponga un factor crítico. Un Sistema SHM permite analizar una estructura concreta capturando de manera periódica el estado de la integridad estructural, que en este proyecto se ha aplicado a estructuras aeronáuticas. P.A.M.E.L.A. (Phase Array Monitoring for Enhanced Life Assessment) es la denominación utilizada para definir una serie de equipos electrónicos para Sistemas SHM desarrollados por AERNOVA y los Grupos de Diseño Electrónico de las universidades UPV/EHU y UPM. Los dispositivos P.A.M.E.L.A. originalmente no cuentan con tecnología Wi-Fi, por lo que incorporan un módulo hardware independiente que se encarga de las comunicaciones inalámbricas, a los que se les denomina Nodos. Estos Nodos poseen un Sistema Operativo propio y todo lo necesario para administrar y organizar la red Mallada Wi-Fi. De esta manera se obtiene una red mallada inalámbrica compuesta por Nodos que interconectan los Sistemas SHM y que se encargan de transmitir los datos a los equipos que procesan los resultados adquiridos por P.A.M.E.L.A. Los Nodos son dispositivos empotrados que llevan instalados un firmware basado en una distribución de Linux para Nodos (o Routers), llamado Openwrt. Que para disponer de una red mallada necesitan de un protocolo orientado a este tipo de redes. Entre las opciones de protocolo más destacadas se puede mencionar: DSDV (Destination Sequenced Distance Vector), OLSR (Optimized Link State Routing), B.A.T.M.A.N-Adv (Better Approach To Mobile Adhoc Networking Advance), BMX (una versión de B.A.T.M.A.N-Adv), AODV (Ad hoc On-Demand Distance Vector) y el DSR (Dynamic Source Routing). Además de la existencia de protocolos orientados a las redes malladas, también hay organizaciones que se dedican a desarrollar firmware que los utilizan, como es el caso del firmware llamado Nightwing que utiliza BMX, Freifunk que utiliza OLSR o Potato Mesh que utiliza B.A.T.M.A.N-Adv. La ventaja de estos tres firmwares mencionados es que las agrupaciones que las desarrollan proporcionan las imágenes precompiladas del sistema,listas para cargarlas en distintos modelos de Nodos. En este proyecto se han instalado las imágenes en los Nodos y se han probado los protocolos BMX, OLSR y B.A.T.M.A.N.-Adv. Concluyendo que la red gestionada por B.A.T.M.A.N.-Adv era la que mejor rendimiento obtenía en cuanto a estabilidad y ancho de banda. Después de haber definido el protocolo a usar, se procedió a desarrollar una distribución basada en Openwrt, que utilice B.A.T.M.A.N.-Adv para crear la red mallada, pero que se ajuste mejor a las necesidades del proyecto, ya que Nightwing, Freifunk y Potato Mesh no lo hacían. Además se implementan aplicaciones en lenguaje ANSI C y en LabVIEW para interactuar con los Nodos y los Sistemas SHM. También se procede a hacer alguna modificación en el Hardware de P.A.M.E.L.A. y del Nodo para obtener una mejor integración entre los dos dispositivos. Y por ultimo, se prueba la transferencia de datos de los Nodos en distintos escenarios. ABSTRACT. Structural Health Monitoring (SHM) systems arise from the need of improving assessment methods and conventional nondestructive tests. Critical structures can be monitored using SHM. A SHM system analyzes periodically a specific structure capturing the state of structural integrity. The aim of this project is to contribute in the implementation of Mesh network for SHM system in aircraft structures. P.A.M.E.L.A. (Phase Array Monitoring for Enhanced Life Assessment) is the name for electronic equipment developed by AERNOVA, the Electronic Design Groups of university UPV/EHU and the Instrumentation and Applied Acoustics research group from UPM. P.A.M.E.L.A. devices were not originally equipped with Wi-Fi interface. In this project a separate hardware module that handles wireless communications (nodes) has been added. The nodes include an operating system for manage the Wi-Fi Mesh Network and they form the wireless mesh network to link SHM systems with monitoring equipment. Nodes are embedded devices with an installed firmware based on special Linux distribution used in routers or nodes, called OpenWRT. They need a Mesh Protocol to stablish the network. The most common protocols options are: DSDV (Destination Sequenced Distance Vector), OLSR (Optimized Link State Routing), BATMAN-Adv (Better Approach To Mobile Ad-hoc Networking Advance), BMX (a version of BATMAN-Adv) AODV (Ad hoc on-Demand Distance Vector) and DSR (Dynamic Source Routing). In addition, there are organizations that are dedicated to develope firmware using these Mesh Protocols, for instance: Nightwing uses BMX, Freifunk use OLSR and Potato Mesh uses BATMAN-Adv. The advantage of these three firmwares is that these groups develop pre-compiled images of the system ready to be loaded in several models of Nodes. In this project the images were installed in the nodes. In this way, BMX, OLSR and BATMAN-Adv have been tested. We conclude that the protocol BATMAN-Adv has better performance in terms of stability and bandwidth. After choosing the protocol, the objective was to develop a distribution based on OpenWRT, using BATMAN-Adv to create the mesh network. This distribution is fitted to the requirements of this project. Besides, in this project it has been developed applications in C language and LabVIEW to interact with the Nodes and the SHM systems. The project also address some modifications to the PAMELA hardware and the Node, for better integration between both elements. Finally, data transfer tests among the different nodes in different scenarios has been carried out.

Provisión de servicios de procesado de imágenes basados en arquitecturas orientadas a servicios

Con este proyecto se pretende crear un procedimiento general para la implantación de aplicaciones de procesado de imágenes en cámaras de video IP y la distribución de dicha información mediante Arquitecturas Orientadas a Servicios (SOA). El objetivo principal es crear una aplicación que se ejecute en una cámara de video IP y realice un procesado básico sobre las imágenes capturadas (detección de colores, formas y patrones) permitiendo distribuir el resultado del procesado mediante las arquitecturas SOA descritas en la especificación DPWS (Device Profile for Web Services). El estudio se va a centrar principalmente en la transformación automática de código de procesado de imágenes escrito en Matlab (archivos .m) a un código C ANSI (archivos .c) que posteriormente se compilará para la arquitectura del procesador de la cámara (arquitectura CRIS, similar a la RISC pero con un conjunto reducido de instrucciones). ABSTRACT. This project aims to create a general procedure for the implementation of image processing applications in IP video cameras and the distribution of such information through Service Oriented Architectures (SOA). The main goal is to create an application that runs on IP video camera and carry out a basic processing on the captured images ( color detection, shapes and patterns) allowing to distribute the result of process by SOA architectures described in the DPWS specification (Device Profile for Web Services). The study will focus primarily on the automated transform of image processing code written in Matlab files (. M) to ANSI C code files (. C) which is then compiled to the processor architecture of the camera (CRIS architecture , similar to the RISC but with a reduced instruction set).