Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uwm.edu!zaphod.mps.ohio-state.edu!sdd.hp.com!elroy.jpl.nasa.gov!ames!ads.com!decwrl!bacchus.pa.dec.com!jumbo!src.dec.com!msm From: msm@src.dec.com (Mark S. Manasse) Newsgroups: comp.theory Subject: Re: factoring a large prime Keywords: factor prime Message-ID: <1990Jul17.211511.3992@src.dec.com> Date: 18 Jul 90 04:15:11 GMT References: <1519@excelan.COM> <113487@linus.mitre.org> Sender: news@src.dec.com (News) Reply-To: msm@src.dec.com (Mark S. Manasse) Organization: DEC Systems Research Center Lines: 24 The factors were 49 and 99 digits, not quite small enough to find using, say, exhaustive search :-) For the algorithm we used, the size of the factors was irrelevant. There are algorithms that can find factors more efficiently if the factors are relatively small, but none of them are good at finding 49 digit factors. The thing that prevents us from factoring arbitrary numbers of this size is not the factor size, but rather that the algorithm we used is *much* more efficient when we have a simple algebraic description of the number being factored. In particular, what we need is to find a polynomial which has a zero modulo the number we want to factor; we want the zero to be around the fifth root of the number being factored, and we want the polynomial to have as many coefficients as small as possible (and still be irreducible). In the factorization of the ninth Fermat number, the polynomial was x^5+8, for which 2^103 is a root mod 2^512+1. For arbitrary numbers, we know how to find a polynomial of the right degree with a zero of the right size, but we have no idea how to make the coefficients small. Mark