From: nikl+sm000281@pchelwig1.mathematik.tu-muenchen.de (Gerhard Niklasch) Newsgroups: sci.math Subject: Re: factoring big number into prime numbers! Date: 18 Aug 1998 11:49:55 GMT In article <35D7FBD8.602362BF@semo.nce.nokia.com>, Lars G Larsson writes: |> I have heard that there is several methods or algorithms |> for factoring big numbers into primes. The only known |> method for me is sieves, try to divide with all primes |> less than square root of the big number! |> |> Any hints to methods / algorithms of factoring |> big numbers is gratefully taken. See Chapters 8 and 10 of Henri Cohen's `A Course in Computational Algebraic Number Theory', Springer Grad.Text in Math. 138. Some of this material may be heavy going, depending on your background (but then there are the earlier chapters of the book to help!), so here's an all-to-brief introduction to two or three of the underlying ideas. (1) Factors up to several 10^5 are best found by trial division. (2) Factors up to ~10^40 and sometimes beyond are best found by methods which do computations in the residue classes mod N and occasionally compute a greatest common divisor of one of the current intermediate results with N. The idea here is that we have a ring Z/NZ of residue classes, in which we can add, subtract, multiply, and occasionally divide (using some kind of extended euclidean algorithm) -- if an attempt to divide fails, we'll have found a factor, which is what we ultimately want -- and that, if p is a smallish prime factor of N, there is a ring homomorphism from Z/NZ onto Z/pZ, so any computation we are doing mod N implicit- ly includes the same computation mod p. And now one tries to arrange the computation in such a way that it will sooner or later run into a cycle. Since there are far fewer residue classes mod p than there are mod N, it will relatively early run into a cycle mod p; that is, some intermediate result will be divisible by p but not by N, and taking a gcd with N will then reveal the factor p. John Pollard's `Rho method' and the `Elliptic Curve Method' are both based on this principle. For an online resource, see e.g. Paul Zimmer- mann's ECMNET page at http://www.loria.fr/~zimmerma/records/ecmnet.html, and the preprints linked from it, especially Brent's paper on the 10th and 11th Fermat numbers. To some extent, these methods can be parallel- ized, but if N has 100 or more digits and fails to have a factor of ~40 or fewer digits, the running time will nevertheless tend to become pro- hibitive. (3) Large numbers without relatively small factors can be split if we succeed in finding integers X,Y such that X^2-Y^2 is divisible by N, but neither X-Y nor X+Y is (and then a nontrivial factor will be revealed if we compute gcd(X+-Y,N)). This idea goes back to Fermat. The problem is finding X,Y -- an exhaustive search would take faaaaaaar too long. Fortunately, some very sophisticated schemes have been de- veloped which, for numbers N up to a hundred digits or more, will come up with suitable pairs in affordable time; some of them parallelize well, and have been used to split ~130-digit numbers using idle time on thousands of PCs and workstations. The `Continued Fraction Method' and the `Multipolynomial Quadratic Sieve' and `Number Field Sieve' come in this category. (One catch with (3) is that no method based on this principle can ever factor an odd prime power. So one also needs to check for pure powers.) If you want to see some of these gadgets in practice, and at how they can be used in succession to attack a number of unknown composition, look at http://pari.home.ml.org/, download pari-2.0.11.beta (2.0.12 will be out soon), compile it, run it, type `default(debuglevel,5)', and use `factor()' on your favorite 50- and 60-digit numbers -- depending on the product of your processor's clock speed by your patience, 70 digits may either still entertain you or begin to bore you -- and glance at the source code while you're waiting... Enjoy, Gerhard -- * Gerhard Niklasch * spam totally unwelcome * http://hasse.mathematik.tu-muenchen.de/~nikl/ ******* all browsers welcome * This .signature now fits into 3 lines and 77 columns * newsreaders welcome ============================================================================== From: bobs@rsa.com Newsgroups: sci.math Subject: Re: Integer factorization Date: Mon, 29 Jun 1998 18:57:41 GMT In article <3597A1C8.B5A9B2EA@caiw.nl>, "R.W.Dirksen" wrote: > > Hi, > I'd like to know how I can factor a large random integer faster than > with trial factoring, for example the number > 13973968988880514322397740519754649357 > I know that it's factors are > 1219569675601, 2505272722451 and 4573599673007 > but how to calculate them? I know it must be possible since I've read > about people factoring a 130-digit number... this number is only 38 > digits shouldn't be too hard. There are a number of methods available. Pollard P-1, P+1, Pollard Rho, The quadratic sieve (and variants) the elliptic curve method, the number field sieve (and variants) etc. etc. To answer your question in full would require a book. Fortunately, there are several: Bressoud, D. Factorization and Primality Testing, Springer-Verlag Riesel, H. Prime Numbers and Computer Methods for Factorization, Birkhauser. Lenstra, A.K. & Lenstra, H.W. (Eds) The development of the number field sieve, Lecture Notes in Math #1554, Springer-Verlag Cohen, H. A Course in Computational Algebraic Number Theory, Springer-Verlag You might also want to look at Knuth Vol 2, chapter 4. -----== Posted via Deja News, The Leader in Internet Discussion ==----- http://www.dejanews.com/rg_mkgrp.xp Create Your Own Free Member Forum