Source author record

Michele Elia

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.NT Information Theory math.IT Cryptography and Security Data Structures and Algorithms math.AC

Catalog footprint

Research overview

14works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

On the Fiber Characters of $\mathbb F^*_{p^m}$ and related Polynomial Algebras

Let $p$ be a prime, $m$ be a positive integer ( $m \geq 1$ , and $m \geq 2$ if $p=2$ ), and $χ_n$ be a multiplicative complex character on $\mathbb F^*_{p^m}$ with order $n| (p^m-1)$ . We show that a partition $\mathcal A_1 \cup \mathcal A_2 \cup \cdots \cup \mathcal A_n$ of $\mathbb F^{*}_{p^m}$ is the partition by fibers of $χ_n$ if and only if these fibers % $\mathcal A_i$ satisfy certain additive properties. This is equivalent to show that the set of multivariate characteristic polynomials of these fibers, completed with the constant polynomial $1$ , is the basis of a $(n+1)$ -dimensional commutative algebra with identity in the ring $\mathbb Q[x_1,\ldots,x_n]/\langle x_1^p-1, \ldots, x_n^p-1 \rangle$ .

preprint2020arXiv

Point-groups over singular cubics

In this paper, we highlight that the point group structure of elliptic curves over finite or infinite fields, may be also observed on singular cubics with a quadratic component. Starting from this, we are able to introduce in a very general way a group's structure over any kind of conics. In the case of conics over finite fields, we see that the point group is cyclic and lies on the quadric; the straight line component plays a role which may be not explicitly visible in the algebraic description of point composition, but it is indispensable in the geometric description. Moreover, some applications to cryptography are described, considering convenient parametrizations of the conics. Finally, we perform an evaluation of the complexity of the operations involved in the parametric groups and consequently in the cryptographic applications.

preprint2016arXiv

Involutions, Trace Maps, and Pseudorandom Numbers

Interesting properties of the partitions of a finite field $\mathbb F_q$ induced by the combination of involutions and trace maps are studied. The special features of involutions of the form $\frac{u}{z}$ , $u$ being a fixed element of $\mathbb F_q$ , are exploited to generate pseudorandom numbers, the randomness resting on the uniform distribution of the images of zero-trace elements among the sets of non-zero trace elements of $\mathbb F_q$ .

preprint2016arXiv

On the Representation of Primes by Binary Quadratic Forms, and Elliptic Curves

It is shown that, under some mild technical conditions, representations of prime numbers by binary quadratic forms can be computed in polynomial complexity by exploiting Schoof's algorithm, which counts the number of $\mathbb F_q$ -points of an elliptic curve over a finite field $\mathbb F_q$ . Further, a method is described which computes representations of primes from reduced quadratic forms by means of the integral roots of polynomials over $\mathbb Z$ . Lastly, some progress is made on the still-unsettled general problem of deciding which primes are represented by which classes of quadratic forms of given discriminant.

preprint2013arXiv

The Rabin cryptosystem revisited

The Rabin public-key cryptosystem is revisited with a focus on the problem of identifying the encrypted message unambiguously for any pair of primes. In particular, a deterministic scheme using quartic reciprocity is described that works for primes congruent 5 modulo 8, a case that was still open. Both theoretical and practical solutions are presented. The Rabin signature is also reconsidered and a deterministic padding mechanism is proposed.

preprint2011arXiv

Additive decompositions induced by multiplicative characters over finite fields

In 1952, Perron showed that quadratic residues in a field of prime order satisfy certain ad- ditive properties. This result has been generalized in different directions, and our contribution is to provide a further generalization concerning multiplicative quadratic and cubic characters over any finite field. In particular, recalling that a character partitions the multiplicative group of the field into cosets with respect to its kernel, we will derive the number of representations of an element as a sum of two elements belonging to two given cosets. These numbers are then related to the equations satisfied by the polynomial characteristic functions of the cosets. Further, we show a connection, a quasi-duality, with the problem of determining how many elements can be added to each element of a subset of a coset in such a way as to obtain elements still belonging to a subset of a coset.

preprint2011arXiv

Complexity of multivariate polynomial evaluation

We describe a method to evaluate multivariate polynomials over a finite field and discuss its multiplicative complexity.

preprint2011arXiv

Efficient evaluation of polynomials over finite fields

A method is described which allows to evaluate efficiently a polynomial in a (possibly trivial) extension of the finite field of its coefficients. Its complexity is shown to be lower than that of standard techniques when the degree of the polynomial is large with respect to the base field. Applications to the syndrome computation in the decoding of cyclic codes, Reed-Solomon codes in particular, are highlighted.

preprint2011arXiv

Gauss sums of cubic characters over $GF(p^r)$ , $p$ odd

