Publications associées à Factoring multivariate integral polynomials

Polynomials Vanishing On Cartesian Products: The Elekes-Szabo Theorem Revisited

Let F 2 C[x; y; z] be a constant-degree polynomial, and let A; B; C subset of C be finite sets of size n. We show that F vanishes on at most O(n(11/6))points of the Cartesian product A X B X C, unless F has a special group-related form. This improves a the ...

Duke Univ Press2016

ON THE DISCRETE LOGARITHM PROBLEM IN FINITE FIELDS OF FIXED CHARACTERISTIC

Robert Granger, Thorsten Kleinjung, Jens Markus Zumbrägel

For~

q

a prime power, the discrete logarithm problem (DLP) in~

\F_{q}

consists in finding, for any

g \in \mathbb{F}_{q}^{\times}

and

h \in \langle g \rangle

, an integer~

x

such that

g^x = h

. We present an algorithm for computing discrete logarithm ...

2016

Multivariate Markov-type and Nikolskii-type inequalities for polynomials associated with downward closed multi-index sets

Giovanni Migliorati

We present novel Markov-type and Nikolskii-type inequalities for multivariate polynomials associated with arbitrary downward closed multi-index sets in any dimension. Moreover, we show how the constant of these inequalities changes, when the polynomial is ...

Elsevier2015

Isometries of quadratic spaces

Eva Bayer Fluckiger

Let k be a global field of characteristic not 2, and let f is an element of k[X] be an irreducible polynomial. We show that a non-degenerate quadratic space has an isometry with minimal polynomial f if and only if such an isometry exists over all the compl ...

European Mathematical Soc2015

On the discrete logarithm problem in finite fields of fixed characteristic

Robert Granger, Thorsten Kleinjung, Jens Markus Zumbrägel

For

q

a prime power, the discrete logarithm problem (DLP) in

\mathbb{F}_q

consists in finding, for any

g \in \mathbb{F}_{q}^{\times}

and

h \in \langle g \rangle

, an integer

x

such that

g^x = h

. We present an algorithm for computing discrete log ...

2015

Polynomial-Time Computation Of Homotopy Groups And Postnikov Systems In Fixed Dimension

For several computational problems in homotopy theory, we obtain algorithms with running time polynomial in the input size. In particular, for every fixed k >= 2, there is a polynomial-time algorithm that, for a 1-connected topological space X given as a f ...

Siam Publications2014

Analysis of Discrete L2 Projection on Polynomial Spaces with Random Evaluations

Fabio Nobile, Giovanni Migliorati, Erik Gustaf Bogislaw Von Schwerin

We analyse the problem of approximating a multivariate function by discrete least-squares projection on a polynomial space starting from random, noise-free observations. An area of possible application of such technique is Uncertainty Quantification (UQ) f ...

2014

On Sub-determinants and the Diameter of Polyhedra

Friedrich Eisenbrand, Martin Niemeier, Marco Di Summa, Nicolas Bonifas

We derive a new upper bound on the diameter of a polyhedron , where . The bound is polynomial in and the largest absolute value of a sub-determinant of , denoted by . More precisely, we show that the diameter of is bounded by . If is bounded, then we show ...

Springer2014

Algebraic algorithms for network information flow

Javad Ebrahimi Boroojeni

Ahlswede et al. in the seminal paper [1] have shown that in data transfer over networks, processing the data at the nodes can significantly improve the throughput. As proved by Li et al. in [2], even with a simple type of operation, namely linear operation ...

EPFL2013

TCHo: A Code-Based Cryptosystem

Serge Vaudenay, Alexandre Raphaël Duc

TCHo is a public-key cryptosystem based on the hardness of finding a multiple polynomial with low weight and on the hardness of distinguishing between the output of an LFSR with noise and some random source. An early version was proposed in 2006 by Finiasz ...

Springer Berlin Heidelberg2013

Factoring multivariate integral polynomials

Graph Chatbot

Chattez avec Graph Search

Polynomials Vanishing On Cartesian Products: The Elekes-Szabo Theorem Revisited

ON THE DISCRETE LOGARITHM PROBLEM IN FINITE FIELDS OF FIXED CHARACTERISTIC

Multivariate Markov-type and Nikolskii-type inequalities for polynomials associated with downward closed multi-index sets

Isometries of quadratic spaces

On the discrete logarithm problem in finite fields of fixed characteristic

Polynomial-Time Computation Of Homotopy Groups And Postnikov Systems In Fixed Dimension

Analysis of Discrete L2 Projection on Polynomial Spaces with Random Evaluations

On Sub-determinants and the Diameter of Polyhedra

Algebraic algorithms for network information flow

TCHo: A Code-Based Cryptosystem

ON THE DISCRETE LOGARITHM PROBLEM IN FINITE FIELDS OF FIXED CHARACTERISTIC

On the discrete logarithm problem in finite fields of fixed characteristic

Multivariate Markov-type and Nikolskii-type inequalities for polynomials associated with downward closed multi-index sets

Algebraic algorithms for network information flow

Polynomial-Time Computation Of Homotopy Groups And Postnikov Systems In Fixed Dimension

On Sub-determinants and the Diameter of Polyhedra

TCHo: A Code-Based Cryptosystem

Polynomials Vanishing On Cartesian Products: The Elekes-Szabo Theorem Revisited

Isometries of quadratic spaces

Analysis of Discrete L2 Projection on Polynomial Spaces with Random Evaluations