Os polinômios possuem características e propriedades que os tornam bastante importantes, seja modelando problemas da natureza e do cotidiano ou servindo como ferramenta de resolução de problemas ou, ainda, para alcançar resultados matemáticos mais avançados. O Currículo do Estado de São Paulo sugere uma sequência de conteúdos para serem trabalhados, levando o aluno a um aprendizado dos polinômios tanto do ponto de vista teórico quanto de aplicações. O ensino de polinômios é feito em espiral do 7º ano do Ensino Fundamental até o 3º ano do Ensino Médio, isto é, seu conteúdo é trabalhado gradativamente no decorrer dos anos escolares, sempre sendo retomado e aprofundado de acordo com o tempo escolar adequado. Este trabalho tem como objetivo contribuir com a formação de professores de Matemática do Ensino Básico apresentando uma sólida teoria sobre os polinômios no que diz respeito a definição, propriedades, operações algébricas, funções polinomiais, traçado de gráfico de polinômios e, já em um nível mais avançado, derivada e integral de polinômios. Além disso, revisamos os conceitos de espaços vetoriais, independência linear, base, projeções e ortogonalidade. A teoria apresentada é então utilizada no estudo de aproximações de funções por polinômios. Entre as formas de aproximação, apresentamos o polinômio de Taylor, a Interpolação Polinomial e o ajuste polinomial pelo Método dos Mínimos Quadrados. Ao longo do texto apresentamos aplicações no cotidiano como o cálculo do polinômio que descreve uma corrida de táxi, a fórmula 95 para aposentadoria e a curva de lucro de uma sorveteria em função do preço de seus sorvetes. / Polynomials have characteristics and properties that make them very important, modelling nature and daily problems or serving as a tool to solve problems, or even to achieve more advanced mathematical results. The curriculum of São Paulo state suggests a sequence of contents to be worked, leading the student to learning about polynomials from both the theoretical and the applications point of views. The polynomials teaching is done in a spiral way from the 7th year of elementary school to the 3rd year of high school, that is, its contents are gradually worked during the school years, always being resumed and deepened in accordance with the appropriate school time. This work aims to contribute to the training of basic education Mathematics teachers introducing them a solid theory of polynomials concerning about definition, properties, algebraic operations, polynomial functions, polynomial graphics and already at a more advanced level, derivative and integral of polynomials. In addition, we review the concepts of vector spaces, linear independence, base, projections and orthogonality. The presented theory is then used in the study of function approximations by polynomials. Among the forms of approach, we present the Taylor polynomial, the polynomial interpolation and polynomial fit by the least square method. Throughout the text we present applications in daily life such as the calculation of the polynomial that describes a taxi ride, the 95 formula for retirement and the the profit curve of an ice cream shop due to the price of their ice cream.

Diploma thesis deals with image interpolation. The aim of this work is to study theoretically and then describe the nature of the various methods of image interpolation and some of them implemented in the program MATLAB. The introductory part of this work theoretically closer to important terms that are closely related to this topic of digital image processing sufficient to understand the principle. In the following of the thesis will be discussed all of today's commonly used method of image interpolation. Will hear all about the method of image interpolation using nearest neightbor interpolation and image help of polynimals such as (bi)linear, (bi)quadratic and (bi)kubic method. Then work theoretically analyzes the theory of individual species curves and splines. More specifically, coming to their most frequently used variants of B-spline curves and ther generalizations called NURBS, with addressing the problem of interpolating these curves. The final chapter consists of the results achieved in the program MATLAB.

No description available.

