Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!samsung!xylogics!merk!alliant!linus!bs From: bs@linus.mitre.org (Robert D. Silverman) Newsgroups: comp.theory Subject: Re: factoring a large prime Keywords: factor prime Message-ID: <113639@linus.mitre.org> Date: 17 Jul 90 19:19:22 GMT References: <1519@excelan.COM> <113487@linus.mitre.org> Reply-To: bs@faron.UUCP (Robert D. Silverman) Organization: The MITRE Corporation, Bedford MA Lines: 32 In article wenger@twain.rutgers.edu (Rephael Wenger) writes: > > >If I remember correctly the 150 digit number factored into >two numbers of about 15 and 135 digits each. Doesn't the >assymetry here suggest that in some sense the original >number was "easy" or at least "easier" to factor than >other 150 digit numbers? For cryptographic systems >one would usually form a key by multiplying two >primes of about equal length, say 75 digits each. >How much more difficult is factoring a number >of this sort? You memory is somewhat faulty. F9 = 2^512 + 1 factored as the product of 7-digit, 49-digit, and 99-digit primes. If F9 had had a 15-digit factor, its factorization would have been trivial. The number field sieve and quadratic sieve both have run times that depend only on the size of the number being factored and NOT on the size of the factors. Other methods find small factors first. For a 'random' integer of unknown origin, one always looks for small factors first before hauling out sieve methods. The elliptic curve method readily finds factors up to about 25 digits and can find factors up to 30 digits with moderate [e.g. ~1000 hrs CPU time] effort. -- Bob Silverman #include Mitre Corporation, Bedford, MA 01730 "You can lead a horse's ass to knowledge, but you can't make him think"