This thesis focuses on the lower bounds for generic algorithms for discrete logarithms problem and Diffie-Hellman's problems. This thesis introduces two diffrent models of Black-Box for that purpose. On these models thesis approxi- mates and compares success probability of generic algorithms for given problems including Maurer's reduction. This reduction solves discrete logarithms problem using a appropriate elliptic curve and a Diffie-Hellman's oracle. This thesis also researches generic algorithm for identifiaction schemes, that are based on discrete logarithms problem. 1

Der Spigot-Ansatz ist eine elegante Vorgehensweise, spezielle numerische Werte zuverlässig, effizient und mit beliebiger Genauigkeit zu berechnen. Die Stärke des Ansatzes ist seine Effizienz, seine totale Korrektheit und seine mathematisch exakt begründete Sicherstellung einer gewünschten absoluten Genauigkeit. Seine Schwäche ist möglicherweise die eingeschränkte Anwendbarkeit. Es gibt in der Literatur Spigot-Berechnung für e und pi. Wurzelberechnung und Logarithmenberechnung gehören zu den Hauptergebnissen der Dissertation. In Kombination mit den Methoden der Reihentransformation von Zeilberger und Wilf bzw. von Gosper ist der Einsatz zur Berechnung von hypergeometrischen Reihen sehr Erfolg versprechend. Eine interessante offene Frage ist die Berechnung der Feigenbaumkonstanten mit dem Ansatz. 'Spigot' bedeutet 'sukzessive Extraktion von Wertanteilen': die Wertanteile werden extrahiert, als ob sie durch einen Hahn (englisch: spigot) gepumpt werden. Es ist dabei besonders interessant, dass in bestimmten Fällen ein Wert-Anteil mit einer Ziffer der Kodierung des Ergebnisses versehen werden kann. Der Spigot-Ansatz steht damit im Gegensatz zu den konventionellen Iterationsverfahren: in einem Schritt des Spigot-Ansatzes wird jeweils ein Wert-Anteil 'extrahiert' und das gesamte Ergebnis ist die Summe der Wert-Anteile; während ein Schritt in einem Iterationsverfahren die Berechnung eines besseren gesamten Ergebnisses aus dem des vorigen Schritt beinhaltet. Das Grundschema der Berechnung mit dem Spigot-Ansatz sieht folgendermaßen aus: zuerst wird für den zu berechnenden numerischen Wert eine gut konvergierende Reihe mit rationalen Gliedern durch symbolisch-algebraische Methoden hergeleitet; dann wird für eine gewünschte Genauigkeit eine Teilsumme ausgewählt; anschließend werden aus der Teilsumme Wert-Anteile iterativ extrahiert. Die Extraktion von Wert-Anteilen aus der Teilsumme geschieht mit dem Spigot-Algorithmus, der auf Sale zurück geht, nur Integer-Arithmetik benötigt und sich als eine verallgemeinerte Form der Basis-Konvertierung dadurch auffassen lässt, dass die Teilsumme als die Kodierung des Wertes in einer inhomogenen Basis interpretiert wird. Die Spigot-Idee findet auch in der Überführung einer Reihe in eine besser konvergierende Reihe auf der Art und Weise Anwendung, dass Wert-Anteile aus der Reihe extrahiert werden, um die originale Reihe werttreu zur Reihe der Wert-Anteile zu transformieren. Dies geschieht mit den Methoden der Reihentransformation von Gosper bzw. Wilf. Die Dissertation umfasst im Wesentlichen die Formalisierung des Spigot-Algorithmus und der Gosperschen Reihentransformation, eine systematische Darstellung der Ansätze, Methoden und Techniken der Reihenentwiclung und Reihentransformation (die Herleitung von Reihen mit Hilfe charakteristischer Funktionalgleichungen; Methoden der Reihentransformation von Euler, Kummer, Markoff, Gosper, Zeilberger und Wilf) sowie die Methoden zur Berechnung von Wurzeln und Logarithmen mit dem Spigot-Ansatz. Es ist interessant zu sehen, wie sich die Grundideen des Spigot-Algorithmus, der Wurzelberechnung und der Logarithmenberechnung jeweils im Wesentlichen durch eine Gleichung ausdrücken lassen. Es ist auch interessant zu sehen, wie sich verschiedene Methoden der Reihentransformation auf einige einfache Grundideen zurückführen lassen. Beispiele für den Beweis von totalen Korrektheit (bei iterativer Berechnung von Wurzeln) könnte auch von starkem Interesse sein. Um die Zuverlässigkeit anderer Methoden zur Berechnung von natürlichen Logarithmen zu überprüfen, scheint der Vergleich der Ergebnisse mit den des Spigot-Ansatzes die beste Methode zu sein. Anders als bei Wurzelberechnung kann hierbei zur Überprüfung die inverse Berechnung nicht angewandt werden. / spigot, total correctness, acceleration of series, computation of roots, computation of logarithms Reliable numerical computations with spigot approach Spigot approach is an elegant way to compute special numerical values reliably, efficiently and with arbitrary accuracy. The advantage of this way are its efficiency and its total correctness including the bounding of the absolute error. The disadvantage is perhaps its restricted applicableness. There are spigot computation for e an pi. The computation of roots and logarithms belongs to the main results of this thesis. In combination with the methods for acceleration of series by Gosper as well as by Zeilberger and Wilf is the use for numerical summation of hypergeometric series very promising. An interesting open question is the computation of the Feigenbaum constant by this way. ‘Spigot’ means ‘successive extraction of portions of value’: the portions of value are ‘extracted’ as if they were pumped through a spigot. It is very interesting in certain case, where these portions can be interpreted as the digits of the result. With respect to that the spigot approach is the opposition to the iterative approach, where in each step the new better result is computed from the result of the previous step. The schema of spigot approach is characterised as follows: first a series for the value to be computed is derived, then a partial sum of the series is chosen with respect to an desired accuracy, afterwards the portions of value are extracted from the sum. The extraction of potions of value is carried by the spigot algorithm which is due to Sale an requires only integer arithmetic. The spigot algorithm can be understood as a generalisation of radix-conversion if the sum is interpreted as an encoding of the result in a mixed-radix (inhomogeneous) system. The spigot idea is also applied in transferring a series into a better convergent series: portions of value are extracted successively from the original series in order to form the series of extracted potions which should have the same value as the original series. This transfer is carried with the methods for acceleration of series by Gosper and Wilf. The thesis incorporates essentially the formalisation of the spigot algorithm and the method of Gosper for acceleration of series, a systematisation of methods and techniques for derivation and acceleration of series (derivation of series for functions by using their characteristic functional equations; methods for acceleration of series by Euler, Kummer, Markov, Gosper Zeilberger and Wilf) as well as the methods for computation of roots and logarithms by spigot approach. It is interesting to see how to express the basic ideas for spigot algorithm, computation of roots and computation of logarithm respectively in some equations. It is also interesting to see how to build various methods for acceleration of series from some simple basic ideas. Examples for proof of total correctness (for iterative computation of roots) can be of value to read. Comparing with the results produced by spigot approach is possibly the best way for verifying the reliability of other methods for computation of natural logarithms, because (as opposed to root computing) the verification by inverse computation is inapplicable.

Made available in DSpace on 2016-04-27T17:12:56Z (GMT). No. of bitstreams: 1 dissertacao_elpidio_araujo.pdf: 3591682 bytes, checksum: 1e6320d9be62313c3347706ab5174ea4 (MD5) Previous issue date: 2005-11-22 / Made available in DSpace on 2016-08-25T17:25:40Z (GMT). No. of bitstreams: 2 dissertacao_elpidio_araujo.pdf.jpg: 3662 bytes, checksum: 5abae02d1498a95126dea56a691f200b (MD5) dissertacao_elpidio_araujo.pdf: 3591682 bytes, checksum: 1e6320d9be62313c3347706ab5174ea4 (MD5) Previous issue date: 2005-11-22 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This research job has as goal to think up a Mathematics Educational Software for the high school students. The developed questions in this software have as goal to help in the learning of exponential and logarithm functions that will provide the users with informations that will contribute to the development of the planned activities. Our main focus is the student , thus his insertion in a computerized environment opens up one more option to his learning. The development of the software utilized, as basis, researches involving teachers of Elementary School and High School from private and public schools of São Paulo state. The main theme of the investigation was the difficulty that the students present on the comprehension of the exponential and logarithm functions. This research job hunts for an answer for the following inquiry: At which measure the software utilization as teaching tool of the Mathematics contents, related on exponential and logarithm functions, may contribute to the students learning? The activities were thought up based on the needs of the students identified during the research teachers. The software application promoted, in the students, a positive attitude in relation to the solutions of the proposals questions. / Este trabalho tem como objetivo conceber para alunos do Ensino Médio um Software Educacional de Matemática. As questões desenvolvidas neste software têm como objetivo auxiliar na aprendizagem das funções exponenciais e logarítmicas. Elas proporcionarão aos seus usuários informações que contribuirão para o desenvolvimento das atividades. Como nosso foco principal é o aluno, a sua inserção num ambiente informatizado abre uma opção a mais para a sua aprendizagem. O desenvolvimento do software utilizou como base pesquisas realizadas com os professores que ministram aulas no Ensino Fundamental e Médio da rede pública e privada do Estado de São Paulo. O tema principal da investigação foi a dificuldade que os alunos apresentam na compreensão das funções exponenciais e logarítmicas. Este trabalho procura responder a seguinte questão: em que medida a utilização de um software como ferramenta didática no estudo de conteúdos matemáticos relacionados com as funções exponenciais e logarítmicas contribui na aprendizagem do aluno? As atividades foram concebidas a partir das necessidades identificadas na pesquisa com os professores. A aplicação do software desenvolveu nos alunos uma atitude positiva em relação à resolução das questões.

