BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Arne Winterhof

Arne Winterhof appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.NTmath.COInformation Theorymath.ITCryptography and Securitymath.HOmath.NA

Catalog footprint

What is connected

15works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

15 published item(s)

preprint2021arXiv

On the distribution of the Rudin-Shapiro function for finite fields

Let $q=p^r$ be the power of a prime $p$ and $(β_1,\ldots ,β_r)$ be an ordered basis of $\mathbb{F}_q$ over $\mathbb{F}_p$. For $$ ξ=\sum\limits_{j=1}^r x_jβ_j\in \mathbb{F}_q \quad \mbox{with digits }x_j\in\mathbb{F}_p, $$ we define the Rudin-Shapiro function $R$ on $\mathbb{F}_q$ by $$ R(ξ)=\sum\limits_{i=1}^{r-1} x_ix_{i+1}, \quad ξ\in \mathbb{F}_q. $$ For a non-constant polynomial $f(X)\in \mathbb{F}_q[X]$ and $c\in \mathbb{F}_p$ we study the number of solutions $ξ\in \mathbb{F}_q$ of $R(f(ξ))=c$. If the degree $d$ of $f(X)$ is fixed, $r\ge 6$ and $p\rightarrow \infty$, the number of solutions is asymptotically $p^{r-1}$ for any $c$. The proof is based on the Hooley-Katz Theorem.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Note on the Cross-Correlation of Costas Permutations

We build on the work of Drakakis et al. (2011) on the maximal cross-correlation of the families of Welch and Golomb Costas permutations. In particular, we settle some of their conjectures. More precisely, we prove two results. First, for a prime $p\ge 5$, the maximal cross-correlation of the family of the $φ(p-1)$ different Welch Costas permutations of $\{1,\ldots,p-1\}$ is $(p-1)/t$, where $t$ is the smallest prime divisor of $(p-1)/2$ if $p$ is not a safe prime and at most $1+p^{1/2}$ otherwise. Here $φ$ denotes Euler's totient function and a prime $p$ is a safe prime if $(p-1)/2$ is also prime. Second, for a prime power $q\ge 4$ the maximal cross-correlation of a subfamily of Golomb Costas permutations of $\{1,\ldots,q-2\}$ is $(q-1)/t-1$ if $t$ is the smallest prime divisor of $(q-1)/2$ if $q$ is odd and of $q-1$ if $q$ is even provided that $(q-1)/2$ and $q-1$ are not prime, and at most $1+q^{1/2}$ otherwise. Note that we consider a smaller family than Drakakis et al. Our family is of size $φ(q-1)$ whereas there are $φ(q-1)^2$ different Golomb Costas permutations. The maximal cross-correlation of the larger family given in the tables of Drakakis et al. is larger than our bound (for the smaller family) for some $q$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Binary sequences derived from differences of consecutive quadratic residues

For a prime $p\ge 5$ let $q_0,q_1,\ldots,q_{(p-3)/2}$ be the quadratic residues modulo $p$ in increasing order. We study two $(p-3)/2$-periodic binary sequences $(d_n)$ and $(t_n)$ defined by $d_n=q_n+q_{n+1}\bmod 2$ and $t_n=1$ if $q_{n+1}=q_n+1$ and $t_n=0$ otherwise, $n=0,1,\ldots,(p-5)/2$. For both sequences we find some sufficient conditions for attaining the maximal linear complexity $(p-3)/2$. Studying the linear complexity of $(d_n)$ was motivated by heuristics of Caragiu et al. However, $(d_n)$ is not balanced and we show that a period of $(d_n)$ contains about $1/3$ zeros and $2/3$ ones if $p$ is sufficiently large. In contrast, $(t_n)$ is not only essentially balanced but also all longer patterns of length $s$ appear essentially equally often in the vector sequence $(t_n,t_{n+1},\ldots,t_{n+s-1})$, $n=0,1,\ldots,(p-5)/2$, for any fixed $s$ and sufficiently large $p$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The Spherical Kakeya Problem in Finite Fields

