東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back to Search results for [ null ]

Switch To: Labeled | MARC Mode | ISBD

Algorithms for solving linear and po...

Bard, Gregory V.

Linked to FindBook

Google Book

Amazon

博客來

Algorithms for solving linear and polynomial systems of equations over finite fields, with applications to cryptanalysis.

Record Type:	Language materials, printed : Monograph/item
Title/Author:	Algorithms for solving linear and polynomial systems of equations over finite fields, with applications to cryptanalysis./
Author:	Bard, Gregory V.
Description:	200 p.
Notes:	Adviser: Lawrence C. Washington.
Contained By:	Dissertation Abstracts International68-08B.
Subject:	Computer Science. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3277391
ISBN:	9780549159858

Algorithms for solving linear and polynomial systems of equations over finite fields, with applications to cryptanalysis.
Bard, Gregory V.

Algorithms for solving linear and polynomial systems of equations over finite fields, with applications to cryptanalysis. - 200 p.

Adviser: Lawrence C. Washington.

Thesis (Ph.D.)--University of Maryland, College Park, 2007.

This dissertation contains algorithms for solving linear and polynomial systems of equations over GF (2). The objective is to provide fast and exact tools for algebraic cryptanalysis and other applications. Accordingly, it is divided into two parts.

ISBN: 9780549159858Subjects--Topical Terms:

626642
Computer Science.

Algorithms for solving linear and polynomial systems of equations over finite fields, with applications to cryptanalysis.
LDR:03053nam 2200301 a 45 001 941058
005 20110518
008 110518s2007 ||||||||||||||||| ||eng d
020 $a 9780549159858
035 $a (UMI)AAI3277391
035 $a AAI3277391
040 $a UMI $c UMI
100 1 $a Bard, Gregory V. $3 1084544
245 1 0 $a Algorithms for solving linear and polynomial systems of equations over finite fields, with applications to cryptanalysis.
300 $a 200 p.
500 $a Adviser: Lawrence C. Washington.
500 $a Source: Dissertation Abstracts International, Volume: 68-08, Section: B, page: 5270.
502 $a Thesis (Ph.D.)--University of Maryland, College Park, 2007.
520 $a This dissertation contains algorithms for solving linear and polynomial systems of equations over GF (2). The objective is to provide fast and exact tools for algebraic cryptanalysis and other applications. Accordingly, it is divided into two parts.
520 $a The first part deals with polynomial systems. Chapter 2 contains a successful cryptanalysis of Keeloq, the block cipher used in nearly all luxury automobiles. The attack is more than 16,000 times faster than brute force, but queries 0.62 x 232 plaintexts. The polynomial systems of equations arising from that cryptanalysis were solved via SAT-solvers. Therefore, Chapter 3 introduces a new method of solving polynomial systems of equations by converting them into CNF-SAT problems and using a SAT-solver. Finally, Chapter 4 contains a discussion on how SAT-solvers work internally.
520 $a The second part deals with linear systems over GF (2), and other small fields (and rings). These occur in cryptanalysis when using the XL algorithm, which converts polynomial systems into larger linear systems. We introduce a new complexity model and data structures for GF (2)-matrix operations. This is discussed in Appendix B but applies to all of Part II. Chapter 5 contains an analysis of "the Method of Four Russians" for multiplication and a variant for matrix inversion, which is log n faster than Gaussian Elimination, and can be combined with Strassen-like algorithms. Chapter 6 contains an algorithm for accelerating matrix multiplication over small finite fields. It is feasible but the memory cost is so high that it is mostly of theoretical interest. Appendix A contains some discussion of GF (2)-linear algebra and how it differs from linear algebra in R and C . Appendix C discusses algorithms faster than Strassen's algorithm, and contains proofs that matrix multiplication, matrix squaring, triangular matrix inversion, LUP-factorization, general matrix inversion and the taking of determinants, are equicomplex. These proofs are already known, but are here gathered into one place in the same notation.
590 $a School code: 0117.
650 4 $a Computer Science. $3 626642
650 4 $a Mathematics. $3 515831
690 $a 0405
690 $a 0984
710 2 $a University of Maryland, College Park. $b Applied Mathematics and Scientific Computation. $3 1021743
773 0 $t Dissertation Abstracts International $g 68-08B.
790 $a 0117
790 1 0 $a Washington, Lawrence C., $e advisor
791 $a Ph.D.
792 $a 2007
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3277391