Number Theoretic Methods in Cryptography: Complexity lower by Igor Shparlinski PDF

By Igor Shparlinski

ISBN-10: 3034886640

ISBN-13: 9783034886642

ISBN-10: 3034897235

ISBN-13: 9783034897235

The booklet introduces new innovations which suggest rigorous decrease bounds at the complexity of a few quantity theoretic and cryptographic difficulties. those tools and strategies are according to bounds of personality sums and numbers of ideas of a few polynomial equations over finite fields and residue jewelry. It additionally encompasses a variety of open difficulties and suggestions for extra learn. We receive a number of reduce bounds, exponential by way of logp, at the de grees and orders of • polynomials; • algebraic capabilities; • Boolean capabilities; • linear habitual sequences; coinciding with values of the discrete logarithm modulo a first-rate p at suf ficiently many issues (the variety of issues could be as small as pI/He). those features are thought of over the residue ring modulo p and over the residue ring modulo an arbitrary divisor d of p - 1. The case of d = 2 is of certain curiosity because it corresponds to the illustration of the fitting so much little bit of the discrete logarithm and defines no matter if the argument is a quadratic residue. We additionally receive non-trivial higher bounds at the de gree, sensitivity and Fourier coefficients of Boolean services on bits of x determining no matter if x is a quadratic residue. those effects are used to acquire reduce bounds at the parallel mathematics and Boolean complexity of computing the discrete logarithm. for instance, we end up that any unbounded fan-in Boolean circuit. of sublogarithmic intensity computing the discrete logarithm modulo p has to be of superpolynomial size.

Show description

Read or Download Number Theoretic Methods in Cryptography: Complexity lower bounds PDF

Similar science books

New PDF release: The Magnetic Field of the Earth's Lithosphere: The Satellite

Many geological positive factors of the Earth's lithosphere create adaptations within the Earth's magnetic box that may be detected via satellites. The ensuing magnetic anomaly maps offers new insights into the tectonic gains and huge constructions of the lithosphere. This ebook records the purchase, aid and research of satellite tv for pc magnetic box facts within the examine of the Earth's lithosphere.

Read e-book online The Periodic Table: A Very Short Introduction PDF

During this authoritative Very brief advent to the periodic desk, Eric Scerri offers a contemporary and clean exploration of this basic subject within the actual sciences, contemplating the deeper implications of the preparations of the desk to atomic physics and quantum mechanics. Scerri seems to be on the traits in homes of parts that ended in the development of the periodic desk, and the way the deeper which means of its constitution progressively grew to become obvious with the improvement of atomic idea and quantum mechanics, in order that physics arguably got here to colonize a wholly diverse technological know-how, chemistry.

Get Worldviews: An Introduction to the History and Philosophy of PDF

Up to date all through and with 3 completely new chapters, Worldviews: An creation to the heritage and Philosophy of technology, moment version furthers its attractiveness because the definitive introductory textual content at the historic advancements and philosophical matters that tell our medical view of the area round us.

Read e-book online Complexity and the Arrow of Time PDF

There's a frequent assumption that the universe mostly, and existence particularly, is 'getting extra advanced with time'. This ebook brings jointly quite a lot of specialists in technology, philosophy and theology and unveils their joint attempt in exploring this concept. They confront crucial difficulties in the back of the speculation of complexity and the function of existence inside it: what's complexity?

Extra info for Number Theoretic Methods in Cryptography: Complexity lower bounds

Sample text

In particular, if H ~ max{8p'5, pl/2+<5logp} with some fixed (j> 0 then the order of the sequence must be exponentially large, n » p8 . It is interesting to note that the lower bound does not depend on the divisor d. In particular, selecting d = 2, we see that even the rightmost bit of ind x cannot be given by a linear recurring sequence of small order. 1, one obtains a lower bound L(H) = n(Hp-l/2log -1 p) on the linear complexity profile of the discrete logarithm modulo a divisor d of p - 1. We note that for d = 2 the linear complexity L has been evaluated precisely in [59] as follows (p - 1)/2, p, L={ (p + 1)/2, p-1, ifxp=l ifxp=3 ifxp=5 ifxp=7 (mod (mod (mod (mod 8), 8), 8), 8), see also [56, 58].

8 Chapter 6 Approximation of the Discrete Logarithm by Boolean Functions Here we consider the bitwise approximation of the discrete logarithm given the bit representation of the argument. Moreover, we concentrate on the rightmost bit of ind x. This question is essentially equivalent to deciding quadratic residuacity of x. In [71] (see also [74]) the identity X(q-l)/2 = { 1, -1, if x is a quadratic residue in IFq, if x is a quadratic non-residue in IFq, has been used to obtain the lower bound O(log q) on the depth of arithmetic circuits over IFq deciding whether x E IF; is a quadratic residue (the most important thing is that the degree (q - 1)/2 is large).

N, corresponds to the non-linear complexity of the discrete logarithm on the interval N + 1 :S x :S N + H. Thus if H ~ pI/He then it is n(logp). The result can be extended to any divisor d of p - 1 without any difficulty. 8 Chapter 6 Approximation of the Discrete Logarithm by Boolean Functions Here we consider the bitwise approximation of the discrete logarithm given the bit representation of the argument. Moreover, we concentrate on the rightmost bit of ind x. This question is essentially equivalent to deciding quadratic residuacity of x.

Download PDF sample