On factoring polynomials, constructing curves and lifting points

In this thesis, we study three closely related problems in computational number theory and cryptography.; In the first part we develop a new algorithm for factoring polynomials over finite fields by exploring an interesting connection between the algebraic factoring problem and the combinatorial problem of stable coloring of tournaments. We prove that our algorithm performs better than the best previously known deterministic algorithm. Under a purely combinatorial conjecture concerning tournaments, the algorithm has polynomial time complexity.; In the second part we show that under a weak variant of the Bateman-Horn conjecture, if q and r are primes and q > (r log q)2 + epsilon, then there are at least O( qr logq ) non-isomorphic elliptic curves E/F q, such that the quotient group E( Fqr )/E(Fq) has prime order. We also show that under the same conjecture, if q and r are primes satisfying q > (2r log q)2 + epsilon and q=oqr logq , then there are at least O( qrlog q ) curves H/Fq of genus 2, such that the order of the quotient group Jac( H)( Fqr )/Jac(H)(Fq) is a prime. These results provide a guideline to properly set the parameters, such as q and r, when we need to construct this type of curve for cryptography.; The third problem concerns the difficulties of obtaining partial information about the global lift of a point on an elliptic curve over a finite field. In particular, we are interested in calculating the reduction of the global lift modulo another prime, which we call the shifting prime problem . We reduce the discrete logarithm problem on elliptic curves to the shifting prime problem in random polynomial time. This shows that shifting prime is as hard as solving discrete logarithm problem on elliptic; curves, when the target curves are general. On the other hand, we show that there is a non-uniform polynomial time shifting prime algorithm, consequently a nonuniform attack on DDH, if certain special global curves exist and we lift to these curves.