How to solve a multivariate quadratic polynomial equation system is believed to be one of the key points to beark AES. But to solve the MQE problem is NP-hard, so it's very important to develop a good algorithm to solve it. In such a situation, the XL algorithm is claimed to be the method to solve the MQE problem, and the cryptographers pay a lot of attetion to it. But the XL algorithm works only when the equation system is overdefined, for this reason cryptographers are looking for some ways, such as BES, to increase the numbers of equations. In practice we know that the process of solving MQE, the system will extend very fast, therefore if we input too many equations and variates, we usually using out of memory before finding out the solution. In the paper we use multiple plaintext-ciphertext to increase the number of equations and try to do some pre-computing work to reduce the size of a problem, and make it work better in pratice.

Submitted by Viviane Lima da Cunha (viviane@biblioteca.ufpb.br) on 2015-05-18T15:43:21Z No. of bitstreams: 2 arquivototal.pdf: 2728017 bytes, checksum: 0ba7ffbb932e751d626d29e41fd8c5df (MD5) license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) / Approved for entry into archive by Viviane Lima da Cunha (viviane@biblioteca.ufpb.br) on 2015-05-18T15:44:20Z (GMT) No. of bitstreams: 2 arquivototal.pdf: 2728017 bytes, checksum: 0ba7ffbb932e751d626d29e41fd8c5df (MD5) license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) / Made available in DSpace on 2015-05-18T15:44:20Z (GMT). No. of bitstreams: 2 arquivototal.pdf: 2728017 bytes, checksum: 0ba7ffbb932e751d626d29e41fd8c5df (MD5) license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) Previous issue date: 2013-08-15 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Since ancient times, for about 4000 years, many people have already solved polynomial equations in their daily lives through problems and practices constructions. In this paper, we study some algebraic and geometric methods used for solving polynomial equations. We start talking about factoring and division of polynomials, device Briot-Ruffini, relationships Girard, theorem of the complex roots and the theorem of the rational roots research. In chapter 2, we will show the methods algebraic of Viète, Cardano, Ferrari and Euler, and some geometric methods, such as the of proportion, of the Descartes and Thomas Carlyle and of the conicas. In section 3, we see the derivative of a polynomial, Newton's iterative method, translation of coordinate axes, using the derived for to find coeffcients of the reduced form of the polynomial and with the aid of derivatives show a method of resolution the equations 3rd and 4th degrees. / Desde a antiguidade, há mais ou menos 4000 anos, vários povos já resolviam equações polinomiais no seu cotidiano através de problemas e construções práticas. Neste trabalho, estudaremos alguns métodos algébricos e geométricos usados para resolução de equações polinomiais. Iniciaremos falando sobre fatoração e divisão de polinômios, dispositivo de Briot-Ruffini, relações de Girard, teorema das raízes complexas e o teorema de pesquisa das raízes racionais. No capítulo 2, mostraremos os métodos algébricos de Viète, Cardano, Ferrari e Euler, e alguns métodos geométricos, como o da proporção, o de Descartes e Thomas Carlyle e das cônicas. No capítulo 3, veremos a derivada de uma função polinomial, o método iterativo de Newton, translação de eixos coordenados, o uso da derivada para encontrar os coeficientes da forma reduzida das funções polinomiais e com auxílio de derivadas mostraremos um método de resolução para as equações do 3 e 4 graus.

