The field of definition of function fields and a problem in the reducibility of polynomials in two variables
Introduction Let K be a number field, O the ring of integers of K. Suppose we are given a projective curve Z, and a morphism :Z pr(C) (where pr(C) is the projective line) such that and Z are both defined over K. We denote by K(Z) the field of functions of Z defined over K, and from this data we obtain a permutation representation T of the Galois group G(K(Z)^/K(Pr(C))) (where K(Z) is the normal closure of K(Z) over K(Pr(C) ). In Section 1 we investigate (for our needs) the combinatorial and group theoretical aspects of the situation where
Prime and composite Laurent polynomials
In 1922 Ritt constructed the theory of functional decompositions of polynomials with complex coefficients. In particular, he described explicitly indecomposable polynomial solutions of the functional equation f(p(z))=g(q(z)). In this paper we study the equation above in the case when f,g,p,q are holomorphic functions on compact Riemann surfaces. We also construct a self-contained theory of functional decompositions of rational functions with at most two poles generalizing the Ritt theory. In particular, we give new proofs of the theorems of Ritt and of the theorem of Bilu and Tichy.
Rubik's for cryptographers
Hard mathematical problems are at the core of security arguments in cryptography. In this paper, we study mathematical generalizations of the famous Rubik’s cube puzzle, namely the factorization, representation and balance problems in non-Abelian groups. These problems arise naturally when describing the security of Cayley hash functions, a class of cryptographic hash functions with very interesting properties. The factorization problem is also strongly related to a famous long-standing conjecture of Babai, at the intersection of group theory and graph theory. A constructive proof of Babai’s conjecture would make all Cayley hash functions insecure, but on the other hand it would have many positive applications in graph theory and computer science. In this paper, we classify existing attacks against Cayley hash functions and we review known results on Babai’s conjecture. Despite recent cryptanalytic progress on particular instances, we show that the factorization, representation and balance problems presumably remain good sources of cryptographic hard problems. Our study demonstrates that Cayley hash functions deserve further interest by the cryptography community.