有限自動機及在密碼學中的應用

ForewordbyArtoSalomaa.
Preface
1.　Introduction
1.1　Preliminaries
1.1.1　RelationsandFunctions
1.1.2　Graphs
1.2　DefinitionsofFiniteAutomata
1.2.1　FiniteAutomataasTransducers
1.2.2　SpecialFiniteAutomata
1.2.3　CompoundFiniteAutomata
1.2.4　FiniteAutomataasRecognizers
1.3　LinearFiniteAutomata
1.4　ConceptsonInvertibility
1.5　ErrorPropagationandFeedforwardInvertibility
1.6　LabelledTreesasStatesofFiniteAutomata
2.　MutualInvertibilityandSearch
2.1　MinimalOutputWeightandInputSet
2.2　MutualInvertibilityofFiniteAutomata
2.3　FindInputbySearch
2.3.1　OnOutputSetandInputTree
2.3.2　ExhaustingSearch
2.3.3　StochasticSearch
3.　RaRbTransformationMethod
3.1　SufficientConditionsandInversion
3.2　GenerationofFiniteAutomatawithInvertibility
3.3　InvertibilityofQuasi-LinearFiniteAutomata
3.3.1　DecisionCriteria
3.3.2　StructureProblem
4.　RelationsBetweenTransformations
4.1　RelationsBetweenRaRbTransformations
4.2　CompositionofRaRbTransformations
4.3　ReducedEchelonMatrix
4.4　CanonicalDiagonalMatrixPolynomial
4.4.1　RaRbTransformationsoverMatrixPolynomial
4.4.2　RelationsBetweenRaRbTransformationandCanonicalDiagonalForm
4.4.3　RelationsofRight-Parts
4.4.4　ExistenceofTerminatingRaRbTransformationSequence
5.　StructureofFeedforwardInverses
5.1　ADecisionCriterion..
5.2　DelayFree
5.3　OneStepDelay
5.4　TwoStepDelay
6.　SomeTopicsonStructureProblem
6.1　SomeVariantsofFiniteAutomata
6.1.1　PartialFiniteAutomata
6.1.2　NondeterministicFiniteAutomata
6.2　InversesofaFiniteAutomaton
6.3　OriginalInversesofaFiniteAutomaton
6.4　WeakInversesofaFiniteAutomaton
6.5　OriginalWeakInversesofaFiniteAutomaton
6.6　WeakInverseswithBoundedErrorPropagationofaFiniteAutomaton
7.　LinearAutonomousFiniteAutomata
7.1　BinomialCoefficient
7.2　RootRepresentation
7.3　TranslationandPeriod
7.3.1　ShiftRegisters
7.3.2　FiniteAutomata
7.4　Linearization
7.5　Decimation
8.　OneKeyCryptosystemsandLatinArrays
8.1　CanonicalFormforFiniteAutomatonOneKeyCryptosystems
8.2　LatinArrays
8.2.1　Definitions
8.2.2　On(n，k，r)-LatinArrays
8.2.3　Invariant
8.2.4　AutotopismGroup
8.2.5　TheCasen=2，3
8.2.6　TheCasen=4，k≤4
8.3　LinearlyIndependentLatinArrays
8.3.1　LatinArraysofInvertibleFunctions
8.3.2　GenerationofLinearlyIndependentPermutations
9.　FiniteAutomatonPublicKeyCryptosystems
9.1　TheoreticalFundamentals
9.2　BasicAlgorithm
9.3　AnExampleofFAPKC
9.4　OnWeakKeys
9.4.1　LinearRaRbTransformationTest
9.4.2　OnAttackbyReducedEchelonMatrix
9.4.3　OnAttackbyCanonicalDiagonalMatrixPolynomial
9.5　Security
9.5.1　InversionbyaGeneralMethod
9.5.2　InversionbyDecomposingFiniteAutomata
9.5.3　ChosenPlaintextAttack
9.5.4　ExhaustingSearchandStochasticSearch
9.6　GeneralizedAlgorithms
9.6.1　SomeTheoreticalResults
9.6.2　TwoAlgorithms
References
Index