The denominator formula for the Monster Lie algebra is the product expansion for the modular function j(z) − j(τ) in terms of the Hecke system of SL2(Z)-modular functions jn(τ). This formula can be reformulated enti...
In CRYPTO 2015, Elias, Lauter, Ozman and Stange described an attack on the non-dual decision version of the ring learning with errors problem (RLWE) for two special families of defining polynomials, whose construction...
详细信息
ISBN:
(数字)9783662498903
ISBN:
(纸本)9783662498903;9783662498897
In CRYPTO 2015, Elias, Lauter, Ozman and Stange described an attack on the non-dual decision version of the ring learning with errors problem (RLWE) for two special families of defining polynomials, whose construction depends on the modulus q that is being used. For particularly chosen error parameters, they managed to solve nondual decision RLWE given 20 samples, with a success rate ranging from 10% to 80 %. In this paper we show how to solve the search version for the same families and error parameters, using only 7 samples with a success rate of 100 %. Moreover our attack works for every modulus q' instead of the q that was used to construct the defining polynomial. The attack is based on the observation that the RLWE error distribution for these families of polynomials is very skewed in the directions of the polynomial basis. For the parameters chosen by Elias et al. the smallest errors are negligible and simple linear algebra suffices to recover the secret. But enlarging the error paremeters makes the largest errors wrap around, thereby turning the RLWE problem unsuitable for cryptographic applications. These observations also apply to dual RLWE, but do not contradict the seminal work by Lyubashevsky, Peikert and Regev.
In Oste and Van der Jeugt, SIGMA, 12 (2016), [13], we classified all pairs of recurrence relations connecting two sets of Hahn, dual Hahn or Racah polynomials of the same type but with different parameters. We examine...
Let R be a real closed field and Q(1), . . . , Q (l) is an element of R[X-1,...,X-k] such that for each i, 1 <= i <= l, deg(Q(i)) <= di. For 1 <= i <= l, denote by Q(i) = {Q(1),..., Q(i)}, Vi the real v...
详细信息
Let R be a real closed field and Q(1), . . . , Q (l) is an element of R[X-1,...,X-k] such that for each i, 1 <= i <= l, deg(Q(i)) <= di. For 1 <= i <= l, denote by Q(i) = {Q(1),..., Q(i)}, Vi the real variety defined by Q(i), and k(i) an upper bound on the real dimension of V-i (by convention V-0 = R-k and k(0) = k). Suppose also that 2 <= d(1) <= d(2) <= 1/k + 1 d(3) <= 1/(k + 1)(2) d(4) <= . . . <= 1/ (k + 1)(l -3) d(l-1) <= 1/(k + 1)(l-2) d(l), and that l <= k. We prove that the number of semi- algebraically connected components of V-l is bounded by O(k)(2k) (Pi(1 <= jalgebraically closed fields and is false over real closed fields) to varieties defined over real closed fields. Additionally, if P subset of R[X-1,..., X-k] is a finite family of polynomials with deg(P) <= d for all P is an element of P, card P = s and dl <= 1/k+1 d, then we prove that the number of semi-algebraically connected components of the realizations of all realizable sign conditions of the family P restricted to V-l is bounded by O(k)(2k) (sd)(kl) (Pi(1 <= japplications in discrete geometry, for proving incidence bounds [ 11, 31], as well as in efficient range searching [20].
This stimulating textbook presents a broad and accessible guide to the fundamentals of discrete mathematics, highlighting how the techniques may be applied to various exciting areas in computing. The text is designed ...
ISBN:
(数字)9783319445618
ISBN:
(纸本)9783319445601
This stimulating textbook presents a broad and accessible guide to the fundamentals of discrete mathematics, highlighting how the techniques may be applied to various exciting areas in computing. The text is designed to motivate and inspire the reader, encouraging further study in this important skill. Features: provides an introduction to the building blocks of discrete mathematics, including sets, relations and functions; describes the basics of numbertheory, the techniques of induction and recursion, and the applications of mathematical sequences, series, permutations, and combinations; presents the essentials of algebra; explains the fundamentals of automata theory, matrices, graph theory, cryptography, coding theory, language theory, and the concepts of computability and decidability; reviews the history of logic, discussing propositional and predicate logic, as well as advanced topics; examines the field of software engineering, describing formal methods; investigates probability and statistics.
We consider two problems. First let u be an element of a quaternion algebra B over (d√)Q(d) such that u is non-central and u2∈ . We relate the complexity of finding an element v′ such that uv′=−v′u and v′2 ∈ to...
详细信息
The idea behind this book is to provide the mathematical foundations for assessing modern developments in the Information Age. It deepens and complements the basic concepts, but it also considers instructive and more ...
详细信息
ISBN:
(数字)9783110413335
ISBN:
(纸本)9783110413328
The idea behind this book is to provide the mathematical foundations for assessing modern developments in the Information Age. It deepens and complements the basic concepts, but it also considers instructive and more advanced topics. The treatise starts with a general chapter on algebraic structures; this part provides all the necessary knowledge for the rest of the book. The next chapter gives a concise overview of cryptography. Chapter 3 on number theoretic algorithms is important for developping cryptosystems, Chapter 4 presents the deterministic primality test of Agrawal, Kayal, and Saxena. The account to elliptic curves again focuses on cryptographic applications and algorithms. With combinatorics on words and automata theory, the reader is introduced to two areas of theoretical computer science where semigroups play a fundamental *** last chapter is devoted to combinatorial group theory and its connections to automata.
Contents: algebraic structures Cryptography number theoretic algorithms Polynomial time primality test Elliptic curves Combinatorics on words Automata Discrete infinite groups
Contains brief chapter summaries as well as examples, problems and solutions.
References for further reading in every chapter.
Mathematical derivations are illustrated by a plethora of illustrations.
Recently the notion of Quaternion Fuzzy numbers (QFN) was introduced in the literature [I]. The Quaternion algebra provides applications in many fields, like the representation of rotation and translation of a rigid b...
详细信息
ISBN:
(纸本)9789813146969
Recently the notion of Quaternion Fuzzy numbers (QFN) was introduced in the literature [I]. The Quaternion algebra provides applications in many fields, like the representation of rotation and translation of a rigid body in three-dimensional space. The purpose of this paper is to briefly present the Quaternion Gradual number(QGN) concept introduced in [2] and shown as the alpha-cut set of QFN can be represented by these numbers.
The Cohn-Umans group-theoretic approach to matrix multiplication suggests embedding matrix multiplication into group algebra multiplication, and bounding ω in terms of the representation theory of the host group. Thi...
详细信息
暂无评论