Computational problems of quadratic forms [Elektronische Ressource] : complexity and cryptographic perspectives / Rupert Hartung
183 pages
English

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Computational problems of quadratic forms [Elektronische Ressource] : complexity and cryptographic perspectives / Rupert Hartung

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
183 pages
English
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

Computational Problems ofQuadratic Forms:Complexity and CryptographicPerspectivesDissertationzur Erlangung des Doktorgradesder Naturwissenschaftenvorgelegt beim Fachbereich Informatik und Mathematikder Johann Wolfgang Goethe-Universitat¨in Frankfurt am MainvonRupert Hartungaus OberweselFrankfurt am Main, 2007ContentsIntroduction viiTable of Notation xviiI Quadratic Forms and their Applications 11 Preliminaries 31.1 Computational Problems. . . . . . . . . . . . . . . . . . . . . . . 31.1.1 Model of computation . . . . . . . . . . . . . . . . . . . . 31.1.2 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.1.3 Probabilistic Computation . . . . . . . . . . . . . . . . . . 51.1.4 Reductions . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2 Quadratic Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.2.1 Quadratic Forms . . . . . . . . . . . . . . . . . . . . . . . 61.2.2 Representations . . . . . . . . . . . . . . . . . . . . . . . . 81.2.3 Properties of forms . . . . . . . . . . . . . . . . . . . . . . 91.2.4 Transformations . . . . . . . . . . . . . . . . . . . . . . . 91.2.5 Class structure over Important Rings. . . . . . . . . . . . 121.2.6 Classes and Genera. . . . . . . . . . . . . . . . . . . . . . 191.2.7 Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 211.3 Problems of Quadratic Forms . . . . . . . . . . . . . . . . . . . . 211.3.1 Rings . . . . . . . . . . . . . . . . . . . . . . . . .

Sujets

Informations

Publié par
Publié le 01 janvier 2008
Nombre de lectures 20
Langue English

Extrait