CAPES / Neste trabalho apresenta-se uma proposta para o ensino de funções exponenciais e logarítmicas, precedido pelo conceito de Progressões que permite ao professor do ensino médio tratar do conceito de função exponenciais e logarítmica de maneira mais clara e construtivista para o aluno. Propõe-se a construção do conhecimento através de atividades de modelagem matemática desenvolvidas a partir do uso de tabelas construídas em planilhas eletrônicas e em um ambiente de geometria dinâmica (GeoGebra), explorando as ideias intuitivas de variação e caracterização dessas funções reais a partir das progressões no domínio discreto. Apresenta-se sugestões de atividades interdisciplinares envolvendo estimativas através do ajuste de curvas. / This work presents a proposal for teaching exponential and logarithmic functions, preceded by the concept of progressions which allows high school teacher dealing with the concept of exponential and logarithmic function more clear and constructive way for the student. Proposes the construction of knowledge through mathematical modeling developed from the use of built in spreadsheets and dynamic geometry (GeoGebra) environment tables activities, exploring the intuitive ideas of variation and characterization of these real functions from progressions in discrete domain. Presents suggestions for interdisciplinary activities involving estimates by adjusting curves.

CAPES / Neste trabalho apresenta-se uma proposta para o ensino de funções exponenciais e logarítmicas, precedido pelo conceito de Progressões que permite ao professor do ensino médio tratar do conceito de função exponenciais e logarítmica de maneira mais clara e construtivista para o aluno. Propõe-se a construção do conhecimento através de atividades de modelagem matemática desenvolvidas a partir do uso de tabelas construídas em planilhas eletrônicas e em um ambiente de geometria dinâmica (GeoGebra), explorando as ideias intuitivas de variação e caracterização dessas funções reais a partir das progressões no domínio discreto. Apresenta-se sugestões de atividades interdisciplinares envolvendo estimativas através do ajuste de curvas. / This work presents a proposal for teaching exponential and logarithmic functions, preceded by the concept of progressions which allows high school teacher dealing with the concept of exponential and logarithmic function more clear and constructive way for the student. Proposes the construction of knowledge through mathematical modeling developed from the use of built in spreadsheets and dynamic geometry (GeoGebra) environment tables activities, exploring the intuitive ideas of variation and characterization of these real functions from progressions in discrete domain. Presents suggestions for interdisciplinary activities involving estimates by adjusting curves.

The problem of feature selection is critical in several areas of machine learning and data analysis such as, for example, cancer classification using gene expression data, text categorization, etc. In this work, we consider feature selection for supervised learning problems, where one wishes to select a small set of features that facilitate learning a good prediction model in the reduced feature space. Our interest is primarily in filter methods that select features independently of the learning algorithm to be used and are generally faster to implement compared to other types of feature selection algorithms. Many common filter methods for feature selection make use of information-theoretic criteria such as those based on mutual information to guide their search process. However, even in simple binary classification problems, mutual information based methods do not always select the best set of features in terms of the Bayes error. In this thesis, we develop a general approach for selecting a set of features that directly aims to minimize the Bayes error in the reduced feature space with respect to the loss or performance measure of interest. We show that the mutual information based criterion is a special case of our setting when the loss function of interest is the logarithmic loss for class probability estimation. We give a greedy forward algorithm for approximately optimizing this criterion and demonstrate its application to several supervised learning problems including binary classification (with 0-1 error, cost-sensitive error, and F-measure), binary class probability estimation (with logarithmic loss), bipartite ranking (with pairwise disagreement loss), and multiclass classification (with multiclass 0-1 error). Our experiments suggest that the proposed approach is competitive with several state-of-the art methods.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal.

Dans cette thèse, on étudie deux types d’équations diophantiennes. Une première partie de notre étude porte sur la résolution des équations dites de Ramanujan-Nagell Cx2+ b2mD = yn. Une deuxième partie porte sur les équations dites de Ngell-Ljunggren xp+ypx+y = pezq incluant le cas diagonal p = q. Les nouveaux réesultats obtenus seront appliqués aux équations de la forme xp + yp = Bzq. L’équation de Catalan-Fermat (cas B = 1) fera l’objet d’un traitement à part. / In this thesis, we study two types of diophantine equations. A ?rst part of our study is about the resolution of the Ramanujan-Nagell equations Cx2 + b2mD = yn. A second part of our study is about the Nagell-Ljungren equations xp+yp x+y = pezq including the diagonal case p = q. Our new results will be applied to the diophantine equations of the form xp + yp = Bzq. The Fermat-Catalan equation (case B = 1) will be the subject of a special study.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

No description available.