Dissertations / Theses on the topic 'Arithmetic applications'
To see the other types of publications on this topic, follow the link: Arithmetic applications.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Arithmetic applications.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Hanss, Michael. "Applied fuzzy arithmetic : an introduction with engineering applications /." Berlin [u.a.] : Springer, 2005. http://www.loc.gov/catdir/enhancements/fy0662/2004117177-d.html.
Full text
2
Lee, Peter. "Hybrid-logarithmic arithmetic and applications." Thesis, University of Kent, 2011. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.633518.
Full textAbstract:
This thesis is a contribution to the existing body of research on logarithmic arithmetic and signal processing. The implementation of log2 arithmetic circuits using modem digital hardware has been an area of active research for over 40 years. In this time over 400 academic papers in journals and conferences have been published and more than 40 patent applications submitted. At the time of writing there are at least 6 different research groups around the world actively working on new algorithms for conversion to and from the logarithmic domain and using logarithmic arithmetic and logarithmic signal processing in a wide range of academic, industrial, consumer and scientific applications. This thesis is separated into two sections. The first section deals with algorithms for logarithmic and anti-logarithmic conversion. It includes an overview and comparison of existing conversion algorithms before presenting two new conversion architectures which are more computationally efficient and suitable for implementation in both ASIC and VLSI technologies. The second section presents material published by the author on two specific applications of logarithmic signal processing where a Hybrid-Logarithmic Number System (Hybrid-LNS or Hybrid-Log) approach has been used. The first is the analysis, design· and implementation of a Discrete Cosine Transform (and its inverse) architecture which has been optimised for use in image compression applications such as JPEG and MPEG. The second describes the TOTEM neural network processor before discussing its implementation in both full-custom IC and FPGA technologies. The concentration. on Hybrid-LNS solutions indicates that this thesis does not discuss in any significant detail the problem of performing addition and subtraction in the logarithnlic domain. There has been extensive research into this problem in recent years and it · is beyond the scope of this thesis. This work is intended to add to the continued debate about the advantages/disadvantages of Hybrid-LNS architectures over "pure" logarithmic or LNS processors.
3
Taïbi, Olivier. "Two arithmetic applications of Arthur's work." Palaiseau, Ecole polytechnique, 2014. https://tel.archives-ouvertes.fr/pastel-01066463/document.
Full textAbstract:
Nous proposons deux applications à l'arithmétique des travaux récents de James Arthur sur la classification endoscopique du spectre discret des groupes symplectiques et orthogonaux. La première consiste à ôter une hypothèse d'irréductibilité dans un résultat de Richard Taylor décrivant l'image des conjugaisons complexes par les représentations galoisiennes p-adiques associées aux représentations automorphes cuspidales algébriques régulières essentiellement autoduales pour le groupe GL_{2n+1} sur un corps totalement réel. Nous l'étendons également au cas de GL_{2n}, sous une hypothèse de parité du caractère multiplicatif. Nous utilisons un résultat de déformation p-adique. Plus précisément, nous montrons l'abondance de points correspondant à des représentations galoisiennes (quasi-)irréductibles sur les variétés de Hecke pour les groupes symplectiques et orthogonaux pairs. La classification d'Arthur est utilisée à la fois pour définir les représentations galoisiennes et pour transférer des représentations automorphes autoduales (pas nécessairement cuspidales) de groupes linéaires aux groupes symplectiques et orthogonaux. La deuxième application concerne le calcul explicite de dimensions d'espaces de formes automorphes ou modulaires. Notre contribution principale est un algorithme calculant les intégrales orbitales aux éléments de torsion des groupes classiques p-adiques non ramifiés, pour l'unité de l'algèbre de Hecke non ramifiée. Cela permet le calcul du côté géométrique de la formule des traces d'Arthur, et donc celui de la caractéristique d'Euler du spectre discret en niveau un. La classification d'Arthur permet l'analyse fine de cette caractéristique d'Euler, jusqu'à en déduire les dimensions des espaces de formes automorphes. De là il n'est pas difficile d'apporter une réponse à un problème plus classique: déterminer les dimensions des espaces de formes modulaires de Siegel à valeurs vectoriellesWe present two arithmetic applications of James Arthur's endoscopic classification of the discrete automorphic spectrum for symplectic and orthogonal groups. The first one consists in removing the irreducibility assumption in a theorem of Richard Taylor describing the image of complex conjugations by p-adic Galois representations associated with regular, algebraic, essentially self-dual, cuspidal automorphic representations of GL_{2n+1} over a totally real number field. We also extend it to the case of representations of GL_{2n} whose multiplicative character is ''odd''. We use a p-adic deformation argument, more precisely we prove that on the eigenvarieties for symplectic and even orthogonal groups, there are ''many'' points corresponding to (quasi-)irreducible Galois representations. Arthur's endoscopic classification is used to define these Galois representations, and also to transfer self-dual automorphic representations of the general linear group to these classical groups. The second application concerns the explicit computation of dimensions of spaces of automorphic or modular forms. Our main contribution is an algorithm computing orbital integrals at torsion elements of an unramified p-adic classical group, for the unit of the unramified Hecke algebra. It allows to compute the geometric side in Arthur's trace formula, and thus the Euler characteristic of the discrete spectrum in level one. Arthur's endoscopic classification allows to analyse precisely this Euler characteristic, and deduce the dimensions of spaces of level one automorphic forms. The dimensions of spaces of vector-valued Siegel modular forms, which constitute a more classical problem, are easily derived
4
Cheng, Lo Sing. "Efficient finite field arithmetic with cryptographic applications." Thesis, University of Ottawa (Canada), 2005. http://hdl.handle.net/10393/26871.
Full textAbstract:
Finite field multiplication is one of the most useful arithmetic operations and has applications in many areas such as signal processing, coding theory and cryptography. However, it is also one of the most time consuming operations in both software and hardware, which makes it pertinent to develop a fast and efficient implementation. We propose four improved FPGA multiplication implementations using the Karatsuba and Fast Fourier Transform algorithms over GF (2n). We also implement the hyperelliptic curve coprocessor and compare the results of our finite field arithmetics on the ring arithmetics.
Three of our implementations are based on the Karatsuba algorithm which has a running time of O (n1.585). Our final implementation is based on Fast Fourier Transform algorithm who's running time is O (nlog(n)). They are a significant increase from the classical schoolbook algorithm which has a running time of O (n2).
We then approximate the ring arithmetic's performance in our hyperelliptic curve coprocessor by applying our finite field implementations. We had improvements of up to 96 percent over the classical multiplier. We conclude that we have the most efficient ring arithmetic FPGA implementation with regards to area and speed.
5
Göbel, Benjamin [Verfasser], and Ulf [Akademischer Betreuer] Kühn. "Arithmetic Local Coordinates and Applications to Arithmetic Self-Intersection Numbers / Benjamin Göbel. Betreuer: Ulf Kühn." Hamburg : Staats- und Universitätsbibliothek Hamburg, 2015. http://d-nb.info/1075317495/34.
Full text
6
Göbel, Benjamin Verfasser], and Ulf [Akademischer Betreuer] [Kühn. "Arithmetic Local Coordinates and Applications to Arithmetic Self-Intersection Numbers / Benjamin Göbel. Betreuer: Ulf Kühn." Hamburg : Staats- und Universitätsbibliothek Hamburg, 2015. http://nbn-resolving.de/urn:nbn:de:gbv:18-74739.
Full text
7
Handley, W. G. "Some machine characterizations of classes close to #DELTA#0̲'IN." Thesis, University of Manchester, 1986. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.375068.
Full text
8
Dyer, A. K. "Applications of sieve methods in number theory." Thesis, Bucks New University, 1987. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.384646.
Full text
9
Viale, Matteo. "Applications of the proper forcing axiom to cardinal arithmetic." Paris 7, 2006. http://www.theses.fr/2006PA07A003.
Full text
10
Zhu, Dalin. "Residue number system arithmetic inspired applications in cellular downlink OFDMA." Thesis, Manhattan, Kan. : Kansas State University, 2009. http://hdl.handle.net/2097/2070.
Full text
11
Oudjida, Abdelkrim Kamel. "Binary Arithmetic for Finite-Word-Length Linear Controllers : MEMS Applications." Thesis, Besançon, 2014. http://www.theses.fr/2014BESA2001/document.
Full textAbstract:
Cette thèse traite le problème d'intégration hardware optimale de contrôleurs linéaires à taille de mot finie, dédiés aux applications MEMS. Le plus grand défi est d'assurer des performances de contrôle satisfaisantes avec un minimum de ressources logiques. Afin d'y parvenir, deux optimisations distinctes mais complémentaires peuvent être entreprises: en théorie de contrôle et en arithmétique binaire. Seule cette dernière est considérée dans ce travail.Comme cette arithmétique cible des applications MEMS, elle doit faire preuve de vitesse afin de prendre en charge la dynamique rapide des MEMS, à faible consommation de puissance pour un contrôle intégré, hautement re-configurabe pour un ajustement facile des performances de contrôle, et facilement prédictible pour fournir une idée précise sur les ressources logiques nécessaires avant l'implémentation même.L'exploration d'un certain nombre d'arithmétiques binaires a montré que l'arithmétique radix-2r est celle qui répond au mieux aux exigences précitées. Elle a été pleinement exploitée afin de concevoir des circuits de multiplication efficaces, qui sont au fait, le véritable moteur des systèmes linéaires.L'arithmétique radix-2r a été appliquée à l'intégration hardware de deux structures linéaires à taille de mot finie: un contrôleur PID variant dans le temps et à un contrôleur LQG invariant dans le temps,avec un filtre de Kalman. Le contrôleur PID a montré une nette supériorité sur ses homologues existants. Quant au contrôleur LQG, une réduction très importante des ressources logiques a été obtenue par rapport à sa forme initiale non optimiséeThis thesis addresses the problem of optimal hardware-realization of finite-word-length(FWL) linear controllers dedicated to MEMS applications. The biggest challenge is to ensuresatisfactory control performances with a minimal hardware. To come up, two distinct butcomplementary optimizations can be undertaken: in control theory and in binary arithmetic. Only thelatter is involved in this work.Because MEMS applications are targeted, the binary arithmetic must be fast enough to cope withthe rapid dynamic of MEMS; power-efficient for an embedded control; highly scalable for an easyadjustment of the control performances; and easily predictable to provide a precise idea on therequired logic resources before the implementation.The exploration of a number of binary arithmetics showed that radix-2r is the best candidate that fitsthe aforementioned requirements. It has been fully exploited to designing efficient multiplier cores,which are the real engine of the linear systems.The radix-2r arithmetic was applied to the hardware integration of two FWL structures: a linear timevariant PID controller and a linear time invariant LQG controller with a Kalman filter. Both controllersshowed a clear superiority over their existing counterparts, or in comparison to their initial forms
12
Lazda, Christopher David. "Rational homotopy theory in arithmetic geometry : applications to rational points." Thesis, Imperial College London, 2014. http://hdl.handle.net/10044/1/24707.
Full textAbstract:
In this thesis I study various incarnations of rational homotopy theory in the world of arithmetic geometry. In particular, I study unipotent crystalline fundamental groups in the relative setting, proving that for a smooth and proper family of geometrically connected varieties f:X->S in positive characteristic, the rigid fundamental groups of the fibres X_s glue together to give an affine group scheme in the category of overconvergent F-isocrystals on S. I then use this to define a global period map similar to the one used by Minhyong Kim to study rational points on curves over number fields. I also study rigid rational homotopy types, and show how to construct these for arbitrary varieties over a perfect field of positive characteristic. I prove that these agree with previous constructions in the (log-)smooth and proper case, and show that one can recover the usual rigid fundamental groups from these rational homotopy types. When the base field is finite, I show that the natural Frobenius structure on the rigid rational homotopy type is mixed, building on previous results in the log-smooth and proper case using a descent argument. Finally I turn to l-adic étale rational homotopy types, and show how to lift the Galois action on the geometric l-adic rational homotopy type from the homotopy category Ho(Q_l-dga) to get a Galois action on the dga representing the rational homotopy type. Together with a suitable lifted p-adic Hodge theory comparison theorem, this allows me to define a crystalline obstruction for the existence of integral points. I also study the continuity of the Galois action via a suitably constructed category of cosimplicial Q_l-algebras on a scheme.
13
Nibouche, O. "High performana computer arithmetic architectures for image and signal processing applications." Thesis, Queen's University Belfast, 2002. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.395217.
Full text
14
Koutsianas, Angelos. "Applications of S-unit equations to the arithmetic of elliptic curves." Thesis, University of Warwick, 2016. http://wrap.warwick.ac.uk/86760/.
Full textAbstract:
Let K be a number field and S a finite set of prime ideals of K. By a classical result of Shafarevich ([Sil86]) we know that there are finitely many isomorphism classes ƸK;S of elliptic curves de ned over K with good reduction outside S. Many people have developed methods of computing ƸK;S explicitly. At the end, all the methods ask for solutions of specific Diophantine equations in order to determine ƸK;S. In this thesis we develop a new algorithmic method of computing EK;S by solving S{unit equations. The method is implemented in the mathematical software Sage ([Dev16]) and examples are included in this thesis.
15
Zhao, Kaiyong. "A multiple-precision integer arithmetic library for GPUs and its applications." HKBU Institutional Repository, 2011. http://repository.hkbu.edu.hk/etd_ra/1237.
Full text
16
COLOMAR, MARIA FERNANDA PALLARES. "APPLICATIONS OF THE FIRST CONSISTENCY PROOF PRESENTED BY GENTZEN FOR PEANO ARITHMETIC." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2003. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=4126@1.
Full textAbstract:
COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIORNa antologia que M.E. Szabo realizara dos trabalhos de Gentzen e publicara em 1969 se transcrevem, em um apêndice, algumas passagens apresentadas por Bernays ao editor pertencentes a uma primeira prova de consistência para a Aritmética de Peano realizada por Gentzen que não tinha sido publicada até então. À diferença das outras provas de consistência realizadas por Gentzen e já conhecidas na década de trinta, esta prova não utiliza o procedimento de indução transfinita até e0. Ao contrário, baseia-se na definição de um processo de redução de seqüentes que se associa sistematicamente a todo seqüente derivável permitindo reconhecê-lo como verdadeiro. Nós reconstruímos essa prova realizando algumas variações e estudamos o modo pelo qual a técnica principal utilizada (a definição do processo de redução de seqüentes) pode ser vista em relação a resultados da lógica clássica de primeira ordem tais como provas de completude. A parte central da nossa dissertação é a realização de uma versão desta prova de consistência para um sistema formal para a Aritmética de Heyting.
In the antology of Gentzens works made by M.E.Szabo and published in 1969, we find out in an appendix, some passages presented by Bernays to the editor. These texts belong to a first proof of Peanos Arithmetic consistency that Gentzen did not publish. In a different way from the other proofs of consistency made by Gentzen and already known in the thirties, this proof does not use the procedure of transfinite induction up to e0. On the contrary, it is based on the definition of a reduction process for sequents that is systematically associated to every derivable sequent allowing us to recognize it as a true sequent. We reconstructed this proof making some variations and we studied how the main technique used (the definition of the reduction process) could be seen in relation with other results of first order logic like proofs of completness. The main part of our dissertation is another version of this consistency proof for a formal system for Heyting Arithmetic.
17
Vonk, Jan Bert. "The Atkin operator on spaces of overconvergent modular forms and arithmetic applications." Thesis, University of Oxford, 2015. http://ora.ox.ac.uk/objects/uuid:081e4e46-80c1-41e7-9154-3181ccb36313.
Full textAbstract:
We investigate the action of the Atkin operator on spaces of overconvergent p-adic modular forms. Our contributions are both computational and geometric. We present several algorithms to compute the spectrum of the Atkin operator, as well as its p-adic variation as a function of the weight. As an application, we explicitly construct Heegner-type points on elliptic curves. We then make a geometric study of the Atkin operator, and prove a potential semi-stability theorem for correspondences. We explicitly determine the stable models of various Hecke operators on quaternionic Shimura curves, and make a purely geometric study of canonical subgroups.
18
Reading, Alan G. "On counting problems in nonstandard models of Peano arithmetic with applications to groups." Thesis, University of Birmingham, 2014. http://etheses.bham.ac.uk//id/eprint/5421/.
Full textAbstract:
Coding devices in Peano arithmetic (PA) allow complicated finite objects such as groups to be encoded in a model \(M\) ╞ PA. We call such coded objects \(M\) -finite. This thesis concerns \(M\) -finite abelian groups, and counting problems for \(M\)-finite groups. We define a notion of cardinality for non-\(M\) -finite sets via the suprema and infima of appropriate \(M\) -finite sets, if these agree we call the set \(M\) -countable. We investigate properties of \(M\) -countable sets and give examples which demonstrate marked differences to measure theory. Many of the pathologies are related to the arithmetic of cuts and we show what can be recovered in special cases. We propose a notion of measure that mimics the Carathéodory definition. We show that an \(M\) -countable subgroup of any \(M\) -finite group has an \(M\) -countable transversal of appropriate cardinality. We look at \(M\) -finite abelian groups. After discussing consequences of the basis theorem we concentrate on the case of a single \(M\) -finite group \(C\)(\(p\)\(^k\)) and investigate its external structure as an infinite abelian group. We prove that certain externally divisible subgroups of \(C\)(\(p\)\(^k\)) have \(M\) -countable complements. We generalize this result to show that \(d\)\(G\), the divisible part of \(G\), has an \(M\) -countable complement for a general \(M\) -finite abelian \(G\).
19
Rivero, Salgado Óscar. "Arithmetic applications of the Euler systems of Beilinson-Flach elements and diagonal cycles." Doctoral thesis, Universitat Politècnica de Catalunya, 2021. http://hdl.handle.net/10803/671865.
Full textAbstract:
The main objective of this dissertation is the exploration of certain arithmetic applications of the Euler systems of Beilinson--Flach elements and diagonal cycles. Euler systems have been proved to be a very powerful tool for the study of Iwasawa theory and Selmer groups. Roughly speaking, they are collections of Galois cohomology classes satisfying certain compatibility relations, and are typically constructed using the étale cohomology of algebraic varieties. The genesis of the concept comes from Kolyvagin, who used them to fully prove the Birch and Swinnerton--Dyer conjecture in analytic rank one, and also from Rubin, who proposed a systematic framework to understand this cohomological tool. In the last years, many new constructions and results around these Euler systems have been obtained, and the aim of this thesis is to look at some of their arithmetic applications towards exceptional zeros, special value formulas, and Eisenstein congruences.
The first chapters deal with different kinds of exceptional zero phenomena. The main result we obtain is the proof of a conjecture of Darmon, Lauder and Rotger on special values of the Hida--Rankin p-adic L-function, which may be regarded both as the proof of a Gross--Stark type conjecture, or as the determination of the L-invariant corresponding to the adjoint representation of a weight one modular form. The proof recasts to Hida theory and to the ideas developed by Greenberg--Stevens, and makes use of the Galois deformation techniques introduced by Bellaïche and Dimitrov. We further discuss a similar exceptional zero phenomenon from the Euler system side, leading us to the construction of derived Beilinson--Flach classes. This allows us to give a more conceptual proof of the previous result, using the underlying properties of this Euler system. We also discuss other instances of this formalism, studying exceptional zeros at the level of cohomology classes both in the scenario of elliptic units and diagonal cycles.
The last part of the thesis aims to start a systematic study of the Artin formalism for Euler systems. This relies on ideas regarding factorizations of p-adic $L$-functions, and also recasts to the theory of Perrin-Riou maps and the study of canonical periods attached to weight two modular forms. We hope that these results could be extended to different settings concerning the other Euler systems studied in this memoir.Aquesta tesi estudia algunes aplicacions a problemes aritmètics dels anomenats sistemes d'Euler, que són classes de cohomologia galoisiana que varien de forma compatible sobre torres de cossos. Seguint una filosofia força general introduïda per Perrin-Riou, la imatge d'aquests sistemes d'Euler sota certs reguladors ens permet recuperar la funció L p-àdica associada a una representació de Galois. En aquesta tesi ens centrem fonamentalment en els sistemes de Beilinson-Flach i de cicles diagonals, tot i que també estudiem altres que comparteixen propietats amb els anteriors i que ens ajuden a una millor comprensió dels mateixos. Recordem que diferents treballs a la darrera dècada ja havíem aconseguit, mitjançant aquests sistemes d’Euler, provar nous casos de la conjectura equivariant de Birch i Swinnerton-Dyer, un dels grans reptes matemàtics dels nostres temps. Les aplicacions aritmètiques que discutim en aquesta monografia són diverses: zeros excepcionals, fórmules de valors especials, resultats de no anul·lació, connexions amb la teoria d’Iwasawa... Els primers capítols de la tesi estudien un fenomen de zeros excepcionals. Recordi’s que les funcions L p-àdiques interpolen, al llarg d’una certa regió, valors de la funció L complexa, llevat de certs factors d’Euler. L’anul·lació d’aquests factors acostuma donar lloc a fenòmens aritmètics interessants. Això, lluny de ser casual, admet una interpretació algebraica en termes de grups de Selmer. Per exemple, la anul·lació en s=0 de la funció de KubotaLeopoldt es relaciona amb el fet que hi hagi una p-unitat extra a la corresponent component del grup d’unitats, i el seu logaritme es relaciona amb la derivada de la funció L p-àdica. Aquesta és una de les conjectures més conegudes de Gross. Aquí comencem estudiant el cas de la representació adjunta d’una forma modular de pes 1. En aquest cas, provem una conjectura de Darmon, Lauder i Rotger que expressa el valor de la derivada de la funció L p-àdica associada en termes d’una combinació de logaritmes de unitats i p-unitats en el cos retallat per la representació. La prova fa servir la teoria de funcions L p-àdiques i funcions L p-àdiques millorades, així com les deformacions de Galois. A més, observem un fenomen que complementa aquest estudi. Les funcions L p-àdiques que hi surten són la imatge del sistema d’Euler de Beilinson-Flach pel morfisme de Perrin-Riou. Aquests zeros excepcionals també s’observen a nivell de sistemes d’Euler, i un pot introduir un concepte de classe derivada que ens permet recuperar l’invariant L que controla l’aritmètica de la representació galoisiana. No només això: amb aquesta noció de derivada podem donar una demostració alternativa del resultat anterior explotant la geometria d’aquests sistemes. Aquesta primera part de la tesi es complementa amb dos capítols on treballem el fenomen de zeros excepcionals tant per a unitats el·líptiques com per a cicles diagonals. Els últims capítols s’endinsen en l’estudi d’altres qüestions al voltant dels sistemes d’Euler, i es comença amb el desenvolupament d’un formalisme d’Artin a nivell de classes de cohomologia. El cas més bàsic passa per considerar una forma pròpia cuspidal de pes 2, de manera que sigui congruent a una sèrie d’Eisenstein. La classe de cohomologia associada a f descompon com la suma de dues components mòdul p. Nosaltres suggerim congruències relacionant cadascuna d’elles amb expressions que involucren unitats circulars. Això fa servir, per una banda, factoritzacions de funcions L p-àdiques i les lleis de reciprocitats; per l’altra, recuperarem alguns resultats de Fukaya-Kato desenvolupats durant la prova de les conjectures de Sharifi.
20
Карнаушенко, В. П., and А. В. Бородин. "Field Programmable Counter Arrays Integration with Field Programmable Gates Arrays." Thesis, NURE, MC&FPGA, 2019. https://mcfpga.nure.ua/conf/2019-mcfpga/10-35598-mcfpga-2019-004.
Full textAbstract:
Field Programmable Counter Arrays (FPCAs) have been recently introduced to close the gap between Field Programmable Gates Arrays (FPGA) and Application Specified Integrated Circuits (ASICs) for arithmetic dominated applications. FPCAs are reconfigurable lattices that can be embedded into FPGAs to efficiently compute the result of multi-operand additions.
21
O'Neill, Adam. "Stronger security notions for trapdoor functions and applications." Diss., Georgia Institute of Technology, 2010. http://hdl.handle.net/1853/37109.
Full textAbstract:
Trapdoor functions, introduced in the seminal paper of Diffie and Hellman, are a fundamental notion in modern cryptography. Informally, trapdoor functions are injective functions that are easy to evaluate but hard to invert unless given an additional input called the trapdoor. Specifically, the classical security notion considered for trapdoor functions is one-wayness, which asks that it be hard to invert (except with very small probability) a uniformly random point in the range without the trapdoor.
Motivated by the demands of emerging applications of cryptography as well as stronger security properties desired from higher-level cryptographic primitives constructed out of trapdoor functions, this thesis studies new strengthenings to the classical notion of one-way trapdoor functions and their applications. Our results are organized along two separate threads, wherein we introduce two new cryptographic primitives that strengthen the notion of one-wayness for trapdoor functions in different ways:
Deterministic Encryption: Our notion of deterministic (public-key) encryption addresses the weaknesses of using trapdoor functions directly for encryption articulated by Goldwasser and Micali, to the extent possible without randomizing the encryption function (whereas Goldwasser and Micali address them using randomized encryption). Specifically, deterministic encryption ensures no partial information is leaked about a high-entropy plaintext or even multiple correlated such plaintexts. Deterministic encryption has applications to fast search on encrypted data, securing legacy protocols, and ``hedging' randomized encryption against bad randomness.
We design a conceptually appealing semantic-security style definition of security for deterministic encryption as well as an easier-to-work-with but equivalent indistinguishability style definition. In the random oracle model of Bellare and Rogaway, we show a secure construction of deterministic encryption for an unbounded number of arbitrarily correlated high-entropy plaintexts based on any randomized encryption scheme, as well as length-preserving such construction based on RSA. In the standard model, we develop a general framework for constructing deterministic encryption schemes based on a new notion of ``robust' hardcore functions. We show a secure construction of deterministic for a single high-entropy plaintext based on exponentially-hard one-way trapdoor functions; single-message security is equivalent to security for an unbounded number of messages drawn from a block-source (where each subsequent message has high entropy conditioned on the previous). We also show a secure construction of deterministic encryption for a bounded number of arbitrarily correlated high-entropy plaintexts based on the notion of lossy trapdoor functions introduced by Peikert and Waters.
paragraph*{Adaptive Trapdoor Functions:} Our notion of adaptive trapdoor functions asks that one-wayness be preserved in the presence of an inversion oracle that can be queried on some range points. The main application we give is the construction of black-box chosen-ciphertext secure public-key encryption from weaker general assumptions. (``Black-box' means that the specific code implementing the trapdoor function is not used in the construction, which typically incurs a huge efficiency cost.) Namely, we show such a construction of chosen-ciphertext secure public-key encryption from adaptive trapdoor functions. We then show that adaptive trapdoor functions can be realized from the recently introduced notions of lossy trapdoor functions by Peikert and Waters and correlated-product secure trapdoor functions by Rosen and Segev. In fact, by extending a recent result of Vahlis, we show adaptivity is strictly weaker than the latter notions (in a black-box sense). As a consequence, adaptivity is the weakest security property of trapdoor functions known to imply black-box chosen-ciphertext security. Additionally, by slightly extending our framework and considering ``tag-based' adaptive trapdoor functions, we obtain exactly the chosen-ciphertext secure encryption schemes proposed in prior work, thereby unifying them, although the schemes we obtain via adaptive trapdoor functions are actually more efficient. Finally, we show that adaptive trapdoor functions can be realized from a (non-standard) computational assumption on RSA inversion, leading to a very efficient RSA-based chosen-ciphertext secure encryption scheme in the standard model.
22
Sano, Kaoru. "Growth rate of height functions associated with ample divisors and its applications." Kyoto University, 2019. http://hdl.handle.net/2433/242570.
Full text
23
Arikan, Ali Ferda. "Structural models for the pricing of corporate securities and financial synergies : applications with stochastic processes including arithmetic Brownian motion." Thesis, University of Bradford, 2010. http://hdl.handle.net/10454/5416.
Full textAbstract:
Mergers are the combining of two or more firms to create synergies. These synergies may come from various sources such as operational synergies come from economies of scale or financial synergies come from increased value of securities of the firm. There are vast amount of studies analysing operational synergies of mergers. This study analyses the financial ones. This way the dynamics of purely financial synergies can be revealed. Purely financial synergies can be transformed into financial instruments such as securitization. While analysing financial synergies the puzzle of distribution of financial synergies between claimholders is investigated. Previous literature on mergers showed that bondholders may gain more than existing shareholders of the merging firms. This may become rather controversial. A merger may be synergistic but it does not necessarily mean that shareholders' wealth will increase. Managers and/or shareholders are the parties making the merger decision. If managers are acting to the best interest of shareholders then they would try to increase shareholders' wealth. To solve this problem first the dynamics of mergers were analysed and then new strategies developed and demonstrated to transfer the financial synergies to the shareholders.
24
Arikan, Ali F. "Structural models for the pricing of corporate securities and financial synergies. Applications with stochastic processes including arithmetic Brownian motion." Thesis, University of Bradford, 2010. http://hdl.handle.net/10454/5416.
Full textAbstract:
Mergers are the combining of two or more firms to create synergies. These synergies
may come from various sources such as operational synergies come from
economies of scale or financial synergies come from increased value of securities
of the firm. There are vast amount of studies analysing operational synergies of
mergers. This study analyses the financial ones. This way the dynamics of purely
financial synergies can be revealed. Purely financial synergies can be transformed
into financial instruments such as securitization.
While analysing financial synergies the puzzle of distribution of financial synergies
between claimholders is investigated. Previous literature on mergers showed that
bondholders may gain more than existing shareholders of the merging firms. This
may become rather controversial. A merger may be synergistic but it does not
necessarily mean that shareholders¿ wealth will increase. Managers and/or shareholders
are the parties making the merger decision. If managers are acting to the
best interest of shareholders then they would try to increase shareholders¿ wealth.
To solve this problem first the dynamics of mergers were analysed and then new
strategies developed and demonstrated to transfer the financial synergies to the
shareholders.
25
Wong, Kenneth Koon-Ho. "Applications of finite field computation to cryptology : extension field arithmetic in public key systems and algebraic attacks on stream ciphers." Queensland University of Technology, 2008. http://eprints.qut.edu.au/17570/.
Full textAbstract:
In this digital age, cryptography is largely built in computer hardware or software as discrete structures. One of the most useful of these structures is finite fields. In this thesis, we explore a variety of applications of the theory and applications of arithmetic and computation in finite fields in both the areas of cryptography and cryptanalysis. First, multiplication algorithms in finite extensions of prime fields are explored. A new algebraic description of implementing the subquadratic Karatsuba algorithm and its variants for extension field multiplication are presented. The use of cy- clotomic fields and Gauss periods in constructing suitable extensions of virtually all sizes for efficient arithmetic are described. These multiplication techniques are then applied on some previously proposed public key cryptosystem based on exten- sion fields. These include the trace-based cryptosystems such as XTR, and torus- based cryptosystems such as CEILIDH. Improvements to the cost of arithmetic were achieved in some constructions due to the capability of thorough optimisation using the algebraic description. Then, for symmetric key systems, the focus is on algebraic analysis and attacks of stream ciphers. Different techniques of computing solutions to an arbitrary system of boolean equations were considered, and a method of analysing and simplifying the system using truth tables and graph theory have been investigated. Algebraic analyses were performed on stream ciphers based on linear feedback shift registers where clock control mechanisms are employed, a category of ciphers that have not been previously analysed before using this method. The results are successful algebraic attacks on various clock-controlled generators and cascade generators, and a full algebraic analyses for the eSTREAM cipher candidate Pomaranch. Some weaknesses in the filter functions used in Pomaranch have also been found. Finally, some non-traditional algebraic analysis of stream ciphers are presented. An algebraic analysis on the word-based RC4 family of stream ciphers is performed by constructing algebraic expressions for each of the operations involved, and it is concluded that each of these operations are significant in contributing to the overall security of the system. As far as we know, this is the first algebraic analysis on a stream cipher that is not based on linear feedback shift registers. The possibility of using binary extension fields and quotient rings for algebraic analysis of stream ciphers based on linear feedback shift registers are then investigated. Feasible algebraic attacks for generators with nonlinear filters are obtained and algebraic analyses for more complicated generators with multiple registers are presented. This new form of algebraic analysis may prove useful and thereby complement the traditional algebraic attacks. This thesis concludes with some future directions that can be taken and some open questions. Arithmetic and computation in finite fields will certainly be an important area for ongoing research as we are confronted with new developments in theory and exponentially growing computer power.
26
Wigren, Thomas. "The Cauchy-Schwarz inequality : Proofs and applications in various spaces." Thesis, Karlstads universitet, Avdelningen för matematik, 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:kau:diva-38196.
Full textAbstract:
We give some background information about the Cauchy-Schwarz inequality including its history. We then continue by providing a number of proofs for the inequality in its classical form using various proof techniques, including proofs without words. Next we build up the theory of inner product spaces from metric and normed spaces and show applications of the Cauchy-Schwarz inequality in each content, including the triangle inequality, Minkowski's inequality and Hölder's inequality. In the final part we present a few problems with solutions, some proved by the author and some by others.
27
Métairie, Jérémy. "Contribution aux opérateurs arithmétiques GF(2m) et leurs applications à la cryptographie sur courbes elliptiques." Thesis, Rennes 1, 2016. http://www.theses.fr/2016REN1S023/document.
Full textAbstract:
La cryptographie et la problématique de la sécurité informatique deviennent des sujets de plus en plus prépondérants dans un monde hyper connecté et souvent embarqué. La cryptographie est un domaine dont l'objectif principal est de ''protéger'' l'information, de la rendre inintelligible à ceux ou à celles à qui elle n'est pas destinée. La cryptographie repose sur des algorithmes solides qui s'appuient eux-mêmes sur des problèmes mathématiques réputés difficiles (logarithme discret, factorisation des grands nombres etc). Bien qu'il soit complexe, sur papier, d'attaquer ces systèmes de protection, l'implantation matérielle ou logicielle, si elle est négligée (non protégée contre les attaques physiques), peut apporter à des entités malveillantes des renseignements complémentaires (temps d’exécution, consommation d'énergie etc) : on parle de canaux cachés ou de canaux auxiliaires. Nous avons, dans cette thèse, étudié deux aspects. Le premier est l'apport de nouvelles idées algorithmiques pour le calcul dans les corps finis binaires GF(2^m) utilisés dans le cadre de la cryptographie sur courbes elliptiques. Nous avons proposé deux nouvelles représentations des éléments du corps : la base normale permutée et le Phi-RNS. Ces deux nouveautés algorithmiques ont fait l'objet d'implémentations matérielles en FPGA dans laquelle nous montrons que ces premières, sous certaines conditions, apportent un meilleur compromis temps-surface. Le deuxième aspect est la protection d'un crypto-processeur face à une attaque par canaux cachés (dite attaque par «templates»). Nous avons implémenté, en VHDL, un crypto-processeur complet et nous y avons exécuté, en parallèle, des algorithmes de «double-and-add» et «halve-and-add» afin d'accélérer le calcul de la multiplication scalaire et de rendre, de par ce même parallélisme, notre crypto-processeur moins vulnérable face à certaines attaques par canaux auxiliaires. Nous montrons que le parallélisme seul des calculs ne suffira pas et qu'il faudra marier le parallélisme à des méthodes plus conventionnelles pour assurer, à l'implémentation, une sécurité raisonnableCryptography and security market is growing up at an annual rate of 17 % according to some recent studies. Cryptography is known to be the science of secret. It is based on mathematical hard problems as integers factorization, the well-known discrete logarithm problem. Although those problems are trusted, software or hardware implementations of cryptographic algorithms can suffer from inherent weaknesses. Execution time, power consumption (...) can differ depending on secret informations such as the secret key. Because of that, some malicious attacks could be used to exploit these weak points and therefore can be used to break the whole crypto-system. In this thesis, we are interested in protecting our physical device from the so called side channel attacks as well as interested in proposing new GF(2^m) multiplication algorithms used over elliptic curves cryptography. As a protection, we first thought that parallel scalar multiplication (using halve-and-add and double-and-add algorithms both executed at the same time) would be a great countermeasure against template attacks. We showed that it was not the case and that parallelism could not be used as protection by itself : it had to be combined with more conventional countermeasures. We also proposed two new GF(2^m) representations we respectively named permuted normal basis (PNB) and Phi-RNS. Those two representations, under some requirements, can offer a great time-area trade-off on FPGAs
28
Silva, Salatiel Dias da. "Estudo do binômio de Newton." Universidade Federal da Paraíba, 2013. http://tede.biblioteca.ufpb.br:8080/handle/tede/7526.
Full textAbstract:
Submitted by Viviane Lima da Cunha (viviane@biblioteca.ufpb.br) on 2015-10-16T15:00:20Z
No. of bitstreams: 1
arquivototal.pdf: 971519 bytes, checksum: 75c5acddc58c0f9e43eb4d646a3fa8fd (MD5)Approved for entry into archive by Maria Suzana Diniz (msuzanad@hotmail.com) on 2015-10-16T22:38:36Z (GMT) No. of bitstreams: 1 arquivototal.pdf: 971519 bytes, checksum: 75c5acddc58c0f9e43eb4d646a3fa8fd (MD5)
Made available in DSpace on 2015-10-16T22:38:36Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 971519 bytes, checksum: 75c5acddc58c0f9e43eb4d646a3fa8fd (MD5) Previous issue date: 2013-08-14
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES
This work deals with the study of the binomial developments started in the late years of Elementary School, when we deal with notable products, which is complemented in the second year of High School, from the study of Newton's Binomial. We will make a detailed study of the same, through a historical overview about the subject, properties of arithmetic triangle (Pascal's triangle / Tartaglia's), reaching the binomial theorem and, nally, some applications of these results in solving various problems, in the multinomial expanding and in the binomial series.
Este trabalho vem mostrar o estudo dos desenvolvimentos binomiais iniciado na 7a série (8o ano) do Ensino Fundamental, quando tratamos de produtos notáveis, que é complementado na segunda série do ensino médio, a partir do estudo do Binômio de Newton. Faremos um estudo detalhado do mesmo, passando por um apanhado histórico sobre o assunto, propriedades do triângulo aritmético (triângulo de Pascal/Tartaglia), chegando ao Teorema binomial e, por m, a algumas aplicações destes na resolução de problemas diversos, expansão multinomial e nas séries binomiais.
29
[Verfasser], Surapong Pongyupinpanich, Manfred [Akademischer Betreuer] Glesner, Michael [Akademischer Betreuer] Hübner, Andreas [Akademischer Betreuer] Binder, Harald [Akademischer Betreuer] Klingbeil, and Hans [Akademischer Betreuer] Eveking. "Optimal Design of Fixed-Point and Floating-Point Arithmetic Units for Scientific Applications / Surapong Pongyupinpanich. Betreuer: Manfred Glesner ; Michael Hübner ; Andreas Binder ; Harald Klingbeil ; Hans Eveking." Darmstadt : Universitäts- und Landesbibliothek Darmstadt, 2012. http://d-nb.info/1106117581/34.
Full text
30
Chakhari, Aymen. "Évaluation analytique de la précision des systèmes en virgule fixe pour des applications de communication numérique." Thesis, Rennes 1, 2014. http://www.theses.fr/2014REN1S059/document.
Full textAbstract:
Par rapport à l'arithmétique virgule flottante, l'arithmétique virgule fixe se révèle plus avantageuse en termes de contraintes de coût et de consommation, cependant la conversion en arithmétique virgule fixe d'un algorithme spécifié initialement en virgule flottante se révèle être une tâche fastidieuse. Au sein de ce processus de conversion, l'une des étapes majeures concerne l'évaluation de la précision de la spécification en virgule fixe. En effet, le changement du format des données de l'application s'effectue en éliminant des bits ce qui conduit à la génération de bruits de quantification qui se propagent au sein du système et dégradent la précision des calculs en sortie de l'application. Par conséquent, cette perte de précision de calcul doit être maîtrisée et évaluée afin de garantir l'intégrité de l'algorithme et répondre aux spécifications initiales de l'application. Le travail mené dans le cadre de cette thèse se concentre sur des approches basées sur l'évaluation de la précision à travers des modèles analytiques (par opposition à l'approche par simulations). Ce travail traite en premier lieu de la recherche de modèles analytiques pour évaluer la précision des opérateurs non lisses de décision ainsi que la cascade d'opérateurs de décision. Par conséquent, la caractérisation de la propagation des erreurs de quantification dans la cascade d'opérateurs de décision est le fondement des modèles analytiques proposés. Ces modèles sont appliqués à la problématique de l'évaluation de la précision de l'algorithme de décodage sphérique SSFE (Selective Spanning with Fast Enumeration) utilisé pour les systèmes de transmission de type MIMO (Multiple-Input Multiple-Output). Dans une seconde étape, l'évaluation de la précision des structures itératives d'opérateurs de décision a fait l'objet d'intérêt. Une caractérisation des erreurs de quantification engendrées par l'utilisation de l'arithmétique en virgule fixe est menée afin de proposer des modèles analytiques basés sur l'estimation d'une borne supérieure de la probabilité d'erreur de décision ce qui permet de réduire les temps d'évaluation. Ces modèles sont ensuite appliqués à la problématique de l'évaluation de la spécification virgule fixe de l'égaliseur à retour de décision DFE (Decision Feedback Equalizer). Le second aspect du travail concerne l'optimisation des largeurs de données en virgule fixe. Ce processus d'optimisation est basé sur la minimisation de la probabilité d'erreur de décision dans le cadre d'une implémentation sur un FPGA (Field-Programmable Gate Array) de l'algorithme DFE complexe sous contrainte d'une précision donnée. Par conséquent, pour chaque spécification en virgule fixe, la précision est évaluée à travers les modèles analytiques proposés. L'estimation de la consommation des ressources et de la puissance sur le FPGA est ensuite obtenue à l'aide des outils de Xilinx pour faire un choix adéquat des largeurs des données en visant à un compromis précision/coût. La dernière phase de ce travail traite de la modélisation en virgule fixe des algorithmes de décodage itératif reposant sur les concepts de turbo-décodage et de décodage LDPC (Low-Density Parity-Check). L'approche proposée prend en compte la structure spécifique de ces algorithmes ce qui implique que les quantités calculées au sein du décodeur (ainsi que les opérations) soient quantifiées suivant une approche itérative. De plus, la représentation en virgule fixe utilisée (reposant sur le couple dynamique et le nombre de bits total) diffère de la représentation classique qui, elle, utilise le nombre de bits accordé à la partie entière et la partie fractionnaire. Avec une telle représentation, le choix de la dynamique engendre davantage de flexibilité puisque la dynamique n'est plus limitée uniquement à une puissance de deux. Enfin, la réduction de la taille des mémoires par des techniques de saturation et de troncature est proposée de manière à cibler des architectures à faible-complexitéTraditionally, evaluation of accuracy is performed through two different approaches. The first approach is to perform simulations fixed-point implementation in order to assess its performance. These approaches based on simulation require large computing capacities and lead to prohibitive time evaluation. To avoid this problem, the work done in this thesis focuses on approaches based on the accuracy evaluation through analytical models. These models describe the behavior of the system through analytical expressions that evaluate a defined metric of precision. Several analytical models have been proposed to evaluate the fixed point accuracy of Linear Time Invariant systems (LTI) and of non-LTI non-recursive and recursive linear systems. The objective of this thesis is to propose analytical models to evaluate the accuracy of digital communications systems and algorithms of digital signal processing made up of non-smooth and non-linear operators in terms of noise. In a first step, analytical models for evaluation of the accuracy of decision operators and their iterations and cascades are provided. In a second step, an optimization of the data length is given for fixed-point hardware implementation of the Decision Feedback Equalizer DFE based on analytical models proposed and for iterative decoding algorithms such as turbo decoding and LDPC decoding-(Low-Density Parity-Check) in a particular quantization law. The first aspect of this work concerns the proposition analytical models for evaluating the accuracy of the non-smooth decision operators and the cascading of decision operators. So, the characterization of the quantization errors propagation in the cascade of decision operators is the basis of the proposed analytical models. These models are applied in a second step to evaluate the accuracy of the spherical decoding algorithmSSFE (Selective Spanning with Fast Enumeration) used for transmission MIMO systems (Multiple-Input Multiple -Output). In a second step, the accuracy evaluation of the iterative structures of decision operators has been the interesting subject. Characterization of quantization errors caused by the use of fixed-point arithmetic is introduced to result in analytical models to evaluate the accuracy of application of digital signal processing including iterative structures of decision. A second approach, based on the estimation of an upper bound of the decision error probability in the convergence mode, is proposed for evaluating the accuracy of these applications in order to reduce the evaluation time. These models are applied to the problem of evaluating the fixed-point specification of the Decision Feedback Equalizer DFE. The estimation of resources and power consumption on the FPGA is then obtained using the Xilinx tools to make a proper choice of the data widths aiming to a compromise accuracy/cost. The last step of our work concerns the fixed-point modeling of iterative decoding algorithms. A model of the turbo decoding algorithm and the LDPC decoding is then given. This approach integrates the particular structure of these algorithms which implies that the calculated quantities in the decoder and the operations are quantified following an iterative approach. Furthermore, the used fixed-point representation is different from the conventional representation using the number of bits accorded to the integer part and the fractional part. The proposed approach is based on the dynamic and the total number of bits. Besides, the dynamic choice causes more flexibility for fixed-point models since it is not limited to only a power of two
31
Baktir, Selcuk. "Efficient algorithms for finite fields, with applications in elliptic curve cryptography." Link to electronic thesis, 2003. http://www.wpi.edu/Pubs/ETD/Available/etd-0501103-132249.
Full textAbstract:
Thesis (M.S.)--Worcester Polytechnic Institute.Keywords: multiplication; OTF; optimal extension fields; finite fields; optimal tower fields; cryptography; OEF; inversion; finite field arithmetic; elliptic curve cryptography. Includes bibliographical references (p. 50-52).
32
Joldes, Mioara Maria. "Approximations polynomiales rigoureuses et applications." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2011. http://tel.archives-ouvertes.fr/tel-00657843.
Full textAbstract:
Quand on veut évaluer ou manipuler une fonction mathématique f, il est fréquent de la remplacer par une approximation polynomiale p. On le fait, par exemple, pour implanter des fonctions élémentaires en machine, pour la quadrature ou la résolution d'équations différentielles ordinaires (ODE). De nombreuses méthodes numériques existent pour l'ensemble de ces questions et nous nous proposons de les aborder dans le cadre du calcul rigoureux, au sein duquel on exige des garanties sur la précision des résultats, tant pour l'erreur de méthode que l'erreur d'arrondi.Une approximation polynomiale rigoureuse (RPA) pour une fonction f définie sur un intervalle [a,b], est un couple (P, Delta) formé par un polynôme P et un intervalle Delta, tel que f(x)-P(x) appartienne à Delta pour tout x dans [a,b].Dans ce travail, nous analysons et introduisons plusieurs procédés de calcul de RPAs dans le cas de fonctions univariées. Nous analysons et raffinons une approche existante à base de développements de Taylor.Puis nous les remplaçons par des approximants plus fins, tels que les polynômes minimax, les séries tronquées de Chebyshev ou les interpolants de Chebyshev.Nous présentons aussi plusieurs applications: une relative à l'implantation de fonctions standard dans une bibliothèque mathématique (libm), une portant sur le calcul de développements tronqués en séries de Chebyshev de solutions d'ODE linéaires à coefficients polynômiaux et, enfin, un processus automatique d'évaluation de fonction à précision garantie sur une puce reconfigurable.
33
Brunie, Nicolas. "Contribution à l'arithmétique des ordinateurs et applications aux systèmes embarqués." Thesis, Lyon, École normale supérieure, 2014. http://www.theses.fr/2014ENSL0894/document.
Full textAbstract:
Au cours des dernières décennies les systèmes embarqués ont dû faire face à des demandes applicatives de plus en plus variées et de plus en plus contraintes. Ce constat s'est traduit pour l’arithmétique par le besoin de toujours plus de performances et d'efficacité énergétique. Ce travail se propose d'étudier des solutions allant du matériel au logiciel, ainsi que les diverses interactions qui existent entre ces domaines, pour améliorer le support arithmétique dans les systèmes embarqués. Certains résultats ont été intégrés au processeur MPPA développé par Kalray. La première partie est consacrée au support de l'arithmétique virgule flottante dans le MPPA. Elle commence par la mise au point d'une unité flottante matérielle basée sur l'opérateur classique FMA (fused multiply-Add). Les améliorations proposées, implémentées et évaluées incluent un FMA à précision mixte, l'addition à 3 opérandes et le produit scalaire 2D, à chaque fois avec un seul arrondi et le support des sous-Normaux. Cette partie se poursuit par l'étude de l'implémentation des autres primitives flottantes normalisées : division et racine carrée. L'unité flottante matérielle précédente est réutilisée et modifiée pour optimiser ces primitives à moindre coût. Cette première partie s’ouvre sur le développement d'un générateur de code destiné à l'implémentation de bibliothèques mathématiques optimisées pour différents contextes (architecture, précision, latence, débit). La seconde partie consiste en la présentation d'une nouvelle architecture de coprocesseur reconfigurable. Cet opérateur matériel peut être dynamiquement modifié pour s'adapter à la volée à des besoins applicatifs variés. Il vise à fournir des performances se rapprochant d'une implémentation matérielle dédiée sans renier la flexibilité inhérente au logiciel. Il a été spécifiquement pensé pour être intégré avec un cœur embarqué faible consommation du MPPA. Cette partie s'attache aussi à décrire le développement d'un environnement logiciel pour cibler ce coprocesseur ainsi qu'explorer divers choix architecturaux envisagés. La dernière partie étudie un problème plus large : l'utilisation efficace de ressources arithmétiques parallèles. Elle présente une amélioration des architectures régulières Single Instruction Multiple Data tels qu’on les trouve dans les accélérateurs graphiques (GPU) pour l'exécution de graphes de flot de contrôle divergentsIn the last decades embedded systems have been challenged with more and more application variety, each time more constrained. This implies an ever growing need for performances and energy efficiency in arithmetic units. This work studies solutions ranging from hardware to software to improve arithmetic support in embedded systems. Some of these solutions were integrated in Kalray's MPPA processor. The first part of this work focuses on floating-Point arithmetic support in the MPPA. It starts with the design of a floating-Point unit (FPU) based on the classical FMA (Fused Multiply-Add) operator. The improvements we suggest, implement and evaluate include a mixed precision FMA, a 3-Operand add and a 2D scalar product, each time with a single rounding and support for subnormal numbers. It then considers the implementation of division and square root. The FPU is reused and modified to optimize the software implementations of those primitives at a lower cost. Finally, this first part opens up on the development of a code generator designed for the implementation of highly optimized mathematical libraries in different contexts (architecture, accuracy, latency, throughput). The second part studies a reconfigurable coprocessor, a hardware operator that could be dynamically modified to adapt on the fly to various applicative needs. It intends to provide performance close to ASIC implementation, with some of the flexibility of software. One of the addressed challenges is the integration of such a reconfigurable coprocessor into the low power embedded cluster of the MPPA. Another is the development of a software framework targeting the coprocessor and allowing design space exploration. The last part of this work leaves micro-Architecture considerations to study the efficient use of parallel arithmetic resources. It presents an improvement of regular architectures (Single Instruction Multiple Data), like those found in graphic processing units (GPU), for the execution of divergent control flow graphs
34
Filip, Silviu-Ioan. "Robust tools for weighted Chebyshev approximation and applications to digital filter design." Thesis, Lyon, 2016. http://www.theses.fr/2016LYSEN063/document.
Full textAbstract:
De nombreuses méthodes de traitement du signal reposent sur des résultats puissants d'approximation numérique. Un exemple significatif en est l'utilisation de l'approximation de type Chebyshev pour l'élaboration de filtres numériques.En pratique, le caractère fini des formats numériques utilisés en machine entraîne des difficultés supplémentaires pour la conception de filtres numériques (le traitement audio et le traitement d'images sont deux domaines qui utilisent beaucoup le filtrage). La majorité des outils actuels de conception de filtres ne sont pas optimisés et ne certifient pas non plus la correction de leurs résultats. Notre travail se veut un premier pas vers un changement de cette situation.La première partie de la thèse traite de l'étude et du développement de méthodes relevant de la famille Remez/Parks-McClellan pour la résolution de problèmes d'approximation polynomiale de type Chebyshev, en utilisant l'arithmétique virgule-flottante.Ces approches sont très robustes, tant du point de vue du passage à l'échelle que de la qualité numérique, pour l'élaboration de filtres à réponse impulsionnelle finie (RIF).Cela dit, dans le cas des systèmes embarqués par exemple, le format des coefficients du filtre qu'on utilise en pratique est beaucoup plus petit que les formats virgule flottante standard et d'autres approches deviennent nécessaires.Nous proposons une méthode (quasi-)optimale pour traîter ce cas. Elle s'appuie sur l'algorithme LLL et permet de traiter des problèmes de taille bien supérieure à ceux que peuvent traiter les approches exactes. Le résultat est ensuite utilisé dans une couche logicielle qui permet la synthèse de filtres RIF pour des circuits de type FPGA.Les résultats que nous obtenons en sortie sont efficaces en termes de consommation d'énergie et précis. Nous terminons en présentant une étude en cours sur les algorithmes de type Remez pour l'approximation rationnelle. Ce type d'approches peut être utilisé pour construire des filtres à réponse impulsionnelle infinie (RII) par exemple. Nous examinons les difficultés qui limitent leur utilisation en pratiqueThe field of signal processing methods and applications frequentlyrelies on powerful results from numerical approximation. One suchexample, at the core of this thesis, is the use of Chebyshev approximationmethods for designing digital filters.In practice, the finite nature of numerical representations adds an extralayer of difficulty to the design problems we wish to address using digitalfilters (audio and image processing being two domains which rely heavilyon filtering operations). Most of the current mainstream tools for thisjob are neither optimized, nor do they provide certificates of correctness.We wish to change this, with some of the groundwork being laid by thepresent work.The first part of the thesis deals with the study and development ofRemez/Parks-McClellan-type methods for solving weighted polynomialapproximation problems in floating-point arithmetic. They are veryscalable and numerically accurate in addressing finite impulse response(FIR) design problems. However, in embedded and power hungry settings,the format of the filter coefficients uses a small number of bits andother methods are needed. We propose a (quasi-)optimal approach basedon the LLL algorithm which is more tractable than exact approaches.We then proceed to integrate these aforementioned tools in a softwarestack for FIR filter synthesis on FPGA targets. The results obtainedare both resource consumption efficient and possess guaranteed accuracyproperties. In the end, we present an ongoing study on Remez-type algorithmsfor rational approximation problems (which can be used for infinite impulseresponse (IIR) filter design) and the difficulties hindering their robustness
35
Thomé, Emmanuel. "Théorie algorithmique des nombres et applications à la cryptanalyse de primitives cryptographiques." Habilitation à diriger des recherches, Université de Lorraine, 2012. http://tel.archives-ouvertes.fr/tel-00765982.
Full textAbstract:
Le problème de la factorisation et celui du logarithme discret sont deux fondements essentiels de nombreux algorithmes de la cryptographie à clé publique. Dans le champ des algorithmes pour attaquer ces problèmes éminemment ardus, le crible algébrique et ses algorithmes cousins occupent une place de première importance. La première partie de ce mémoire est consacrée à la présentation de la " famille " du crible algébrique, et à plusieurs de mes contributions dans ce domaine. D'autres travaux sont abordés dans la partie suivante, notamment en lien avec le problème du logarithme discret sur les jacobiennes de courbes, et à ma contribution à de nouveaux algorithmes pour ce problème dans certains cas particuliers. La partie 3 du mémoire aborde mes travaux sur le thème de l'algèbre linéaire creuse sur les corps finis, motivés par le contexte d'application des algorithmes précédemment cités. La partie 4, enfin, traite de mes travaux dans le domaine de l'arithmétique, notamment concernant l'arithmétique des polynômes sur GF(2). La proximité des travaux apparaissant dans ces parties 3 et 4 avec des problématiques d'implantation indique le souci permanent, dans mes travaux, de ne pas laisser de côté cet aspect.
36
Nehmeh, Riham. "Quality Evaluation in Fixed-point Systems with Selective Simulation." Thesis, Rennes, INSA, 2017. http://www.theses.fr/2017ISAR0020/document.
Full textAbstract:
Le temps de mise sur le marché et les coûts d’implantation sont les deux critères principaux à prendre en compte dans l'automatisation du processus de conception de systèmes numériques. Les applications de traitement du signal utilisent majoritairement l'arithmétique virgule fixe en raison de leur coût d'implantation plus faible. Ainsi, une conversion en virgule fixe est nécessaire. Cette conversion est composée de deux parties correspondant à la détermination du nombre de bits pour la partie entière et pour la partie fractionnaire. Le raffinement d'un système en virgule fixe nécessite d'optimiser la largeur des données en vue de minimiser le coût d'implantation tout en évitant les débordements et un bruit de quantification excessif. Les applications dans les domaines du traitement d'image et du signal sont tolérantes aux erreurs si leur probabilité ou leur amplitude est suffisamment faible. De nombreux travaux de recherche se concentrent sur l'optimisation de la largeur de la partie fractionnaire sous contrainte de précision. La réduction du nombre de bits pour la partie fractionnaire conduit à une erreur d'amplitude faible par rapport à celle du signal. La théorie de la perturbation peut être utilisée pour propager ces erreurs à l'intérieur des systèmes à l'exception du cas des opérations un- smooth, comme les opérations de décision, pour lesquelles une erreur faible en entrée peut conduire à une erreur importante en sortie. De même, l'optimisation de la largeur de la partie entière peut réduire significativement le coût lorsque l'application est tolérante à une faible probabilité de débordement. Les débordements conduisent à une erreur d'amplitude élevée et leur occurrence doit donc être limitée. Pour l'optimisation des largeurs des données, le défi est d'évaluer efficacement l'effet des erreurs de débordement et de décision sur la métrique de qualité associée à l'application. L'amplitude élevée de l'erreur nécessite l'utilisation d'approches basées sur la simulation pour évaluer leurs effets sur la qualité. Dans cette thèse, nous visons à accélérer le processus d'évaluation de la métrique de qualité. Nous proposons un nouveau environnement logiciel utilisant des simulations sélectives pour accélérer la simulation des effets des débordements et des erreurs de décision. Cette approche peut être appliquée à toutes les applications de traitement du signal développées en langage C. Par rapport aux approches classiques basées sur la simulation en virgule fixe, où tous les échantillons d'entrée sont traités, l'approche proposée simule l'application uniquement en cas d'erreur. En effet, les dépassements et les erreurs de décision doivent être des événements rares pour maintenir la fonctionnalité du système. Par conséquent, la simulation sélective permet de réduire considérablement le temps requis pour évaluer les métriques de qualité des applications. De plus, nous avons travaillé sur l'optimisation de la largeur de la partie entière, qui peut diminuer considérablement le coût d'implantation lorsqu'une légère dégradation de la qualité de l'application est acceptable. Nous exploitons l'environnement logiciel proposé auparavant à travers un nouvel algorithme d'optimisation de la largeur des données. La combinaison de cet algorithme et de la technique de simulation sélective permet de réduire considérablement le temps d'optimisationTime-to-market and implementation cost are high-priority considerations in the automation of digital hardware design. Nowadays, digital signal processing applications use fixed-point architectures due to their advantages in terms of implementation cost. Thus, floating-point to fixed-point conversion is mandatory. The conversion process consists of two parts corresponding to the determination of the integer part word-length and the fractional part world-length. The refinement of fixed-point systems requires optimizing data word -length to prevent overflows and excessive quantization noises while minimizing implementation cost. Applications in image and signal processing domains are tolerant to errors if their probability or their amplitude is small enough. Numerous research works focus on optimizing the fractional part word-length under accuracy constraint. Reducing the number of bits for the fractional part word- length leads to a small error compared to the signal amplitude. Perturbation theory can be used to propagate these errors inside the systems except for unsmooth operations, like decision operations, for which a small error at the input can leads to a high error at the output. Likewise, optimizing the integer part word-length can significantly reduce the cost when the application is tolerant to a low probability of overflow. Overflows lead to errors with high amplitude and thus their occurrence must be limited. For the word-length optimization, the challenge is to evaluate efficiently the effect of overflow and unsmooth errors on the application quality metric. The high amplitude of the error requires using simulation based-approach to evaluate their effects on the quality. In this thesis, we aim at accelerating the process of quality metric evaluation. We propose a new framework using selective simulations to accelerate the simulation of overflow and un- smooth error effects. This approach can be applied on any C based digital signal processing applications. Compared to complete fixed -point simulation based approaches, where all the input samples are processed, the proposed approach simulates the application only when an error occurs. Indeed, overflows and unsmooth errors must be rare events to maintain the system functionality. Consequently, selective simulation allows reducing significantly the time required to evaluate the application quality metric. 1 Moreover, we focus on optimizing the integer part, which can significantly decrease the implementation cost when a slight degradation of the application quality is acceptable. Indeed, many applications are tolerant to overflows if the probability of overflow occurrence is low enough. Thus, we exploit the proposed framework in a new integer word-length optimization algorithm. The combination of the optimization algorithm and the selective simulation technique allows decreasing significantly the optimization time
37
Robert, Jean-Marc. "Contrer l'attaque Simple Power Analysis efficacement dans les applications de la cryptographie asymétrique, algorithmes et implantations." Thesis, Perpignan, 2015. http://www.theses.fr/2015PERP0039/document.
Full textAbstract:
Avec le développement des communications et de l'Internet, l'échange des informations cryptées a explosé. Cette évolution a été possible par le développement des protocoles de la cryptographie asymétrique qui font appel à des opérations arithmétiques telles que l'exponentiation modulaire sur des grands entiers ou la multiplication scalaire de point de courbe elliptique. Ces calculs sont réalisés par des plates-formes diverses, depuis la carte à puce jusqu'aux serveurs les plus puissants. Ces plates-formes font l'objet d'attaques qui exploitent les informations recueillies par un canal auxiliaire, tels que le courant instantané consommé ou le rayonnement électromagnétique émis par la plate-forme en fonctionnement.Dans la thèse, nous améliorons les performances des opérations résistantes à l'attaque Simple Power Analysis. Sur l'exponentiation modulaire, nous proposons d'améliorer les performances par l'utilisation de multiplications modulaires multiples avec une opérande commune optimisées. Nous avons proposé trois améliorations sur la multiplication scalaire de point de courbe elliptique : sur corps binaire, nous employons des améliorations sur les opérations combinées AB,AC et AB+CD sur les approches Double-and-add, Halve-and-add et Double/halve-and-add et l'échelle binaire de Montgomery ; sur corps binaire, nous proposons de paralléliser l'échelle binaire de Montgomery ; nous réalisons l'implantation d'une approche parallèle de l'approche Right-to-left Double-and-add sur corps premier et binaire, Halve-and-add et Double/halve-and-add sur corps binaireThe development of online communications and the Internet have made encrypted data exchange fast growing. This has been possible with the development of asymmetric cryptographic protocols, which make use of arithmetic computations such as modular exponentiation of large integer or elliptic curve scalar multiplication. These computations are performed by various platforms, including smart-cards as well as large and powerful servers. The platforms are subject to attacks taking advantage of information leaked through side channels, such as instantaneous power consumption or electromagnetic radiations.In this thesis, we improve the performance of cryptographic computations resistant to Simple Power Analysis. On modular exponentiation, we propose to use multiple multiplications sharing a common operand to achieve this goal. On elliptic curve scalar multiplication, we suggest three different improvements : over binary fields, we make use of improved combined operation AB,AC and AB+CD applied to Double-and-add, Halve-and-add and Double/halve-and-add approaches, and to the Montgomery ladder ; over binary field, we propose a parallel Montgomery ladder ; we make an implementation of a parallel approach based on the Right-to-left Double-and-add algorithm over binary and prime fields, and extend this implementation to the Halve-and-add and Double/halve-and-add over binary fields
38
Dia, Roxana. "Towards Environment Perception using Integer Arithmetic for Embedded Application." Thesis, Université Grenoble Alpes, 2020. http://www.theses.fr/2020GRALM038.
Full textAbstract:
Le principal inconvénient de l'utilisation de représentations basées sur la grille pour SLAM et pour la localisation globale est la complexité de calcul exponentielle requise en termes de taille de grille (de la carte et des cartes de pose). La taille de grille requise pour modéliser l'environnement entourant un robot ou un véhicule peut être de l'ordre de milliers de millions de cellules. Par exemple, un espace 2D de forme carrée de taille 100 m × 100 m, avec une taille de cellule de 10 cm est modélisé avec une grille de 1 million de cellules. Si nous incluons une hauteur de 2 m pour représenter la troisième dimension, 20 millions de cellules sont nécessaires. Par conséquent, les approches SLAM classiques basées sur une grille et de localisation globale nécessitent une unité de calcul parallèle afin de répondre à la latence imposée par les normes de sécurité. Un tel calcul est généralement effectué sur des postes de travail intégrant des unités de traitement graphique (GPU) et / ou des processeurs haut de gamme. Cependant, les véhicules autonomes ne peuvent pas gérer de telles plateformes pour des raisons de coût et de problèmes de certification. De plus, ces plates-formes nécessitent une consommation d'énergie élevée qui ne peut pas correspondre à la source d'énergie limitée disponible dans certains robots. Les plates-formes matérielles intégrées sont couramment utilisées comme solution alternative dans les applications automobiles. Ces plateformes répondent aux contraintes de faible coût, de faible puissance et de petit espace. De plus, certains d'entre eux sont certifiés automobiles1, suivant la norme ISO26262. Cependant, la plupart d'entre eux ne sont pas équipés d'une unité à virgule flottante, ce qui limite les performances de calcul.L'équipe du projet sigma-fusion du laboratoire LIALP du CEA-Leti a développé une méthode de perception basée sur des nombres entiers adaptée aux appareils embarqués. Cette méthode permet de construire une grille d'occupation via la fusion bayésienne en utilisant uniquement l'arithmétique entière, d'où son "embarquabilité" sur des plateformes informatiques embarquées, sans unité à virgule flottante. Ceci constitue la contribution majeure de la thèse de doctorat de Tiana Rakotovao [Rakotovao Andriamahefa 2017].L'objectif de la présente thèse est d'étendre le cadre de perception des nombres entiers au SLAM et aux problèmes de localisation globale, offrant ainsi des solutions «embarquables» sur les systèmes embarquésThe main drawback of using grid-based representations for SLAM and for global localization is the required exponential computational complexity in terms of the grid size (of the map and the pose maps). The required grid size for modeling the environment surrounding a robot or of a vehicle can be in the order of thousands of millions of cells. For instance, a 2D square-shape space of size 100m × 100m, with a cell size of 10cm is modelled with a grid of 1 million cells. If we include a 2m of height to represent the third dimension, 20 millions of cells are required. Consequently, classical grid-based SLAM and global localization approaches require a parallel computing unit in order to meet the latency imposed by safety standards. Such a computation is usually done over workstations embedding Graphical Processing Units (GPUs) and/or a high-end CPUs. However, autonomous vehicles cannot handle such platforms for cost reason, and certification issues. Also, these platforms require a high power consumption that cannot fit within the limited source of energy available in some robots. Embedded hardware platforms are com- monly used as an alternative solution in automotive applications. These platforms meet the low-cost, low-power and small-space constraints. Moreover, some of them are automotive certified1, following the ISO26262 standard. However, most of them are not equipped with a floating-point unit, which limits the computational performance.The sigma-fusion project team in the LIALP laboratory at CEA-Leti has developed an integer-based perception method suitable for embedded devices. This method builds an occupancy grid via Bayesian fusion using integer arithmetic only, thus its "embeddability" on embedded computing platforms, without floating-point unit. This constitutes the major contribution of the PhD thesis of Tiana Rakotovao [Rakotovao Andriamahefa 2017].The objective of the present PhD thesis is to extend the integer perception framework to SLAM and global localization problems, thus offering solutions “em- beddable” on embedded systems
39
Godau, Claudia. "Cognitive bases of spontaneous shortcut use in primary school arithmetic." Doctoral thesis, Humboldt-Universität zu Berlin, Lebenswissenschaftliche Fakultät, 2015. http://dx.doi.org/10.18452/17110.
Full textAbstract:
Aufgabengeeignete Rechenstrategien flexibel zu nutzen ist ein wichtiges Ziel mathematischer Bildung und Bestandteil der Bildungsstandards der Grundschulmathematik. Kinder sollen spontan entscheiden, ob sie arithmetische Aufgaben in üblicher Weise berechnen oder ob sie Zeit und Aufwand investieren, um nach Vereinfachungsstrategien zu suchen und diese anzuwenden. Der Schwerpunkt der aktuellen Arbeit ist, wie Schüler beim flexiblen Erkennen und Anwenden von Vereinfachungsstrategien unterstützt werden können. Kontextfaktoren werden untersucht, welche die spontane Nutzung von Vereinfachungsstrategien unterstützen und den Transfer zwischen ihnen beeinflussen. Kognitive Theorien über die Entwicklung von mathematischen Konzepten und Strategien wurden mit Erkenntnissen aus der Expertise Forschung verbunden, welche die Unterschiede in der Flexibilität zwischen Experten und Novizen offen legen. Im Rahmen der iterativen Entwicklung von mathematischen Konzepten könnte ein erfolgreiches Erkennen und Anwenden einer Vereinfachungsstrategie von Faktoren, die konzeptionelles und/oder prozedurales Wissen aktivieren, profitieren. Am Beispiel von Vereinfachungsstrategien, die auf dem Kommutativgesetz (a + b = b + a) basieren, werden drei Kontextfaktoren (Instruktion, Assoziation und Schätzen), die spontanen Strategiegebrauch unterstützen oder behindern, untersucht. Insgesamt zeigt die Dissertation, dass spontane Strategienutzung durch bestimmte Kontextfaktoren unterstützt und durch Andere behindert werden kann. Diese Kontextfaktoren können im Prinzip in der Schulumgebung gesteuert werden.Flexible use of task-appropriate solving strategies is an important goal in mathematical education and educational standard of elementary school mathematics. Children need to decide spontaneously whether they calculate arithmetic problems the usual way or whether they invest time and effort to search for shortcut options and apply them. The focus of the current work lies on how students can be supported in spotting and applying shortcut strategies flexibly. Contextual factors are investigated that support the spontaneous usage of shortcuts and influences the transfer between them. Cognitive theories about how mathematical concepts and strategies develop were combined with findings from research on expertise, which disclose differences between the flexibility of experts and novices. In line with iterativ development of mathematical concepts successfully spotting and applying a shortcut might thus benefit from factors activating conceptual and/or procedural knowledge. Shortcuts based on commutativity (a + b = b + a) are used as a test case to investigat three contextual factors (instruction, association and estimation), which support or hinder spontaneous strategy use. Overall, the dissertation shows that spontaneous strategy use can be supported by some contextual factors and impeded by others. These contextual factors can, in principle, be controlled in school environment.
40
Miyamoto, Kenji. "Program extraction from coinductive proofs and its application to exact real arithmetic." Diss., Ludwig-Maximilians-Universität München, 2013. http://nbn-resolving.de/urn:nbn:de:bvb:19-177777.
Full textAbstract:
Program extraction has been initiated in the field of constructive
mathematics, and it attracts interest not only from mathematicians but
also from computer scientists nowadays. From a mathematical viewpoint
its aim is to figure out computational meaning of proofs, while from a
computer-scientific viewpoint its aim is the study of a method to
obtain correct programs. Therefore, it is natural to have both
theoretical results and a practical computer system to develop
executable programs via program extraction.
In this Thesis we study the computational interpretation of
constructive proofs involving inductive and coinductive reasoning. We
interpret proofs by translating the computational content of proofs
into executable program code. This translation is the procedure we
call program extraction and it is given through Kreisel's modified
realizability. Here we study a proof-theoretic foundation for program
extraction, enriching the proof assistant system Minlog based on this
theoretical improvement. Once a proof of a formula is written in
Minlog, a program can be extracted from the proof by the system
itself, and the extracted program can be executed in Minlog.
Moreover, extracted programs are provably correct with respect to the
proven formula due to a soundness theorem which we prove. We practice
program extraction by elaborating some case studies from exact real
arithmetic within our formal theory. Although these case studies have
been studied elsewhere, here we offer a formalization of them in
Minlog, and also machine-extraction of the corresponding programs.Die Methode der Programmextraktion hat ihren Ursprung im Bereich der konstruktiven Mathematik, und stößt in letzter Zeit auf viel Interesse nicht nur bei Mathematikern sondern auch bei Informatikern. Vom Standpunkt der Mathematik ist ihr Ziel, aus Beweisen ihre rechnerische Bedeutung abzulesen, während vom Standpunkt der Informatik ihr Ziel die Untersuchung einer Methode ist, beweisbar korrekte Programme zu erhalten. Es ist deshalb naheliegend, neben theoretischen Ergebnissen auch ein praktisches Computersystem zur Verfügung zu haben, mit dessen Hilfe durch Programmextraktion lauffähige Programme entwickelt werden können. In dieser Doktorarbeit wird eine rechnerische Interpretation konstruktiver Beweise mit induktiven und koinduktiven Definitionen angegeben und untersucht. Die Interpretation geschieht dadurch, daß der rechnerische Gehalt von Beweisen in eine Programmiersprache übersetzt wird. Diese übersetzung wird Programmextraktion genannt; sie basiert auf Kreisels modifizierter Realisierbarkeit. Wir untersuchen die beweistheoretischen Grundlagen der Programmextraktion und erweitern den Beweisassistenten Minlog auf der Basis der erhaltenen theoretischen Resultate. Wenn eine Formel in Minlog formal bewiesen ist, läßt sich ein Programm aus dem Beweis extrahieren, und dieses extrahierte Programm kann in Minlog ausgeführt werden. Ferner sind extrahierte Programme beweisbar korrekt bezüglich der entsprechenden Formel aufgrund eines Korrektheitsatzes, den wir beweisen werden. Innerhalb unserer formalen Theorie bearbeiten wir einige aus der Literatur bekannte Fallstudien im Bereich der exakten reellen Arithmetik. Wir entwickeln eine vollständige Formalisierung der entsprechenden Beweise und diskutieren die in Minlog automatisch extrahierten Programme.
41
Chelton, William N. "Galois Field GF (2'') Arithmetic Circuits and Their Application in Elliptic Curve Cryptography." Thesis, University of Sheffield, 2008. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.490334.
Full text
42
Katayama, Shin-ichi. "A Theorem on the Cohomology of Groups and some Arithmetical Applications." 京都大学 (Kyoto University), 1985. http://hdl.handle.net/2433/86360.
Full text
43
Lo, Haw-Jing. "Design of a reusable distributed arithmetic filter and its application to the affine projection algorithm." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2009. http://hdl.handle.net/1853/28199.
Full textAbstract:
Thesis (M. S.)--Electrical and Computer Engineering, Georgia Institute of Technology, 2009.Committee Chair: Anderson, Dr. David V.; Committee Member: Hasler, Dr. Paul E.; Committee Member: Mooney, Dr. Vincent J.; Committee Member: Taylor, Dr. David G.; Committee Member: Vuduc, Dr. Richard.
44
Miyamoto, Kenji [Verfasser], and Helmut [Akademischer Betreuer] Schwichtenberg. "Program extraction from coinductive proofs and its application to exact real arithmetic / Kenji Miyamoto. Betreuer: Helmut Schwichtenberg." München : Universitätsbibliothek der Ludwig-Maximilians-Universität, 2013. http://d-nb.info/1065610521/34.
Full text
45
Miyamoto, Kenji Verfasser], and Helmut [Akademischer Betreuer] [Schwichtenberg. "Program extraction from coinductive proofs and its application to exact real arithmetic / Kenji Miyamoto. Betreuer: Helmut Schwichtenberg." München : Universitätsbibliothek der Ludwig-Maximilians-Universität, 2013. http://nbn-resolving.de/urn:nbn:de:bvb:19-177777.
Full text
46
Najahi, Mohamed amine. "Synthesis of certified programs in fixed-point arithmetic, and its application to linear algebra basic blocks : and its application to linear algebra basic blocks." Thesis, Perpignan, 2014. http://www.theses.fr/2014PERP1212.
Full textAbstract:
Pour réduire les coûts des systèmes embarqués, ces derniers sont livrés avec des micro-processeurs peu puissants. Ces processeurs sont dédiés à l'exécution de tâches calculatoires dont certaines, comme la transformée de Fourier rapide, peuvent s'avérer exigeantes en termes de ressources de calcul. Afin que les implémentations de ces algorithmes soient efficaces, les programmeurs utilisent l'arithmétique à virgule fixe qui est plus adaptée aux processeurs dépourvus d'unité flottante. Cependant, ils se retrouvent confrontés à deux difficultés: D'abord, coder en virgule fixe est fastidieux et exige que le programmeur gère tous les détails arithmétiques. Ensuite, et en raison de la faible dynamique des nombres à virgule fixe par rapport aux nombres flottants, les calculs en fixe sont souvent perçus comme intrinsèquement peu précis. La première partie de cette thèse propose une méthodologie pour dépasser ces deux limitations. Elle montre comment concevoir et mettre en œuvre des outils pour générer automatiquement des programmes en virgule fixe. Ensuite, afin de rassurer l'utilisateur quant à la qualité numérique des codes synthétisés, des certificats sont générés qui fournissent des bornes sur les erreurs d'arrondi. La deuxième partie de cette thèse est dédiée à l'étude des compromis lors de la génération de programmes en virgule fixe pour les briques d'algèbre linéaire. Des données expérimentales y sont fournies sur la synthèse de code pour la multiplication et l'inversion matriciellesTo be cost effective, embedded systems are shipped with low-end micro-processors. These processors are dedicated to one or few tasks that are highly demanding on computational resources. Examples of widely deployed tasks include the fast Fourier transform, convolutions, and digital filters. For these tasks to run efficiently, embedded systems programmers favor fixed-point arithmetic over the standardized and costly floating-point arithmetic. However, they are faced with two difficulties: First, writing fixed-point codes is tedious and requires that the programmer must be in charge of every arithmetical detail. Second, because of the low dynamic range of fixed-point numbers compared to floating-point numbers, there is a persistent belief that fixed-point computations are inherently inaccurate. The first part of this thesis addresses these two limitations as follows: It shows how to design and implement tools to automatically synthesize fixed-point programs. Next, to strengthen the user's confidence in the synthesized codes, analytic methods are suggested to generate certificates. These certificates can be checked using a formal verification tool, and assert that the rounding errors of the generated codes are indeed below a given threshold. The second part of the thesis is a study of the trade-offs involved when generating fixed-point code for linear algebra basic blocks. It gives experimental data on fixed-point synthesis for matrix multiplication and matrix inversion through Cholesky decomposition
47
Parashar, Karthick. "Optimisations de niveau système pour les algorithmes de traitement du signal utilisant l'arithmétique virgule fixe." Phd thesis, Université Rennes 1, 2012. http://tel.archives-ouvertes.fr/tel-00783806.
Full textAbstract:
Le problème de l'optimisation des systèmes utilisant l'arithmétique virgule fixe est un problème d'optimisation combinatoire de complexité NP-difficile. Savoir analyser et optimiser des applications complexes et de taille réelle est le thème central de cette thèse. Une technique de type diviser-pour-régner, où un système donné est décomposé en plusieurs petits sous-systèmes organisés selon une hiérarchie est au cœur de cette approche. Cette décomposition ouvre la voie à l'évaluation rapide de la précision et au problème d'optimisation hiérarchique de la largeur des données et des opérations du système. En raison de la réduction du nombre de variables, la convergence du problème d'optimisation hiérarchique vers une solution est beaucoup plus rapide que dans le cas classique. Le modèle "Single Noise Source" (SNS) est proposé pour étudier les statistiques des erreurs de quantification. Au lieu de simplement se concentrer sur la moyenne et la variance du bruit des erreurs dues à la quantification, il fournit également des formules analytiques pour dériver les paramètres statistiques des processus aléatoires produisant les erreurs de quantification équivalentes à une simulation en virgule fixe. En présence des opérations " non-lisses " (un- smooth) telles que la décision dans les modulations QAM, les fonctions Min() ou Max(), etc., il est pour l'instant inévitable d'utiliser la simulation en virgule fixe. Une technique pour l'évaluation analytique des statistiques des erreurs de quantification en présence d'opérateurs non-lisses dans les graphes ne contenant pas de rebouclage est également proposée. Afin de tenir compte également des systèmes ayant des rebouclages, une technique hybride qui utilise le modèle SNS pour accélérer les simulations en virgule fixe est de plus proposée. Un cadre d'utilisation de l'optimisation convexe est proposé comme heuristique pour résoudre le problème d'optimisation des largeurs. Cette nouvelle technique améliore non seulement la qualité de la solution, mais permet de résoudre le problème plus rapidement que les approches itératives classiques. L'application des techniques proposées permet non seulement de réduire les coûts du système mais aussi une réduction de plusieurs ordres de grandeur dans le temps nécessaire pour optimiser les systèmes utilisant l'arithmétique virgule fixe.
48
Hachami, Saïd. "Périodes hermitiennes des courbes et application à une formule de chowla-selberg." Nancy 1, 1988. http://www.theses.fr/1988NAN10142.
Full textAbstract:
La nouvelle démonstration de la formule de chowla-selberg dans le cas P = 7 consiste à exhiber une application méromorphe entre la courbe de fermat X**(7) + Y**(7) + Z**(7) = 0 de P::(2)(C) et une courbe elliptique. Un calcul direct que D. Barlet a effectué précédemment en liaison avec le calcul de la forme hermitienne cannonique des singularités isolées des surfaces de fermat X**(A) + Y**(B) + Z**(C) dans C**(3) montraient qu'une période hermitienne convenable sur la courbe X**(7) + Y**(7) + Z**(7) coincidait avec le membre de droite de la formule de chowla-selberg pour P = 7 (à des constantes triviales près). La construction élaborée permet de relier directement cette période hermitienne à l'aide du parallélogramme d'une courbe elliptique
49
Gerner, Alexander. "A novel strategy for estimating groundwater recharge in arid mountain regions and its application to parts of the Jebel Akhdar Mountains (Sultanate of Oman)." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2014. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-137045.
Full textAbstract:
In arid regions, mountain catchments are the major contributor to the total natural water yield. Due to generally low groundwater tables, subsurface underflow - referred to as mountain-front recharge - is important in distinction to the surface runoff at the mountain front. The extent of the groundwater basin is hereby often vague. Approaches to assess mountain-front recharge are mostly based on groundwater data and integrate over time and space. This, however, cannot provide prognostic and time-dependent estimates of subsurface inflow to the adjacent alluvial basin aquifer. Consequently, the proposed strategy builds on rainfall based approaches. Temporal and spatial resolution is in this case mostly limited by data scarcity regarding hydrological characteristics of the catchment area and high-resolution rainfall data. The proposed novel strategy combines three approaches to tackle these challenges. A newly developed conceptual hydrologic model provides time-dependent estimates based on fully distributed monthly rainfall. For distinct response units and seasons, non-linear relationships between rainfall and recharge describe the hydrogeologic response. The derivation of the response functions is based on a mass balance and considers the principal recharge mechanisms. Parameterisation makes use of available expert knowledge on geomorphology and seasonal rainfall characteristics. As an efficient tool to assess uncertainties, fuzzy arithmetic is used for complementary long-term average water balance estimates. This technique allows considering fuzziness in rainfall input, crop water use in mountain oases, and best available assumptions on recharge as portion of rainfall. Uncertainty regarding the potential, albeit unknown extent of groundwater basins is portrayed based on continuous surfaces which represent the degree of membership to a distinct geographical entity (termed as fuzzy regions). Distinct subsets of these fuzzy regions represent potential groundwater basins for water balance assessment. The proposed strategy was applied on the large scale in an arid karst mountain range in northern Oman. The two complementary assessment approaches result in similar ranges of values. They are in good agreement with inversely computed inflow to a steady state groundwater model for the adjacent basin aquifer. The results of the conceptual hydrologic model are confirmed by the plausibility of average recharge rates for distinct response units and seasons. This shows that less intense winter rainfall contributes mainly to groundwater recharge. Uncertainties due to the vague extent of the groundwater basin are about 30 % of the total mean annual value. An option to mitigate this uncertainty is the complementary consideration of adjacent aquifer systems in future studies. Hydrogeologic survey and observation of groundwater levels in the alluvial basin aquifer in near distance to the mountains is a way to underpin these findings in future studies. This recommenddation applies not only to the discussed study area, but also to mountain block systems in generalIn ariden Gebieten haben Gebirgseinzugsgebiete einen wesentlichen Anteil am gesamten natürlichen Wasserdargebot. Aufgrund i. Allg. tief liegender Grundwasserspiegel ist - in Abgrenzung zum Oberflächenabfluss am Gebirgsrand - auch der unterirdische Abstrom (mountain-front recharge) von besonderer Bedeutung. Die Ausdehnung des unterirdischen Einzugsgebiets ist dabei oft vage. Ansätze zur Abschätzung des mountain-front recharge basieren meist auf Grundwasserdaten und integrieren in Zeit und Raum. Damit können allerdings keine prognostischen oder zeitabhängigen Schätzungen für den Zustrom zur benachbarten alluvialen Aquifer gemacht werden. Daher wird im folgenden ein niederschlagsbasierter Ansatz vorgeschlagen. Das vorgeschlagene neue Konzept kombiniert drei Ansätze, um den genannten Herausforderungen zu begegnen. Mit einem neu entwickelten konzeptionellen hydrologischen Modell auf Basis verteilter Niederschläge werden monatliche Werte für die Grundwasserneubildung bereitgestellt. Es basiert auf nicht-linearen Beziehungen zwischen Niederschlag und Grundwasserneubildung für definierte hydrologisch homogene Einheiten und Jahreszeiten. Deren Ableitung basiert auf einer Massenbilanz und berücksichtigt die wesentlichen Neubildungsmechanismen. Die Parametrisierung basiert auf Expertenwissen zu Geomorphologie und Niederschlagscharakteristika. Fuzzy Arithmetik wird zur Berücksichtigung von Unsicherheiten in einer ergänzenden mittleren jährlichen Wasserbilanz verwendet. Damit können Unschärfen im Niederschlagsinput, beim Pflanzenwasserbedarf in Gebirgsoasen und best verfügbaren Schätzungen der Neubildung als Bruchteil des Niederschlags effizient berücksichtigt werden. Mittels kontinuierlicher Oberflächen, die den Grad der Zugehörigkeit zu einer bestimmten geographischen Entität anzeigen (fuzzy regions) werden Unsicherheiten in der räumlichen Ausdehnung der unterirdischen Einzugsgebiete beschrieben. Definierte Teilmengen dieser fuzzy regions werden dann bei den Wasserhaushaltsbetrachtungen als potentielle Grundwassereinzugsgebiete verwendet. Der vorgeschlagene Ansatz wurde in einer ariden, teils verkarsteten Gebirgsregion im Norden des Sultanats Oman angewendet. Die beiden sich ergänzenden Ansätze zur Abschätzung der Grundwasserneubildung ergaben im langjährigen Mittel vergleichbare Werte. Diese stimmten auch gut mit den Ergebnissen einer inversen Grundwassermodellierung überein. Die Plausibilität der Neubildungsraten für bestimmte hydrologisch homogene Einheiten und Jahreszeiten spricht für die Verlässlichkeit der Ergebnisse des konzeptionellen hydrologischen Modells. Offensichtlich tragen insbesondere die weniger intensiven Winterniederschläge wesentlich zur Grundwasserneubildung bei. Die Unsicherheiten bezüglich der Ausdehnung des Grundwassereinzugsgebiets belaufen sich auf ca. 30 % des mittleren jährlichen Dargebots. Die komplementäre Betrachtung benachbarter Grundwassereinzugsgebiete ist ein denkbarer Weg, diese Unsicherheit in Zukunft zu reduzieren. Ein wesentlicher Beitrag um die Ergebnisse dieser Studie zukünftig weiter zu untermauern wären hydrogeologische Erkundung und Beobachtung von Grundwasserständen im alluvialen Aquifer, insbesondere nahe dem Gebirgsrand. Diese Empfehlung gilt über dieses Fallbeispiel hinaus für vergleichbare Systeme, in denen ein Gebirgseinzugsgebiet den Aquifer in der angrenzende Ebene speist
50
Masoudi, Pedram. "Application of hybrid uncertainty-clustering approach in pre-processing well-logs." Thesis, Rennes 1, 2017. http://www.theses.fr/2017REN1S023/document.
Full textAbstract:
La thèse est principalement centrée sur l'étude de la résolution verticale des diagraphies. On outre, l'arithmétique floue est appliquée aux modèles expérimentaux pétrophysiques en vue de transmettre l'incertitude des données d'entrée aux données de sortie, ici la saturation irréductible en eau et la perméabilité. Les diagraphies sont des signaux digitaux dont les données sont des mesures volumétriques. Le mécanisme d'enregistrement de ces données est modélisé par des fonctions d'appartenance floues. On a montré que la Résolution Verticale de la Fonction d'Appartenance (VRmf) est supérieur d'espacement. Dans l'étape suivante, la fréquence de Nyquist est revue en fonction du mécanisme volumétrique de diagraphie ; de ce fait, la fréquence volumétrique de Nyquist est proposée afin d'analyser la précision des diagraphies. Basé sur le modèle de résolution verticale développée, un simulateur géométrique est conçu pour générer les registres synthétiques d'une seule couche mince. Le simulateur nous permet d'analyser la sensibilité des diagraphies en présence d'une couche mince. Les relations de régression entre les registres idéaux (données d'entrée de ce simulateur) et les registres synthétiques (données de sortie de ce simulateur) sont utilisées comme relations de déconvolution en vue d'enlever l'effet des épaules de couche d'une couche mince sur les diagraphies GR, RHOB et NPHI. Les relations de déconvolution ont bien été appliquées aux diagraphies pour caractériser les couches minces. Par exemple, pour caractériser une couche mince poreuse, on a eu recours aux données de carottage qui étaient disponibles pour la vérification : NPHI mesuré (3.8%) a été remplacé (corrigé) par 11.7%. NPHI corrigé semble être plus précis que NPHI mesuré, car la diagraphie a une valeur plus grande que la porosité de carottage (8.4%). Il convient de rappeler que la porosité totale (NPHI) ne doit pas être inférieure à la porosité effective (carottage). En plus, l'épaisseur de la couche mince a été estimée à 13±7.5 cm, compatible avec l'épaisseur de la couche mince dans la boite de carottage (<25 cm). Normalement, l'épaisseur in situ est inférieure à l'épaisseur de la boite de carottage, parce que les carottes obtenues ne sont plus soumises à la pression lithostatique, et s'érodent à la surface du sol. La DST est appliquée aux diagraphies, et l'intervalle d'incertitude de DST est construit. Tandis que la VRmf des diagraphies GR, RHOB, NPHI et DT est ~60 cm, la VRmf de l'intervalle d'incertitude est ~15 cm. Or, on a perdu l'incertitude de la valeur de diagraphie, alors que la VRmf est devenue plus précise. Les diagraphies ont été ensuite corrigées entre l'intervalle d'incertitude de DST avec quatre simulateurs. Les hautes fréquences sont amplifiées dans les diagraphies corrigées, et l'effet des épaules de couche est réduit. La méthode proposée est vérifiée dans les cas synthétiques, la boite de carottage et la porosité de carotte. L'analyse de partitionnement est appliquée aux diagraphies NPHI, RHOB et DT en vue de trouver l'intervalle d'incertitude, basé sur les grappes. Puis, le NPHI est calibré par la porosité de carottes dans chaque grappe. Le √MSE de NPHI calibré est plus bas par rapport aux cinq modèles conventionnels d'estimation de la porosité (au minimum 33% d'amélioration du √MSE). Le √MSE de généralisation de la méthode proposée entre les puits voisins est augmenté de 42%. L'intervalle d'incertitude de la porosité est exprimé par les nombres flous. L'arithmétique floue est ensuite appliquée dans le but de calculer les nombres flous de la saturation irréductible en eau et de la perméabilité. Le nombre flou de la saturation irréductible en eau apporte de meilleurs résultats en termes de moindre sous-estimation par rapport à l'estimation nette. Il est constaté que lorsque les intervalles de grappes de porosité ne sont pas compatibles avec la porosité de carotte, les nombres flous de la perméabilité ne sont pas valablesIn the subsurface geology, characterization of geological beds by well-logs is an uncertain task. The thesis mainly concerns studying vertical resolution of well-logs (question 1). In the second stage, fuzzy arithmetic is applied to experimental petrophysical relations to project the uncertainty range of the inputs to the outputs, here irreducible water saturation and permeability (question 2). Regarding the first question, the logging mechanism is modelled by fuzzy membership functions. Vertical resolution of membership function (VRmf) is larger than spacing and sampling rate. Due to volumetric mechanism of logging, volumetric Nyquist frequency is proposed. Developing a geometric simulator for generating synthetic-logs of a single thin-bed enabled us analysing sensitivity of the well-logs to the presence of a thin-bed. Regression-based relations between ideal-logs (simulator inputs) and synthetic-logs (simulator outputs) are used as deconvolution relations for removing shoulder-bed effect of thin-beds from GR, RHOB and NPHI well-logs. NPHI deconvolution relation is applied to a real case where the core porosity of a thin-bed is 8.4%. The NPHI well-log is 3.8%, and the deconvolved NPHI is 11.7%. Since it is not reasonable that the core porosity (effective porosity) be higher than the NPHI (total porosity), the deconvolved NPHI is more accurate than the NPHI well-log. It reveals that the shoulder-bed effect is reduced in this case. The thickness of the same thin-bed was also estimated to be 13±7.5 cm, which is compatible with the thickness of the thin-bed in the core box (<25 cm). Usually, in situ thickness is less than the thickness of the core boxes, since at the earth surface, there is no overburden pressure, also the cores are weathered. Dempster-Shafer Theory (DST) was used to create well-log uncertainty range. While the VRmf of the well-logs is more than 60 cm, the VRmf of the belief and plausibility functions (boundaries of the uncertainty range) would be about 15 cm. So, the VRmf is improved, while the certainty of the well-log value is lost. In comparison with geometric method, DST-based algorithm resulted in a smaller uncertainty range of GR, RHOB and NPHI logs by 100%, 71% and 66%, respectively. In the next step, cluster analysis is applied to NPHI, RHOB and DT for the purpose of providing cluster-based uncertainty range. Then, NPHI is calibrated by core porosity value in each cluster, showing low √MSE compared to the five conventional porosity estimation models (at least 33% of improvement in √MSE). Then, fuzzy arithmetic is applied to calculate fuzzy numbers of irreducible water saturation and permeability. Fuzzy number of irreducible water saturation provides better (less overestimation) results than the crisp estimation. It is found that when the cluster interval of porosity is not compatible with the core porosity, the permeability fuzzy numbers are not valid, e.g. in well#4. Finally, in the possibilistic approach (the fuzzy theory), by calibrating α-cut, the right uncertainty interval could be achieved, concerning the scale of the study