An elementary approach is shown which derives the values of the Gauss sums over $\mathbb F_{p^r}$ , $p$ odd, of a cubic character without using Davenport-Hasse's theorem. New links between Gauss sums over different field extensions are shown in terms of factorizations of the Gauss sums themselves, which are then rivisited in terms of prime ideal decompositions. Interestingly, one of these results gives a representation of primes $p$ of the form $6k+1$ by a binary quadratic form in integers of a subfield of the cyclotomic field of the $p$ -th roots of unity.

preprint2011arXiv

Gauss Sums of the Cubic Character over $GF(2^m)$ : an elementary derivation

An elementary approach is shown which derives the value of the Gauss sum of a cubic character over a finite field $\mathbb F_{2^s}$ without using Davenport-Hasse's theorem (namely, if $s$ is odd the Gauss sum is -1, and if $s$ is even its value is $-(-2)^{s/2}$ ).

preprint2011arXiv

Improvements on Cantor-Zassenhaus Factorization Algorithm

After revisiting Cantor-Zassenhaus polynomial factorization algorithm, we describe a new simplified version of it, which requires less computational cost. Moreover we show that it is able to find a factor of a fully splitting polynomial of degree $t$ over $\mathbb F_{2^m}$ with $O(\frac{2^m}{3^{t}})$ attempts and over $\mathbb F_{p^m}$ for odd $p$ with $O(\frac{p^m}{2^{t}})$ attempts.

preprint2011arXiv

On the Decoding Complexity of Cyclic Codes Up to the BCH Bound

The standard algebraic decoding algorithm of cyclic codes $[n,k,d]$ up to the BCH bound $t$ is very efficient and practical for relatively small $n$ while it becomes unpractical for large $n$ as its computational complexity is $O(nt)$ . Aim of this paper is to show how to make this algebraic decoding computationally more efficient: in the case of binary codes, for example, the complexity of the syndrome computation drops from $O(nt)$ to $O(t\sqrt n)$ , and that of the error location from $O(nt)$ to at most $\max \{O(t\sqrt n), O(t^2\log(t)\log(n))\}$ .

preprint2011arXiv

On the Rabin signature

Some Rabin signature schemes may be exposed to forgery; several variants are here described to counter this vulnerability. Blind Rabin signatures are also discussed.

preprint2011arXiv

Polynomial evaluation over finite fields: new algorithms and complexity bounds

An efficient evaluation method is described for polynomials in finite fields. Its complexity is shown to be lower than that of standard techniques when the degree of the polynomial is large enough. Applications to the syndrome computation in the decoding of Reed-Solomon codes are highlighted.

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.

Michele Elia

Research overview

Is this your work?

14 publications

On the Fiber Characters of $\mathbb F^*_{p^m}$ and related Polynomial Algebras

Point-groups over singular cubics

Involutions, Trace Maps, and Pseudorandom Numbers

On the Representation of Primes by Binary Quadratic Forms, and Elliptic Curves

The Rabin cryptosystem revisited

Additive decompositions induced by multiplicative characters over finite fields

Complexity of multivariate polynomial evaluation

Efficient evaluation of polynomials over finite fields

Gauss sums of cubic characters over $GF(p^r)$ , $p$ odd

Gauss Sums of the Cubic Character over $GF(2^m)$ : an elementary derivation

Improvements on Cantor-Zassenhaus Factorization Algorithm

On the Decoding Complexity of Cyclic Codes Up to the BCH Bound

On the Rabin signature

Polynomial evaluation over finite fields: new algorithms and complexity bounds

See the researcher in context

Building this map preview

Michele Elia

Research overview

Is this your work?

14 publications

On the Fiber Characters of Fpm∗\mathbb F^*_{p^m}Fpm∗​ and related Polynomial Algebras

Point-groups over singular cubics

Involutions, Trace Maps, and Pseudorandom Numbers

On the Representation of Primes by Binary Quadratic Forms, and Elliptic Curves

The Rabin cryptosystem revisited

Additive decompositions induced by multiplicative characters over finite fields

Complexity of multivariate polynomial evaluation

Efficient evaluation of polynomials over finite fields

Gauss sums of cubic characters over GF(pr)GF(p^r)GF(pr), ppp odd

Gauss Sums of the Cubic Character over GF(2m)GF(2^m)GF(2m): an elementary derivation

Improvements on Cantor-Zassenhaus Factorization Algorithm

On the Decoding Complexity of Cyclic Codes Up to the BCH Bound

On the Rabin signature

Polynomial evaluation over finite fields: new algorithms and complexity bounds

See the researcher in context

Building this map preview

On the Fiber Characters of $\mathbb F^*_{p^m}$ and related Polynomial Algebras

Gauss sums of cubic characters over $GF(p^r)$ , $p$ odd

Gauss Sums of the Cubic Character over $GF(2^m)$ : an elementary derivation