Sofisticadas técnicas para estimação de modelos baseadas em simulação, os filtros de partículas ou métodos de Monte Carlo Seqüenciais, foram empregadas recentemente para solucionar diversos problemas difícieis no campo da robótica móvel. No entanto, o sucesso dos fitros de partículas limitou-se à computação de parâmetros em espaços de baixa dimensionalidade. Os atuais esforços de pesquisa em robótica móvel têm comecado a explorar certas propriedades estruturais de seus domnios de aplicação que envolvem a utilização de filtros de partculas em espacos de maior dimensão, aumentando consideravelmente a complexidade da simulação envolvida. Simulações estatsticas dessa natureza requerem uma grande quantidade de numeros pseudo-aleatorios que possam ser gerados eficientemente e atendam a certos criterios de qualidade. O processo de geração de numeros pseudo-aleatorios torna-se o ponto crtico de tais aplicações em termos de desempenho. Neste contexto, a computação reconguravel insere-se como uma tecnologia capaz de satisfazer a demanda por alto desempenho das grandes simulações estatsticas pois sistemas baseados em arquiteturas reconguraveis possuem o potencial de mapear computação em hardware visando aumento de eficiência sem comprometer seriamente sua exibilidade. Tecnologias reconguraveis também possui o atrativo de um baixo consumo de energia, uma caracterstica essencial para os futuros robôs moveis embarcados. Esta dissertação apresenta a implementação um sistema embarcado baseado em FPGA e projetado para solucionar o problema de localização de robôs por meio de tecnicas probabilsticas. A parte fundamental de todo este sistema e um veloz gerador de numeros aleatorios mapeado ao hardware reconguravel que foi capaz de atender rígidos criterios estatsticos de qualidade / Sophisticated techniques for estimation of models based on simulation, particle filters or Sequential Monte Carlo Methods, were recently used to solve many difficult problems in the field of mobile robotics. However, the success of particle filters was limited to the computation of parameters in low dimensionality spaces. The current research efforts in mobile robotics have begun to explore some structural properties of their application\'s domain involving the use of particle filters in spaces of a higher dimension, greatly increasing the complexity of the involved simulation. Statistical simulations of this nature require a lot of pseudorandom numbers that can be generated efficiently and meet certain quality criteria. The process of generating pseudorandom number becomes the critical point of such applications in terms of performance. In this context, reconfigurable computing is a technology capable of meeting the demand for high performance of large statistical simulations because systems based on reconfigurable architectures have the potential to map computation to hardware aiming to increase eficiency without a serious drawback in exibility. Reconfigurable technologies are also attractive because of their low energy consume, a essential feature for the future mobile robots. This dissertation presents an implementation of a FPGA based embedded system designed to solve the robot localization problem by the means of probabilistic technics. The fundamental part from the whole system is a fast random number generator mapped to reconfigurable hardware wich atends a rigid quality criteria

Monte Carlo é o nome dado de forma geral às técnicas de resolução de problemas numéricos através do uso intensivo de números aleatórios. No trato computacional, esses números não são, de fato, aleatórios, mas pseudo-aleatórios, pois são gerados por algoritmos determinísticos que, no entanto, “parecem” aleatórios, isto é, são aprovados em testes de aleatoriedade. Variáveis aleatórias com quaisquer distribuições de probabilidade são então simuladas a partir de números pseudo-aleatórios uniformemente distribuídos no intervalo (0;1) através de certas transformações. Entre as diversas aplicações do método Monte Carlo destaca-se a quadratura numérica multidimensional, que consiste essencialmente em estimar o valor médio da função integranda através do valor médio da função em pontos escolhidos de modo aleatório no interior da região de integração. Técnicas especiais de amostragem permitem a redução da variância e, em conseqüência, do erro nos valores estimados. O erro de convergência do método é, no pior caso, de ordem O(n-1/2). No entanto o uso de pontos amostrais quase-aleatórios pode levar a convergência mais rápida de ordem O(n-1). O presente trabalho descreve uma grande quantidade de algoritmos para obtenção de variáveis pseudo-aleatórias e quasealeatórias ; para a transformação de diversas distribuições de probabilidade e para quadratura multidimensional. / Monte Carlo is the name usually given to numerical problems resolution techniques by intensive use of random numbers. In computer procedures, this numbers are not, in fact, random but pseudo-random because they are generated by deterministic algorithms, but “look like” random, that is, they pass on randomness tests. Such random variables with any probability distribution are simulated on pseudo-random numbers with uniform distribution in (0;1) by certain transformations. Among a diversity of Monte Carlo methods applications, a special one is the multidimensional numeric quadrature which consists essentially of estimating tha integrand function mean value by the mean that function at random points in the integration region. Sampling techniques allow a variance reduction and hence an estimated error reduction. The error convergence order is, in the worst case, O(n-1/2). However quasi-random sampling points could bring a faster convergence order of O(n-1). The present work describes a wide quantity of algorithms for producing pseudo-random and quasi-random variables; for transforming a diversity of probability distributions, and for multidimensional quadrature.

