**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 - 4ux^3 - 2ax^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
$a$ and $b$, and is derivable from the factorization of $n$. The side
information does not necessarily seem to reveal the factorization of
$n$. For certain other polynomials, such as $p_u(x) = x^3 - u$, 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 $n$. Cheng's special-purpose factoring algorithm is
also reviewed and some extensions suggested.

**Category / Keywords: **public-key cryptography / RSA, Factoring, Roots

**Date: **received 30 Jun 2005, last revised 13 Jul 2005, withdrawn 15 Jul 2005

**Contact author: **dbrown at certicom com

**Available format(s): **(-- withdrawn --)

**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.

**Version: **20050913:200517 (All versions of this report)

**Short URL: **ia.cr/2005/208

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]