Close
Enter your search into one or more of the boxes below:
You can refine your search by selecting from any of the options below:
Search
Number Theoretic Methods in Cryptography: Complexity lower bounds

Number Theoretic Methods in Cryptography: Complexity lower bounds (Paperback)

£81.00
Printed to order. Despatched in 2-3 weeks.
Email me when back in stock

Synopsis

The book introduces new techniques which imply rigorous lower bounds on the complexity of some number theoretic and cryptographic problems. These methods and techniques are based on bounds of character sums and numbers of solutions of some polynomial equations over finite fields and residue rings. It also contains a number of open problems and proposals for further research. We obtain several lower bounds, exponential in terms of logp, on the de- grees and orders of * polynomials; * algebraic functions; * Boolean functions; * linear recurring sequences; coinciding with values of the discrete logarithm modulo a prime p at suf- ficiently many points (the number of points can be as small as pI/He). These functions are considered 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 special interest since it corresponds to the representation of the right- most bit of the discrete logarithm and defines whether the argument is a quadratic residue. We also obtain non-trivial upper bounds on the de- gree, sensitivity and Fourier coefficients of Boolean functions on bits of x deciding whether x is a quadratic residue. These results are used to obtain lower bounds on the parallel arithmetic and Boolean complexity of computing the discrete logarithm. For example, we prove that any unbounded fan-in Boolean circuit. of sublogarithmic depth computing the discrete logarithm modulo p must be of superpolynomial size.

More books by Igor Shparlinski

Leave Review

Delivery

Delivery Options

All delivery times quoted are the average, and cannot be guaranteed. These should be added to the availability message time, to determine when the goods will arrive. During checkout we will give you a cumulative estimated date for delivery.

Location 1st Book Each additional book Average Delivery Time
UK Second Class Available free for ALL orders. No charge for each additional book. 3-7 Days
UK First Class £4.50 £1.00 1-2 Days
UK Courier £7.00 £1.00 1-2 Days
Western Europe** Courier £17.00 £3.00 2-3 Days
Western Europe** Airmail £5.00 £1.50 4-14 Days
USA / Canada Courier £20.00 £3.00 2-4 Days
USA / Canada Airmail £7.00 £3.00 4-14 Days
Rest of World Courier £22.50 £3.00 3-6 Days
Rest of World Airmail £8.00 £3.00 7-21 Days

** Includes Austria, Belgium, Denmark, France, Germany, Greece, Iceland, Irish Republic, Italy, Luxembourg, Netherlands, Portugal, Spain, Sweden and Switzerland.

Delivery Help & FAQs

Returns Information

If you are not completely satisfied with your purchase*, you may return it to us in its original condition with in 30 days of receiving your delivery or collection notification email for a refund. Except for damaged items or delivery issues the cost of return postage is borne by the buyer. Your statutory rights are not affected.

* For Exclusions and terms on damaged or delivery issues see Returns Help & FAQs

You might also like

Geometry and Complexity Theory
(Hardback)
J. M. Landsberg
 
 
£49.99
 
Introduction to Recursive Programming
(Paperback)
Manuel Rubio-Sanchez
 
 
£61.99
 
Kubernetes - Up and Running
(Paperback)
Kelsey Hightower; Brendan Burns; Joe...
 
 
£34.50
 
Algorithms and Networking for ...
(Hardback)
Jouni Smed; Harri Hakonen
 
 
£60.00
 
Latest Blog
Caroline Taggart on Why Punctuation Can be Surprisingly Exciting
18/10/2017

Caroline Taggart explains the versatility of punctuation.

Under the Knife: Recreating the Grimy World of Victorian Surgery
17/10/2017

Lindsey describes how she made the trailer for her debut The Butchering Art in order to see how the sights, sounds, and smells of this gruesome period in medical history would translate onto the screen.

The Sky Doesn't Have to be Blue: Steve Antony on Life as a Colour Blind Illustrator
13/10/2017

Steve explains what it's like to be a colour blind illustrator and why the sky doesn't have to be blue.

View all Blog Entries
Twitter
Show/Hide Tweets
© W&G Foyle Ltd