Monte Carlo é o nome dado de forma geral às técnicas de resolução de problemas numéricos através do uso intensivo de números aleatórios. No trato computacional, esses números não são, de fato, aleatórios, mas pseudo-aleatórios, pois são gerados por algoritmos determinísticos que, no entanto, “parecem” aleatórios, isto é, são aprovados em testes de aleatoriedade. Variáveis aleatórias com quaisquer distribuições de probabilidade são então simuladas a partir de números pseudo-aleatórios uniformemente distribuídos no intervalo (0;1) através de certas transformações. Entre as diversas aplicações do método Monte Carlo destaca-se a quadratura numérica multidimensional, que consiste essencialmente em estimar o valor médio da função integranda através do valor médio da função em pontos escolhidos de modo aleatório no interior da região de integração. Técnicas especiais de amostragem permitem a redução da variância e, em conseqüência, do erro nos valores estimados. O erro de convergência do método é, no pior caso, de ordem O(n-1/2). No entanto o uso de pontos amostrais quase-aleatórios pode levar a convergência mais rápida de ordem O(n-1). O presente trabalho descreve uma grande quantidade de algoritmos para obtenção de variáveis pseudo-aleatórias e quasealeatórias ; para a transformação de diversas distribuições de probabilidade e para quadratura multidimensional. / Monte Carlo is the name usually given to numerical problems resolution techniques by intensive use of random numbers. In computer procedures, this numbers are not, in fact, random but pseudo-random because they are generated by deterministic algorithms, but “look like” random, that is, they pass on randomness tests. Such random variables with any probability distribution are simulated on pseudo-random numbers with uniform distribution in (0;1) by certain transformations. Among a diversity of Monte Carlo methods applications, a special one is the multidimensional numeric quadrature which consists essentially of estimating tha integrand function mean value by the mean that function at random points in the integration region. Sampling techniques allow a variance reduction and hence an estimated error reduction. The error convergence order is, in the worst case, O(n-1/2). However quasi-random sampling points could bring a faster convergence order of O(n-1). The present work describes a wide quantity of algorithms for producing pseudo-random and quasi-random variables; for transforming a diversity of probability distributions, and for multidimensional quadrature.

Monte Carlo é o nome dado de forma geral às técnicas de resolução de problemas numéricos através do uso intensivo de números aleatórios. No trato computacional, esses números não são, de fato, aleatórios, mas pseudo-aleatórios, pois são gerados por algoritmos determinísticos que, no entanto, “parecem” aleatórios, isto é, são aprovados em testes de aleatoriedade. Variáveis aleatórias com quaisquer distribuições de probabilidade são então simuladas a partir de números pseudo-aleatórios uniformemente distribuídos no intervalo (0;1) através de certas transformações. Entre as diversas aplicações do método Monte Carlo destaca-se a quadratura numérica multidimensional, que consiste essencialmente em estimar o valor médio da função integranda através do valor médio da função em pontos escolhidos de modo aleatório no interior da região de integração. Técnicas especiais de amostragem permitem a redução da variância e, em conseqüência, do erro nos valores estimados. O erro de convergência do método é, no pior caso, de ordem O(n-1/2). No entanto o uso de pontos amostrais quase-aleatórios pode levar a convergência mais rápida de ordem O(n-1). O presente trabalho descreve uma grande quantidade de algoritmos para obtenção de variáveis pseudo-aleatórias e quasealeatórias ; para a transformação de diversas distribuições de probabilidade e para quadratura multidimensional. / Monte Carlo is the name usually given to numerical problems resolution techniques by intensive use of random numbers. In computer procedures, this numbers are not, in fact, random but pseudo-random because they are generated by deterministic algorithms, but “look like” random, that is, they pass on randomness tests. Such random variables with any probability distribution are simulated on pseudo-random numbers with uniform distribution in (0;1) by certain transformations. Among a diversity of Monte Carlo methods applications, a special one is the multidimensional numeric quadrature which consists essentially of estimating tha integrand function mean value by the mean that function at random points in the integration region. Sampling techniques allow a variance reduction and hence an estimated error reduction. The error convergence order is, in the worst case, O(n-1/2). However quasi-random sampling points could bring a faster convergence order of O(n-1). The present work describes a wide quantity of algorithms for producing pseudo-random and quasi-random variables; for transforming a diversity of probability distributions, and for multidimensional quadrature.

