International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

On Finding Roots Without Factoring and A Special Purpose Factoring Algorithm

Authors:
Daniel R. L. Brown
Download:
URL: http://eprint.iacr.org/2005/208
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2005-12543,
  title={On Finding Roots Without Factoring and A Special Purpose Factoring Algorithm},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / RSA, Factoring, Roots},
  url={http://eprint.iacr.org/2005/208},
  note={ dbrown@certicom.com 12979 received 30 Jun 2005, last revised 13 Jul 2005, withdrawn 15 Jul 2005},
  author={Daniel R. L. Brown},
  year=2005
}