Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!zaphod.mps.ohio-state.edu!usc!ucla-cs!math.ucla.edu!euphemia!pmontgom From: pmontgom@euphemia.math.ucla.edu (Peter Montgomery) Newsgroups: comp.theory Subject: Re: factoring a large prime Keywords: factor prime Message-ID: <121@kaos.MATH.UCLA.EDU> Date: 11 Jul 90 04:35:28 GMT References: <1519@excelan.COM> Sender: news@MATH.UCLA.EDU Organization: UCLA Mathematics Dept. Lines: 102 In article <1519@excelan.COM> avnish@ka.excelan.com (Avnish Aggarwal) writes: >I read a report recently about how it is that a large (152 digit) >number had been factored using the combined resources of >something like 1000 computers. > >I would like to know more about this "parallel algorithm" >that permits all these computers to simultaneously work on the >same problem and is then able to merge the results. > >(Factoring algorithms I am aware of all work is a serial fashion.) "factoring a large prime" is easy; just write down the original number. But the 155-digit number recently factored was composite. Suppose we wish to factor n = 1234567. I will illustrate the original (single polynomial) quadratic sieve. The network machines search for values of f(x) = x^2 - n where 1070 <= x <= 1155 (say), reporting any case where all prime factors of f(x) are below 100 (or other convenient bound). The central machine validates these reports and stores the values in a data base. Soon it accumulates data similar to that in the left columns below. - 1113445566779 <- primes in 1231397173917137 factor base f(1070) = -3^7*41 v1070 = 1010000100000000 f(1087) = -2*3*11^2*73 v1087 = 1110000000000010 f(1091) = -2*3*11^2*61 v1091 = 1110000000010000 f(1102) = -3*11*13*47 v1102 = 1011100010000000 f(1103) = -2*3*41*73 v1103 = 1110000100000010 f(1105) = -2*3*37*61 v1105 = 1110001000010000 f(1107) = -2*47*97 v1107 = 1100000010000001 f(1108) = -3^2*13*59 v1108 = 1000100000100000 f(1109) = -2*3*11*71 v1109 = 1111000000000100 f(1111) = -2*3*41 v1111 = 1110000100000000 f(1115) = 2*3^2*13*37 v1115 = 0100101000000000 f(1117) = 2*3^8 v1117 = 0100000000000000 f(1124) = 3^3*11*97 v1124 = 0011000000000001 f(1134) = 13*59*67 v1134 = 0000100000101000 f(1142) = 3^3*11*19*37 v1142 = 0011011000000000 f(1144) = 3^3*41*67 v1144 = 0010000100001000 f(1152) = 37*41*61 v1152 = 0000001100010000 f(1154) = 3*13*47*53 v1154 = 0010100011000000 Each f(x) on the left is a product of primes from {2, 3, 11, 13, 19, 37, 41, 47, 53, 59, 61, 67, 71, 73, 97}, except perhaps for a minus sign. That set, plus -1, is called the factor base. After accumulating these values of f(x), we for a nonempty product of values f(x1)f(x2)...f(xk) which is a perfect square. This requires that the exponent of every prime in the product (including that of -1) be even. Set up vectors mod 2, as in the right column, with a 1 where the exponent in f(x) is odd and a 0 where even. Because we have 18 vectors in a space of dimension 16, these vectors must be linearly dependent. Upon solving appropriate linear equations modulo 2, we find three dependencies: 0 = v1070 + v1111 + v1117 = v1105 + v1111 + v1152 = v1070 + v1108 + v1134 + v1144 . Recalling f(1070) = -3^7*41 f(1111) = -2*3*41 f(1117) = 2*3^8 f(1105) = -2*3*37*61 f(1152) = 37*41*61 f(1108) = -3^2*13*59 f(1134) = 13*59*67 f(1144) = 3^3*41*67 and f(x) = x^2 - n == x^2 mod n, we conclude (1070*1111*1117)^2 == (-3^7*41)*(-2*3*41)*(2*3^8) = 2^2*3^16*41^2 = (2*3^8*41)^2 mod n, (1105*1111*1152)^2 == (2*3*37*41*61)^2 mod n, (1070*1108*1134*1144)^2 = (3^6*13*41*59*67)^2 mod n . Reducing the parenthesized quantities mod n = 1234567, these become 696565^2 == 538002^2 mod n, 679345^2 == 555222^2 mod n, 1146294^2 == 164473^2 mod n . The first two congruences are useless, because n = 695565 + 538002 = 679345 + 555222. The last, however, says n divides 1146294^2 - 164473^2 = (1146294 + 164473)(1146294 - 164473) = 1310767*981821. The Euclidean algorithm finds GCD(n, 1310767) = 127 and GCD(n, 981821) = 9721, so 1234567 = 127*9721. The recent factorization of 2^512+1 used a more sophisticated algorithm. But each site contributed relations, such as these values of x; after enough relations were submitted by network sites, the central site solved a huge system of linear equations mod 2 and found the factorization by multiplying the corresponding relations together. -- -------- Peter L. Montgomery pmontgom@MATH.UCLA.EDU Department of Mathematics, UCLA, Los Angeles, CA 90024-1555