Sofisticadas técnicas para estimação de modelos baseadas em simulação, os filtros de partículas ou métodos de Monte Carlo Seqüenciais, foram empregadas recentemente para solucionar diversos problemas difícieis no campo da robótica móvel. No entanto, o sucesso dos fitros de partículas limitou-se à computação de parâmetros em espaços de baixa dimensionalidade. Os atuais esforços de pesquisa em robótica móvel têm comecado a explorar certas propriedades estruturais de seus domnios de aplicação que envolvem a utilização de filtros de partculas em espacos de maior dimensão, aumentando consideravelmente a complexidade da simulação envolvida. Simulações estatsticas dessa natureza requerem uma grande quantidade de numeros pseudo-aleatorios que possam ser gerados eficientemente e atendam a certos criterios de qualidade. O processo de geração de numeros pseudo-aleatorios torna-se o ponto crtico de tais aplicações em termos de desempenho. Neste contexto, a computação reconguravel insere-se como uma tecnologia capaz de satisfazer a demanda por alto desempenho das grandes simulações estatsticas pois sistemas baseados em arquiteturas reconguraveis possuem o potencial de mapear computação em hardware visando aumento de eficiência sem comprometer seriamente sua exibilidade. Tecnologias reconguraveis também possui o atrativo de um baixo consumo de energia, uma caracterstica essencial para os futuros robôs moveis embarcados. Esta dissertação apresenta a implementação um sistema embarcado baseado em FPGA e projetado para solucionar o problema de localização de robôs por meio de tecnicas probabilsticas. A parte fundamental de todo este sistema e um veloz gerador de numeros aleatorios mapeado ao hardware reconguravel que foi capaz de atender rígidos criterios estatsticos de qualidade / Sophisticated techniques for estimation of models based on simulation, particle filters or Sequential Monte Carlo Methods, were recently used to solve many difficult problems in the field of mobile robotics. However, the success of particle filters was limited to the computation of parameters in low dimensionality spaces. The current research efforts in mobile robotics have begun to explore some structural properties of their application\'s domain involving the use of particle filters in spaces of a higher dimension, greatly increasing the complexity of the involved simulation. Statistical simulations of this nature require a lot of pseudorandom numbers that can be generated efficiently and meet certain quality criteria. The process of generating pseudorandom number becomes the critical point of such applications in terms of performance. In this context, reconfigurable computing is a technology capable of meeting the demand for high performance of large statistical simulations because systems based on reconfigurable architectures have the potential to map computation to hardware aiming to increase eficiency without a serious drawback in exibility. Reconfigurable technologies are also attractive because of their low energy consume, a essential feature for the future mobile robots. This dissertation presents an implementation of a FPGA based embedded system designed to solve the robot localization problem by the means of probabilistic technics. The fundamental part from the whole system is a fast random number generator mapped to reconfigurable hardware wich atends a rigid quality criteria

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-10-01T16:46:31Z No. of bitstreams: 1 ELLOÁ BARRETO GUEDES DA COSTA - DISSERTAÇÃO PPGCC 2011..pdf: 1433883 bytes, checksum: fb9fa0561b94ab2b495915f5f377c364 (MD5) / Made available in DSpace on 2018-10-01T16:46:31Z (GMT). No. of bitstreams: 1 ELLOÁ BARRETO GUEDES DA COSTA - DISSERTAÇÃO PPGCC 2011..pdf: 1433883 bytes, checksum: fb9fa0561b94ab2b495915f5f377c364 (MD5) Previous issue date: 2011-03-25 / Este trabalho apresenta um ataque quântico de comprometimento permanente ao gerador pseudo-aleatório de Blum-Micali. A segurança deste gerador, classificado como criptograficamente seguro, baseia-se na hipótese de intratabilidade do problema do logaritmo discreto perante a Computação Clássica. O ataque proposto faz uso do algoritmo quântico de busca em conjunto com o algoritmo quântico para o logaritmo discreto para comprometer a imprevisibilidade do gerador, recuperando todas as saídas passadas e futuras do mesmo. O presente trabalho também descreve generalizações deste ataque que o adequam a uma gama mais vasta de geradores, incluindo geradores da Construção de Blum-Micali e geradores com múltiplos predicados difíceis. Tais generalizações também abrangem a realização de ataques em situações adversas, por exemplo, quando o adversário captura bits não consecutivos ou quando há menos bits que o requerido. Comparado à sua contrapartida clássica, o algoritmo quântico proposto nesse trabalho possui um ganho quadrático em relação à recuperação do representante do estado interno do gerador, seguido de um ganho superpolinomial na obtenção dos demais elementos do estado interno. Estes resultados caracterizam ameaças,elaboradas com Computação Quântica, contra a segurança de geradores utilizados em diversas aplicações criptográficas. / This dissertation presents a quantum permanent compromise attack to the Blum-Micali pseudorandom generator. The security of this generator, classified as cryptographically secure, is based on the hypothesis of intractability of the discrete logarithm problem in Classical Computing. The proposed attack is based on the quantum search algorithm jointly with the quantum discrete logarithm procedure and aims to compromise the unpredictability of the referred generator, recovering all of its past and future outputs. This work also describes generalizations that enables attacks to generators from the Blum-Micali construction and also to generators with multiple hard-core predicates. Such generalizations also allow attacks when the adversary intercepts non-consecutive bits or when there are less bits than required. Compared to its classical counterpart, the proposed algorithm has a quadractic speedup regarding the retrieval of the representant of the generator’s internal state followed by a super polynomial speedup regarding the obtention of the entire generator’sinternalstate. These results represent menaces of the Quantum Computing paradigm against the security of pseudorandom generators adopted in many real-world cryptosystems.