Paper 2005/208

On Finding Roots Without Factoring and A Special Purpose Factoring Algorithm

Daniel R. L. Brown

Abstract

For any integer $n$, some side information exists that allows roots of certain polynomials modulo $n$ to be found efficiently (in polynomial time). The quartics $q_{u,a,b}(x)=x^4-4u{x}^3-2a{x}^2-(8b+4ua)x+a^2-4ub$, where $a$ and $b$ are some fixed integers, can be solved with probability approximately $\frac{1}{4}$ over integers $u$ chosen randomly from in $\{0,1,\dots ,n-1\}$. The side information depends on $$ and $$, and is derivable from the factorization of $$. The side information does not necessarily seem to reveal the factorization of $$. For certain other polynomials, such as $$, it is an important unsolved problem of theoretical cryptology whether there exists an algorithm for finding roots that does not also reveal the factorization of $$. Cheng's special-purpose factoring algorithm is also reviewed and some extensions suggested.

Note: Steven Galbraith found a major flaw in this paper: the information used to find roots also reveals the factorization. My attempts to correct the flaw failed. A later revision of this paper may describe the flaw and attempted fixes.