Computational Problems of
Quadratic Forms:
Complexity and Cryptographic
Perspectives
Dissertation
zur Erlangung des Doktorgrades
der Naturwissenschaften
vorgelegt beim Fachbereich Informatik und Mathematik
der Johann Wolfgang Goethe-Universitat¨
in Frankfurt am Main
von
Rupert Hartung
aus Oberwesel
Frankfurt am Main, 2007Contents
Introduction vii
Table of Notation xvii
I Quadratic Forms and their Applications 1
1 Preliminaries 3
1.1 Computational Problems. . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Model of computation . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.3 Probabilistic Computation . . . . . . . . . . . . . . . . . . 5
1.1.4 Reductions . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Quadratic Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.1 Quadratic Forms . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.2 Representations . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.3 Properties of forms . . . . . . . . . . . . . . . . . . . . . . 9
1.2.4 Transformations . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.5 Class structure over Important Rings. . . . . . . . . . . . 12
1.2.6 Classes and Genera. . . . . . . . . . . . . . . . . . . . . . 19
1.2.7 Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.3 Problems of Quadratic Forms . . . . . . . . . . . . . . . . . . . . 21
1.3.1 Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.3.2 Encoding of properties . . . . . . . . . . . . . . . . . . . . 23
1.3.3 Representation problem . . . . . . . . . . . . . . . . . . . 24
1.3.4 Transformation problem . . . . . . . . . . . . . . . . . . . 26
1.3.5 Primitiveness . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.3.6 Complexity assumption . . . . . . . . . . . . . . . . . . . 27
2 Cryptography 29
2.1 Randomization and Key Generation . . . . . . . . . . . . . . . . 29
2.2 An identification scheme . . . . . . . . . . . . . . . . . . . . . . . 31
2.2.1 Specification of the Protocol. . . . . . . . . . . . . . . . . 31
2.2.2 Proof of knowledge . . . . . . . . . . . . . . . . . . . . . . 32
2.2.3 Zero-knowledge property. . . . . . . . . . . . . . . . . . . 34
2.3 Long Challenges and Signatures . . . . . . . . . . . . . . . . . . . 35
2.3.1 Specification of the protocol . . . . . . . . . . . . . . . . . 35
2.3.2 Application to digital signatures . . . . . . . . . . . . . . 35
iiiiv CONTENTS
2.3.3 Security against Fraudulent Provers . . . . . . . . . . . . 36
2.3.4 Security Fraudulent Verifiers . . . . . . . . . . . . 37
3 Localization and Decisional Complexity 39
3.1 Decision Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2 Forms over Finite Fields . . . . . . . . . . . . . . . . . . . . . . . 45
3.3 Forms over Local Rings . . . . . . . . . . . . . . . . . . . . . . . 47
4 Algorithms for Primes, Classes, and Genera 53
4.1 Algorithmic Prime Selection . . . . . . . . . . . . . . . . . . . . . 53
4.2 Construction of Genera . . . . . . . . . . . . . . . . . . . . . . . 59
4.2.1 Local representations. . . . . . . . . . . . . . . . . . . . . 59
4.2.2 Composition of square classes . . . . . . . . . . . . . . . . 62
4.2.3 Approximation . . . . . . . . . . . . . . . . . . . . . . . . 65
4.2.4 Main algorithm . . . . . . . . . . . . . . . . . . . . . . . . 68
II Classification with Respect to Complexity 73
5 Cases of Low Complexity 75
5.1 Singular Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.2 Reducible Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5.3 Definite Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.4 Isotropic Ternary Forms . . . . . . . . . . . . . . . . . . . . . . . 83
6 The Impact of the Base Ring on Complexity 87
6.1 Forms over the Rational Numbers . . . . . . . . . . . . . . . . . 87
6.2 Rings of Formal Power Series . . . . . . . . . . . . . . . . . . . . 90
6.2.1 Introduction and summary of results . . . . . . . . . . . . 90
6.2.2 Upper bounds. . . . . . . . . . . . . . . . . . . . . . . . . 91
6.2.3 Lower bounds for representations . . . . . . . . . . . . . . 93
6.3 Polynomial Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
7 Complexity for Varying Dimension 101
7.1 Dimension Shift to Ternary and Quaternary Forms . . . . . . . . 101
7.1.1 Introduction and result . . . . . . . . . . . . . . . . . . . 101
7.1.2 Direct sum decomposition of isotropic forms . . . . . . . . 102
7.1.3 Conclusion of the proof . . . . . . . . . . . . . . . . . . . 103
7.2 Binary Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
III Hardness and Interrelationship 107
8 Comparison with Factorization 109
8.1 Introduction and Result . . . . . . . . . . . . . . . . . . . . . . . 109
8.2 Spinor Norm and an Equivalence Criterion . . . . . . . . . . . . 110
8.3 Conclusion of the Proof . . . . . . . . . . . . . . . . . . . . . . . 112
8.4 Problem Modification . . . . . . . . . . . . . . . . . . . . . . . . 114CONTENTS v
9 NP-Hardness Results 115
9.1 Introduction and Summary of Results . . . . . . . . . . . . . . . 115
9.2 From SAT to Squares . . . . . . . . . . . . . . . . . . . . . . . . 121
9.3 The Special Cohen-Lenstra Heuristics . . . . . . . . . . . . . . . 127
9.4 The Image of Binary Forms . . . . . . . . . . . . . . . . . . . . . 130
9.5 The One-Class Condition . . . . . . . . . . . . . . . . . . . . . . 131
9.6 Orbits of Representations . . . . . . . . . . . . . . . . . . . . . . 132
9.7 Conclusion of the Proofs . . . . . . . . . . . . . . . . . . . . . . . 140
10 Relationship between the Problems 145
10.1 Result and Proof Outline . . . . . . . . . . . . . . . . . . . . . . 145
10.2 Construction of a Represented Form . . . . . . . . . . . . . . . . 147
10.3ction of an Equivalent Form . . . . . . . . . . . . . . . . 149
10.4 Reduction to Representations . . . . . . . . . . . . . . . . . . . . 151vi CONTENTSIntroduction
I am the very model of a modern Major-General,
I’ve information vegetable, animal, and mineral,
[...]
I’m very well acquainted, too, with matters mathematical,
I understand equations, both the simple and quadratical
[...].
(W. S. Gilbert, from: The Pirates of Penzance)
At least at first sight, quadratic equations seem to be much more difficult
than linear problems. This is what W. S. Gilbert may have had in mind when
writing this verse for this self-assure officer; or so the juxtaposition between
‘simple’and‘quadratical’equationssuggests. Roughlyspeaking, theaimofthis
dissertation is to answer the question, how difficult the latter are.
Background. Quadratic forms play an important role in number theory as
well as in several related areas. They already aroused the interest of Fermat,
Euler, Lagrange, and Legendre (see [Wei84], [Dic34b, ch. VI–X, XII, XIII],
[Dic34c,ch. I–XI]).Perhapsoneoftheirmainappealsistheirseemingsimplicity:
Being merely a slight abstraction from quadratic equations, quadratic forms are
easy to write down and ask questions about. More specifically, quadratic forms
are just one step beyond linear ones, and the theory of linear forms (i.e. linear
algebra by any other name) is thouroughly explored and easily understandible
– at least from today’s perspective. Curiously, this picture changes radically
when turning to exponent two. Another reason to study quadratic forms lies in
the fact that binary forms bear the structural information on quadratic number
fields, but in an easier accessible way.
The mathematical literature produced by the mid of the 19th century has
notonlycontributedsingnificantlytotheknowledgeaboutquadraticforms, but
also raised new questions. Especially Gauß’ work Disquisitiones Arithmeticae
[Gau89] enjoyed immense popularity among the mathematicians of his and the
following generations: Not only did it mean a leap ahead in the theory, but it
has also shaped much of the area today known as algebraic number theory.
Probably, the flourishing of this reasearch area inspired Hilbert to discuss it
in his famous speech at the International Congress of Mathematicians in Paris
in 1900. The eleventh item on his famous list of mathematical problems for the
20th century calls for a theory of quadratic forms over algebraic number fields.
viiviii INTRODUCTION
The efforts initiated by Hilbert’s speech have given rise to the arithmetic
theory of quadratic forms, which explores quadratic forms over local and global
fields and their respective rings of integers. Many question could be settled in
this area. The honor of having accomplished Hilbert’s task is usually granted
to H. Hasse for the famous Hasse Principle (see [Has24]).
It is this branch of the theory which will prove the most significant here.
Some central results are discussed in Sect. 1.2.5.
Despite these enormous advances, algorithmic questions have hardly ever
come into focus. This is even more suprising in view of the fact that most of
the theory starts with two classical decision problems:
(A) Given two quadratic forms, are they equivalent?
(B) Given a quadratic form and a scalar, can the scalar be repre-
sented by the form?
More than a century of research has provided us with comprehensive crite-
ria for these questions. However, the algorithmic nature of suc

  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents