000			06157nam a22005653i 4500
001			EBC4533883
003			MiAaPQ
005			20240729130520.0
006			m o d |
007			cr cnu||||||||
008			240724s2016 xx o ||||0 eng d
020			_a9783110413335 _q(electronic bk.)
020			_z9783110413328
035			_a(MiAaPQ)EBC4533883
035			_a(Au-PeEL)EBL4533883
035			_a(CaPaEBR)ebr11214970
035			_a(CaONFJC)MIL927184
035			_a(OCoLC)951223219
040			_aMiAaPQ _beng _erda _epn _cMiAaPQ _dMiAaPQ
050		4	_aQA162.D5413 2016
082	0		_a511.3/3
100	1		_aDiekert, Volker.
245	1	0	_aDiscrete Algebraic Methods : _bArithmetic, Cryptography, Automata and Groups.
250			_a1st ed.
264		1	_aBerlin/Boston : _bWalter de Gruyter GmbH, _c2016.
264		4	_c©2016.
300			_a1 online resource (354 pages)
336			_atext _btxt _2rdacontent
337			_acomputer _bc _2rdamedia
338			_aonline resource _bcr _2rdacarrier
490	1		_aDe Gruyter Textbook Series
505	0		_aIntro -- Contents -- Preface -- 1. Algebraic structures -- 1.1 Groups -- 1.2 Regular polygons -- 1.3 Symmetric groups -- 1.4 Rings -- 1.5 Modular arithmetic -- 1.5.1 Euclidean algorithm -- 1.5.2 Ideals in the integers -- 1.5.3 Chinese remainder theorem -- 1.5.4 Euler's totient function -- 1.6 Polynomials and formal power series -- 1.7 Hilbert's basis theorem -- 1.8 Fields -- 1.9 Finite fields -- 1.10 Units modulo n -- 1.11 Quadratic reciprocity -- Exercises -- Summary -- 2. Cryptography -- 2.1 Symmetric encryption methods -- 2.2 Monoalphabetic cipher -- 2.3 Polyalphabetic cipher -- 2.4 Frequency analysis and coincidence index -- 2.5 Perfect security and the Vernam one-time pad -- 2.6 Asymmetric encryption methods -- 2.7 RSA cryptosystem -- 2.8 Rabin cryptosystem -- 2.9 Diffie-Hellman key exchange -- 2.10 ElGamal cryptosystem -- 2.11 Cryptographic hash functions -- 2.12 Digital signatures -- 2.13 Secret sharing -- 2.14 Digital commitment -- 2.15 Shamir's attack on the Merkle-Hellman cryptosystem -- Exercises -- Summary -- 3. Number theoretic algorithms -- 3.1 Runtime analysis of algorithms -- 3.2 Fast exponentiation -- 3.3 Binary GCD -- 3.4 Probabilistic recognition of primes -- 3.4.1 Fermat primality test and Carmichael numbers -- 3.4.2 Solovay-Strassen primality test -- 3.4.3 Miller-Rabin primality test -- 3.4.4 Applications of the Miller-Rabin scheme -- 3.4.5 Miller-Rabin versus Solovay-Strassen -- 3.5 Extracting roots in finite fields -- 3.5.1 Tonelli's algorithm -- 3.5.2 Cipolla's algorithm -- 3.6 Integer factorization -- 3.6.1 Pollard's p - 1 algorithm -- 3.6.2 Pollard's rho algorithm for factorization -- 3.6.3 Quadratic sieve -- 3.7 Discrete logarithm -- 3.7.1 Shanks' baby-step giant-step algorithm -- 3.7.2 Pollard's rho algorithm for the discrete logarithm -- 3.7.3 Pohlig-Hellman algorithm for group order reduction -- 3.7.4 Index calculus.
505	8		_a3.8 Multiplication and division -- 3.9 Discrete fourier transform -- 3.10 Primitive roots of unity -- 3.11 Schönhage-Strassen integer multiplication -- Exercises -- Summary -- 4. Polynomial time primality test -- 4.1 Basic idea -- 4.2 Combinatorial tools -- 4.3 Growth of the least common multiple -- 4.4 Of small numbers and large orders -- 4.5 Agrawal-Kayal-Saxena primality test -- Summary -- 5. Elliptic curves -- 5.1 Group law -- 5.1.1 Lines -- 5.1.2 Polynomials over elliptic curves -- 5.1.3 Divisors -- 5.1.4 Picard group -- 5.2 Applications of elliptic curves -- 5.2.1 Diffie-Hellman key exchange with elliptic curves -- 5.2.2 Pseudocurves -- 5.2.3 Factorization using elliptic curves -- 5.2.4 Goldwasser-Kilian primality certificates -- 5.3 Endomorphisms of elliptic curves -- Exercises -- Summary -- 6. Combinatorics on words -- 6.1 Commutation, transposition and conjugacy -- 6.2 Fine and Wilf's periodicity lemma -- 6.3 Kruskal's tree theorem -- Exercises -- Summary -- 7. Automata -- 7.1 Recognizable sets -- 7.2 Rational sets -- 7.3 Regular languages -- 7.4 Star-free languages -- 7.5 Krohn-Rhodes theorem -- 7.6 Green's relations -- 7.7 Automata over infinite words -- 7.7.1 Deterministic Büchi automata -- 7.7.2 Union and intersection -- 7.7.3 Omega-rational languages -- 7.7.4 Recognizability of omega-regular languages -- 7.7.5 Monadic second-order logic over infinite words -- 7.8 Presburger arithmetic -- 7.9 Solutions of linear Diophantine systems -- Exercises -- Summary -- 8. Discrete infinite groups -- 8.1 Classical algorithmic problems -- 8.2 Residually finite monoids -- 8.3 Presentations -- 8.4 Rewriting systems -- 8.4.1 Termination and confluence -- 8.4.2 Semi-Thue systems -- 8.5 Solving the word problem in finitely presented monoids -- 8.6 Free partially commutative monoids and groups -- 8.7 Semidirect products.
505	8		_a8.8 Amalgamated products and HNN extensions -- 8.9 Rational sets and Benois' theorem -- 8.10 Free groups -- 8.11 The automorphism group of free groups -- 8.12 The special linear group SL(2, Z) -- Exercises -- Summary -- Solutions to exercises -- Chapter 1 -- Chapter 2 -- Chapter 3 -- Chapter 5 -- Chapter 6 -- Chapter 7 -- Chapter 8 -- Bibliography -- Index.
588			_aDescription based on publisher supplied metadata and other sources.
590			_aElectronic reproduction. Ann Arbor, Michigan : ProQuest Ebook Central, 2024. Available via World Wide Web. Access may be limited to ProQuest Ebook Central affiliated libraries.
650		0	_aOrdered algebraic structures--Textbooks.
650		0	_aAlgorithms--Textbooks.
650		0	_aComputer science--Mathematics--Textbooks.
650		0	_aCryptography--Textbooks.
650		0	_aAlgebra--Textbooks.
655		4	_aElectronic books.
700	1		_aKufleitner, Manfred.
700	1		_aRosenberger, Gerhard.
700	1		_aHertrampf, Ulrich.
776	0	8	_iPrint version: _aDiekert, Volker _tDiscrete Algebraic Methods _dBerlin/Boston : Walter de Gruyter GmbH,c2016 _z9783110413328
797	2		_aProQuest (Firm)
830		3	_aDe Gruyter Textbook Series
856	4	0	_uhttps://ebookcentral.proquest.com/lib/orpp/detail.action?docID=4533883 _zClick to View
999			_c110961 _d110961