2017/12/31 by Federico Amadio Guidi, Sofia Lindqvist, Giacomo Micheli
Computer Science · Mathematics · #Affine transformation #Algorithm #Chaos-based Image/Signal Encryption #Coding theory and cryptography #Combinatorics #Cryptography and Residue Arithmetic #Discrete mathematics #Field (mathematics) #Finite field #Generator (circuit theory) #Integer (computer science) #Mathematics #Orbit (dynamics) #Pseudorandom number generator #Pseudorandomness #Pure mathematics #math.NT #msc:11B37 #msc:11K38 #msc:11K45 #msc:11T06 #msc:11T23 #msc:15B33 #msc:65C10
paper · pdf · doi:10.1090/mcom/3400
To appear in Mathematics of Computation
openalex created_date 2018/05/07 · arxiv created 2018/09/10 · openalex publication_date 2018/09/19 · arxiv updated 2019/02/13 · openalex updated_date 2026/08/05
Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be a positive integer. In this paper we provide a general theory to produce full orbit sequences in the affine <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -dimensional space over a finite field. For <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n equals 1"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">n=1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> our construction covers the case of the Inversive Congruential Generators (ICG). In addition, for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n greater-than 1"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>></mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">n>1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> we show that the sequences produced using our construction are easier to compute than ICG sequences. Furthermore, we prove that they have the same discrepancy bounds as the ones constructed using the ICG.