We study subsets of the $n$-dimensional vector space over the finite field $\mathbb{F}_q$, for odd $q$, which contain either a sphere for each radius or a sphere for each first coordinate of the center. We call such sets radii spherical Kakeya sets and center spherical Kakeya sets, respectively. For $n\ge 4$ we prove a general lower bound on the size of any set containing $q-1$ different spheres which applies to both kinds of spherical Kakeya sets. We provide constructions which meet the main terms of this lower bound. We also give a construction showing that we cannot get a lower bound of order of magnitude~$q^n$ if we take lower dimensional objects such as circles in $\mathbb{F}_q^3$ instead of spheres, showing that there are significant differences to the line Kakeya problem. Finally, we study the case of dimension $n=1$ which is different and equivalent to the study of sum and difference sets that cover $\mathbb{F}_q$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Carlitz Rank and Index of Permutation Polynomials

Carlitz rank and index are two important measures for the complexity of a permutation polynomial $f(x)$ over the finite field $\F_q$. In particular, for cryptographic applications we need both, a high Carlitz rank and a high index. In this article we study the relationship between Carlitz rank $Crk(f)$ and index $Ind(f)$. More precisely, if the permutation polynomial is neither close to a polynomial of the form $ax$ nor a rational function of the form $ax^{-1}$, then we show that $Crk(f)>q- \max\{3 Ind(f),(3q)^{1/2}\}$. Moreover we show that the permutation polynomial which represents the discrete logarithm guarantees both a large index and a large Carlitz rank.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Complete mappings and Carlitz rank

The well-known Chowla and Zassenhaus conjecture, proven by Cohen in 1990, states that for any $d\ge 2$ and any prime $p>(d^2-3d+4)^2$ there is no complete mapping polynomial in $\mathbb{F}_{p}[x]$ of degree $d$. For arbitrary finite fields $\mathbb{F}_{q}$, we give a similar result in terms of the Carlitz rank of a permutation polynomial rather than its degree. We prove that if $n<\lfloor q/2\rfloor$, then there is no complete mapping in $\mathbb{F}_{q}[x]$ of Carlitz rank $n$ of small linearity. We also determine how far permutation polynomials $f$ of Carlitz rank $n<\lfloor q/2\rfloor$ are from being complete, by studying value sets of $f+x.$ We provide examples of complete mappings if $n=\lfloor q/2\rfloor$, which shows that the above bound cannot be improved in general.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Expansion complexity and linear complexity of sequences over finite fields

The linear complexity is a measure for the unpredictability of a sequence over a finite field and thus for its suitability in cryptography. In 2012, Diem introduced a new figure of merit for cryptographic sequences called expansion complexity. We study the relationship between linear complexity and expansion complexity. In particular, we show that for purely periodic sequences both figures of merit provide essentially the same quality test for a sufficiently long part of the sequence. However, if we study shorter parts of the period or nonperiodic sequences, then we can show, roughly speaking, that the expansion complexity provides a stronger test. We demonstrate this by analyzing a sequence of binomial coefficients modulo $p$. Finally, we establish a probabilistic result on the behavior of the expansion complexity of random sequences over a finite field.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Digital inversive vectors can achieve strong polynomial tractability for the weighted star discrepancy and for multivariate integration

We study high-dimensional numerical integration in the worst-case setting. The subject of tractability is concerned with the dependence of the worst-case integration error on the dimension. Roughly speaking, an integration problem is tractable if the worst-case error does not explode exponentially with the dimension. Many classical problems are known to be intractable. However, sometimes tractability can be shown. Often such proofs are based on randomly selected integration nodes. Of course, in applications true random numbers are not available and hence one mimics them with pseudorandom number generators. This motivates us to propose the use of pseudorandom vectors as underlying integration nodes in order to achieve tractability. In particular, we consider digital inverse vectors and present two examples of problems, the weighted star discrepancy and integration of Hölder continuous, absolute convergent Fourier- and cosine series, where the proposed method is successful.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the linear complexity profile of some sequences derived from elliptic curves

For a given elliptic curve $\mathbf{E}$ over a finite field of odd characteristic and a rational function $f$ on $\mathbf{E}$ we first study the linear complexity profiles of the sequences $f(nG)$, $n=1,2,\dots$ which complements earlier results of Hess and Shparlinski. We use Edwards coordinates to be able to deal with many $f$ where Hess and Shparlinski's result does not apply. Moreover, we study the linear complexities of the (generalized) elliptic curve power generators $f(e^nG)$, $n=1,2,\dots$. We present large families of functions $f$ such that the linear complexity profiles of these sequences are large.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Family complexity and cross-correlation measure for families of binary sequences