L’aléatoire est un ingrédient clé en cryptographie. Par exemple, les nombres aléatoires sont utilisés pour générer des clés, pour le chiffrement et pour produire des nonces. Ces nombres sont générés par des générateurs pseudo-aléatoires et des fonctions pseudo-aléatoires dont les constructions sont basées sur des problèmes qui sont supposés difficiles. Dans cette thèse, nous étudions certaines mesures de complexité des fonctions pseudo-aléatoires de Naor-Reingold et Dodis-Yampolskiy et étudions la sécurité de certains générateurs pseudo-aléatoires (le générateur linéaire congruentiel et le générateur puissance basés sur les courbes elliptiques) et de certaines signatures à base de couplage basées sur le paradigme d’inversion. Nous montrons que la fonction pseudo-aléatoire de Dodis-Yampolskiy est uniformément distribué et qu’un polynôme multivarié de petit dégré ou de petit poids ne peut pas interpoler les fonctions pseudo-aléatoires de Naor-Reingold et de Dodis-Yampolskiy définies sur un corps fini ou une courbe elliptique. Le contraire serait désastreux car un tel polynôme casserait la sécurité de ces fonctions et des problèmes sur lesquels elles sont basées. Nous montrons aussi que le générateur linéaire congruentiel et le générateur puissance basés sur les courbes elliptiques sont prédictibles si trop de bits sont sortis à chaque itération. Les implémentations pratiques de cryptosystèmes souffrent souvent de fuites critiques d’informations à travers des attaques par canaux cachés. Ceci peut être le cas lors du calcul de l’exponentiation afin de calculer la sortie de la fonction pseudo-aléatoire de Dodis-Yampolskiy et plus généralement le calcul des signatures dans certains schémas de signatures bien connus à base de couplage (signatures de Sakai-Kasahara, Boneh-Boyen et Gentry) basées sur le paradigme d’inversion. Nous présentons des algorithmes (heuristiques) en temps polynomial à base des réseaux qui retrouvent le secret de celui qui signe le message dans ces trois schémas de signatures lorsque plusieurs messages sont signés sous l’hypothèse que des blocs consécutifs de bits des exposants sont connus de l’adversaire. / Randomness is a key ingredient in cryptography. For instance, random numbers are used to generate keys, for encryption and to produce nonces. They are generated by pseudo-random generators and pseudorandom functions whose constructions are based on problems which are assumed to be difficult. In this thesis, we study some complexity measures of the Naor-Reingold and Dodis-Yampolskiy pseudorandom functions and study the security of some pseudo-random generators (the linear congruential generator and the power generator on elliptic curves) and some pairing-based signatures based on exponentinversion framework. We show that the Dodis-Yampolskiy pseudo-random functions is uniformly distributed and that a lowdegree or low-weight multivariate polynomial cannot interpolate the Naor-Reingold and Dodis-Yampolskiy pseudo-random functions over finite fields and over elliptic curves. The contrary would be disastrous since it would break the security of these functions and of problems on which they are based. We also show that the linear congruential generator and the power generator on elliptic curves are insecure if too many bits are output at each iteration. Practical implementations of cryptosystems often suffer from critical information leakage through sidechannels. This can be the case when computing the exponentiation in order to compute the output of the Dodis-Yampolskiy pseudo-random function and more generally in well-known pairing-based signatures (Sakai-Kasahara signatures, Boneh-Boyen signatures and Gentry signatures) based on the exponent-inversion framework. We present lattice based polynomial-time (heuristic) algorithms that recover the signer’s secret in the pairing-based signatures when used to sign several messages under the assumption that blocks of consecutive bits of the exponents are known by the attacker.

Cette thèse vise à la conception de nouveaux algorithmes rapides en calcul numérique via les matrices de Toeplitz. Tout d'abord, nous avons introduit un algorithme rapide sur le calcul de l'inverse d'une matrice triangulaire de Toeplitz en se basant sur des notions d'interpolation polynomiale. Cet algorithme nécessitant uniquement deux FFT(2n) est manifestement efficace par rapport à ses prédécésseurs. ensuite, nous avons introduit un algorithme rapide pour la résolution d'un système linéaire de Toeplitz bande. Cette approche est basée sur l'extension de la matrice donnée par plusieurs lignes en dessus, de plusieurs colonnes à droite et d'attribuer des zéros et des constantes non nulles dans chacune de ces lignes et de ces colonnes de telle façon que la matrice augmentée à la structure d'une matrice triangulaire inférieure de Toeplitz. La stabilité de l'algorithme a été discutée et son efficacité a été aussi justifiée. Finalement, nous avons abordé la résolution d'un système de Toeplitz bandes par blocs bandes de Toeplitz. Ceci étant primordial pour établir la connexion de nos algorithmes à des applications en restauration d'images, un domaine phare en mathématiques appliquées. / This thesis aims to design new fast algorithms for numerical computation via the Toeplitz matrices. First, we introduced a fast algorithm to compute the inverse of a triangular Toeplitz matrix with real and/or complex numbers based on polynomial interpolation techniques. This algorithm requires only two FFT (2n) is clearly effective compared to predecessors. A numerical accuracy and error analysis is also considered. Numerical examples are given to illustrate the effectiveness of our method. In addition, we introduced a fast algorithm for solving a linear banded Toeplitz system. This new approach is based on extending the given matrix with several rows on the top and several columns on the right and to assign zeros and some nonzero constants in each of these rows and columns in such a way that the augmented matrix has a lower triangular Toeplitz structure. Stability of the algorithm is discussed and its performance is showed by numerical experiments. This is essential to connect our algorithms to applications such as image restoration applications, a key area in applied mathematics.