Submitted by Cássia Santos (cassia.bcufg@gmail.com) on 2017-06-26T11:56:52Z No. of bitstreams: 2 Dissertação - Daniell Ferreira e Oliveira - 2017.pdf: 1683315 bytes, checksum: fed38bd9f52686f6e69de7205e93d8aa (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-07-10T13:59:48Z (GMT) No. of bitstreams: 2 Dissertação - Daniell Ferreira e Oliveira - 2017.pdf: 1683315 bytes, checksum: fed38bd9f52686f6e69de7205e93d8aa (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-07-10T13:59:48Z (GMT). No. of bitstreams: 2 Dissertação - Daniell Ferreira e Oliveira - 2017.pdf: 1683315 bytes, checksum: fed38bd9f52686f6e69de7205e93d8aa (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-05-30 / This paper aims to improve the understanding of Mathematics teachers regarding the solution of polynomial equations by means of radicals, focusing on the theory of Galois. The reader _nd in this document a little of Galois's life story, radical resolutions of degree n 4 equations, group, ring and body theories, as well as Galois Theory. / Este trabalho tem como objetivo aperfeiçoar a compreensão de professores de Matemática no que tange à solução de equações polinomiais por meio de radicais, com enfoque na Teoria de Galois. O leitor encontra neste, um pouco da história da vida de Galois, as resoluções por radicais de equações de grau n 4, as teorias de grupos, anéis e corpos, bem como a Teoria de Galois.

Some well-studied infinite-state stochastic models give rise to systems of nonlinear equations. These systems of equations have solutions that are probabilities, generally probabilities of termination in the model. We are interested in finding efficient, preferably polynomial time, algorithms for calculating probabilities associated with these models. The chief tool we use to solve systems of polynomial equations will be Newton’s method as suggested by [EY09]. The main contribution of this thesis is to the analysis of this and related algorithms. We give polynomial-time algorithms for calculating probabilities for broad classes of models for which none were known before. Stochastic models that give rise to such systems of equations include such classic and heavily-studied models as Multi-type Branching Processes, Stochastic Context- Free Grammars(SCFGs) and Quasi Birth-Death Processes. We also consider models that give rise to infinite-state Markov Decision Processes (MDPs) by giving algorithms for approximating optimal probabilities and finding policies that give probabilities close to the optimal probability, in several classes of infinite-state MDPs. Our algorithms for analysing infinite-state MDPs rely on a non-trivial generalization of Newton’s method that works for the max/min polynomial systems that arise as Bellman optimality equations in these models. For SCFGs, which are used in statistical natural language processing, in addition to approximating termination probabilities, we analyse algorithms for approximating the probability that a grammar produces a given string, or produces a string in a given regular language. In most cases, we show that we can calculate an approximation to the relevant probability in time polynomial in the size of the model and the number of bits of desired precision. We also consider more general systems of monotone polynomial equations. For such systems we cannot give a polynomial-time algorithm, which pre-existing hardness results render unlikely, but we can still give an algorithm with a complexity upper bound which is exponential only in some parameters that are likely to be bounded for the monotone polynomial equations that arise for many interesting stochastic models.

Neste trabalho, estudamos polinômios e equações polinomiais, apresentando orientações dos Parâmetros Curriculares Nacionais e informações de como alguns livros didáticos abordam o tema quanto ao tratamento, à metodologia e à priorização no planejamento escolar. Considerando polinômios com coeficientes reais ou complexos, buscamos condições sobre os coeficientes para que tais polinômios tenham raízes. Refletimos sobre como os professores de Matemática podem tratar o tema em sala de aula para obter resultados positivos e tornar a aprendizagem mais atrativa. Abordamos diversos resultados, como o Teorema do Resto, o dispositivo prático de Briot-Ruffini, o Teorema da Decomposição, as relações de Girard, o Teorema das Raízes Racionais, o Teorema Fundamental da Álgebra e as fórmulas de resolução de equações polinomiais por radicais até o quarto grau. Apresentamos uma abordagem para sala de aula com a utilização de um recurso computacional didático e instrumento de avaliação diferenciado. / In this dissertation, we study polynomials and polynomial equations, presenting guidelines from the National Curricular Parameters and information on how some textbooks discuss the topic regarding the treatment, the methodology and the prioritization in school planning. Considering polynomials with real or complex coefficients, we seek conditions on these coefficients so that we ensure that these polynomials have roots. We reflect on how Math teachers can address the topic in the classroom in order to get positive results making the learning more attractive. We address several results such as the Polynomial Remainder Theorem, the Briot-Ruffinis practical rule, the Decomposition Theorem, the Girards relations, the Rational Roots Theorem, the Fundamental Theorem of Algebra and the resolution formulas for polynomial equations by radicals up to the fourth degree. We present a lesson plan with the use of a teaching computational resource and differentiated evaluation tool.

Estudamos neste trabalho as equações polinomiais em sua abrangência: quadráticas, cúbicas e quárticas por diversos métodos clássicos, a limitação das raízes, resultados sobre equações polinomiais com coeficientes reais e inteiros, entre outros / We studied in this work polynomial equations in a wide reach: quadratic, cubic and quartic polynomials by several classical methods, the boundness of roots, results about polynomial equations with real and integer coefficients, among other results

CoordenaÃÃo de AperfeÃoamento de Pessoal de NÃvel Superior / Este trabalho visa contribuir para que alunos e professores do ensino mÃdio possam aprimorar seus conhecimentos matemÃticos em nÃmeros complexos, polinÃmios e equaÃÃes polinomiais. Inicialmente foi analisado o contexto histÃrico dos nÃmeros complexos, em seguida foram vistos alguns conceitos importantes como o de corpo dos nÃmeros complexos, unidade imaginÃria e plano complexo. AlÃm disso, foram apresentadas as propriedades e operaÃÃes bÃsicas dos polinÃmios, o dispositivo de Briot-Ruffini, atravÃs do qual podemos obter o quociente e o resto da divisÃo de um polinÃmio p(x) por um polinÃmio linear. Parte significativa deste trabalho foi dedicado ao estudo de equaÃÃes algÃbricas. Nessa perspectiva, foram discutidos alguns teoremas e mÃtodos resolutivos de equaÃÃes como o mÃtodo de Gustavo, que nos auxilia na resoluÃÃo de equaÃÃes do terceiro e do quarto graus, o teorema das raÃzes racionais, entre outros. Para tanto, foi essencial provar o Teorema Fundamental da Ãlgebra, que afirma que todo polinÃmio nÃo constante com coeficientes complexos possui pelo menos uma raiz complexa. Ademais, mostramos como podemos analisar o nÃmero de raÃzes reais de uma equaÃÃo polinomial com coeficientes reais. Nesse sentido, provamos o Teorema de Descartes, que diz que o nÃmero de raÃzes positivas de uma equaÃÃo nÃo supera o nÃmero de mudanÃas de sinal na sequÃncia dos seus coeficientes nÃo nulos. Provamos tambÃm o Teorema de Bolzano, que investiga o nÃmero de raÃzes reais de uma equaÃÃo num intervalo real e, finalmente, o Teorema de Lagrange que estabelece um limite superior das raÃzes reais de uma equaÃÃo. / This work aims to help students and high school teachers to improve their math skills in complex numbers, polynomials and polynomial equations. Initially it analysed the historical context of complex numbers then were seen some important concepts such as the body of complex numbers, imaginary unit and complex plane. In addition, the properties and basic operations of the polynomials were presented, the Briot-Ruffini device, through which we can get the quotient and remainder of the division of a polynomial p(x) by a linear polynomial. Significant part of this work was devoted to the study of algebraic equations. In this perspective, were discussed some theorems and methods of resolution of equations such as the method of Gustavo, who helps us in the resolution of equations of the third and fourth degrees, the theorem of rational roots, among others. For both, it was essential to prove the Fundamental Theorem of Algebra, which says that all polynomial not constant with complex coeficients has at least one complex root. Furthermore, we show how we can analyze the number of real roots of a polynomial equation with real coeficients. In this sense, we will prove the Theorem of Descartes, which says that the number of positive roots of an equation does not exceed the number of signal changes following its non-zero coeficients. We prove the theorem of Bolzano, which investigates the number of real roots of an equation in a real interval and finally the theorem of Lagrange the establishes an upper limit on roots of an equation.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2014-09-22T11:18:05Z No. of bitstreams: 2 Queiroz, Cleber da Costa.pdf: 1949775 bytes, checksum: fb4f5a0a7954a1b830a3614a3d55d110 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2014-09-22T11:29:10Z (GMT) No. of bitstreams: 2 Queiroz, Cleber da Costa.pdf: 1949775 bytes, checksum: fb4f5a0a7954a1b830a3614a3d55d110 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2014-09-22T11:29:10Z (GMT). No. of bitstreams: 2 Queiroz, Cleber da Costa.pdf: 1949775 bytes, checksum: fb4f5a0a7954a1b830a3614a3d55d110 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2013-03-22 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This paper aims to study the algebric methods to solve polynomial equations, with a deeper study about 3rd grade polynomial equations. It firstly broaches the historical aspects about polynomial functions by mentioning some mathematicians who collaborated to the obtainment of these resolutive methods. One chapter is designated to the study of complexes numbers and polynomial that have a great importance to theme development. The objective was not to deepen in the study of complexes numbers and polynomial, but to put in relief the definitions, properties and theorems that are considerable to the paper base, once that a polynomial equation has at least a complex root (Fundamental Theorem of Algebra) and that we always use the knowledge about the polynomial equations. By the end, resolutive methods for polynomial equations until 4rd grade are presented, emphasizing Cardano’s Formule and the algebric method for the 4rd grade equation, besides making a study about the relation between the coefficient and the roots of the 3rd grade equation, analysis of 3rd grade equation roots and the study of the 3rd grade function’s graphic. / Este trabalho tem por objetivo estudar os métodos algébricos para resolução das equações polinomiais onde destinamos um estudo mais aprofundado para as equações polinomiais do 3o grau. Inicialmente fazemos uma abordagem dos aspectos históricos relacionados às funções polinomiais citando alguns dos matemáticos que colaboraram para obtenção desses métodos resolutivos. Destinamos um capítulo ao estudo dos números complexos e polinômios, os quais são de fundamental importância para o desenvolvimento do tema. Nosso objetivo não foi de aprofundar o estudo de números complexos e polinômios, mas sim destacar as definições, propriedades e teoremas mais relevantes para a fundamentação do trabalho, visto que uma equação polinomial possui pelo menos uma raiz complexa (Teorema Fundamental da Álgebra) e que sempre utilizamos os conhecimentos a respeito das equações polinomiais. Por fim, mostramos métodos resolutivos para equações polinomiais até o grau 4, destacando a Fórmula de Cardano e o método algébrico para equação do 4o grau, além de fazer um estudo sobre a relação entre os coeficientes e as raízes da equação do 3o grau, análise das raízes da equação do 3o grau e estudo sobre o gráfico da função do 3o grau.

The theory of solving polynomial systems by homotopy continuation method has been proposed by Garcia, Zangwill and Drexler, and the most typical method in this category is total degree homotpy. The numerical implementation of tracking homotopy curves can be taken as two parts: prediction and correction. In this thesis we compare the performance of several prediction methods in the total degree homotopy, including Runge-Kutta method, Adams-Bashforth method and cubic Hermite method. In addition, we design an adaptive stepsize control algorithm in path tracking, which is based on the information obtained during Newton correction process. The numerical experiment shows that the stepsize control algorithm is quite efficient and reliable in path tracking. In the end we employ the algorithm for solving eigenvalue problems by random product homotopy method

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This dissertation aims to propose a new approach in teaching polynomials. As this subject is worked in the last year of high school, we offer a proposal focused on higher education, but in an investigative and intuitive way while emphasizing the definitions and theorems. In the first chapter we will make a historical overview about the study of polynomials, highlighting the most important facts and their researchers, as well as their relevance. In the second chapter we will deal with the way the subject is approached in schools and books currently in high school in Brazil, emphasizing the important aspects that we think should be revised. A new proposal for the study of polynomials is presented in the third chapter. We conclude with the fourth chapter where we report the partial application of this proposal in a class of third year of the technical computer course in IFRS - Câmpus Ibirubá. / O presente trabalho de dissertação tem como objetivo propor uma nova forma de abordagem no ensino de polinômios. Como este assunto é trabalhado no último ano do Ensino Médio, oferecemos uma proposta focada no Ensino Superior, porém de uma forma investigativa e intuitiva sem deixar de dar ênfase às definições e teoremas. No primeiro capítulo faremos um apanhado histórico sobre o estudo dos polinômios destacando os principais fatos e seus estudiosos, bem como sua relevância. No segundo capítulo trataremos sobre a forma que o assunto é abordado atualmente nas escolas e livros de Ensino Médio do Brasil, salientando os aspectos que consideramos importantes que sejam revistos. Uma nova proposta de trabalho de estudo de polinômios é apresentada no terceiro capítulo. Concluímos com o quarto capítulo onde relataremos a aplicação parcial desta proposta em uma turma de terceiro ano técnico em informática do IFRS Câmpus Ibirubá.