We study the relationship between two measures of pseudorandomness for families of binary sequences: family complexity and cross-correlation measure introduced by Ahlswede et al.\ in 2003 and recently by Gyarmati et al., respectively. More precisely, we estimate the family complexity of a family $(e_{i,1},\ldots,e_{i,N})\in \{-1,+1\}^N$, $i=1,\ldots,F$, of binary sequences of length $N$ in terms of the cross-correlation measure of its dual family $(e_{1,n},\ldots,e_{F,n})\in \{-1,+1\}^F$, $n=1,\ldots,N$. We apply this result to the family of sequences of Legendre symbols with irreducible quadratic polynomials modulo $p$ with middle coefficient $0$, that is, $e_{i,n}=\left(\frac{n^2-bi^2}{p}\right)_{n=1}^{(p-1)/2}$ for $i=1,\ldots,(p-1)/2$, where $b$ is a quadratic nonresidue modulo $p$, showing that this family as well as its dual family have both a large family complexity and a small cross-correlation measure up to a rather large order.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Non-Existence of Some Nearly Perfect Sequences, Near Butson-Hadamard Matrices, and Near Conference Matrices

In this paper we study the non-existence problem of (nearly) perfect (almost) $m$-ary sequences via their connection to (near) Butson-Hadamard (BH) matrices and (near) conference matrices. Firstly, we apply a result on vanishing sums of roots of unity and a result of Brock on the unsolvability of certain equations over a cyclotomic number field to derive non-existence results for near BH matrices and near conference matrices. Secondly, we refine the idea of Brock in the case of cyclotomic number fields whose ring of integers is not a principal ideal domains and get many new non-existence results.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Polynomial quotients: Interpolation, value sets and Waring's problem

For an odd prime $p$ and an integer $w\ge 1$, polynomial quotients $q_{p,w}(u)$ are defined by $$ q_{p,w}(u)\equiv \frac{u^w-u^{wp}}{p} \bmod p ~~ \mathrm{with}~~ 0 \le q_{p,w}(u) \le p-1, ~~u\ge 0, $$ which are generalizations of Fermat quotients $q_{p,p-1}(u)$. First, we estimate the number of elements $1\le u<N\le p$ for which $f(u)\equiv q_{p,w}(u) \bmod p$ for a given polynomial $f(x)$ over the finite field $\mathbb{F}_p$. In particular, for the case $f(x)=x$ we get bounds on the number of fixed points of polynomial quotients. Second, before we study the problem of estimating the smallest number (called the Waring number) of summands needed to express each element of $\mathbb{F}_p$ as sum of values of polynomial quotients, we prove some lower bounds on the size of their value sets, and then we apply these lower bounds to prove some bounds on the Waring number using results from bounds on additive character sums and additive number theory.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Covering sets for limited-magnitude errors

For a set $\cM=\{-μ,-μ+1,\ldots, λ\}\setminus\{0\}$ with non-negative integers $λ,μ<q$ not both 0, a subset $\cS$ of the residue class ring $\Z_q$ modulo an integer $q\ge 1$ is called a $(λ,μ;q)$-\emph{covering set} if $$ \cM \cS=\{ms \bmod q : m\in \cM,\ s\in \cS\}=\Z_q. $$ Small covering sets play an important role in codes correcting limited-magnitude errors. We give an explicit construction of a $(λ,μ;q)$-covering set $\cS$ which is of the size $q^{1 + o(1)}\max\{λ,μ\}^{-1/2}$ for almost all integers $q\ge 1$ and of optimal size $p\max\{λ,μ\}^{-1}$ if $q=p$ is prime. Furthermore, using a bound on the fourth moment of character sums of Cochrane and Shi we prove the bound $$ω_{λ,μ}(q)\le q^{1+o(1)}\max\{λ,μ\}^{-1/2},$$ for any integer $q\ge 1$, however the proof of this bound is not constructive.

0 citations0 reviewsNo code linkedOpen access