avnish@ka.excelan.com (Avnish Aggarwal) (07/10/90)
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 algoirthms I am aware of all work is a serial fasion.)
UUCP: {ames,sun,apple,mtxinu,cae780,sco}!excelan!avnish Avnish Aggarwal
Internet: avnish@ka.excelan.com pmontgom@euphemia.math.ucla.edu (Peter Montgomery) (07/11/90)
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
bs@linus.mitre.org (Robert D. Silverman) (07/16/90)
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 algoirthms I am aware of all work is a serial fasion.)
:UUCP: {ames,sun,apple,mtxinu,cae780,sco}!excelan!avnish Avnish Aggarwal
:Internet: avnish@ka.excelan.com
See the following:
T. Caron & R. Silverman
Parallel Implementation of the Quadratic Sieve
J. Supercomputing V. 1 #3, 1988 pp. 273-290
The algorithm used to factor F9, the 155 digit number just factored
was the Number Field Sieve, rather than the Quadratic Sieve, but its
parallel implementation is identical.
--
Bob Silverman
#include <std.disclaimer>
Mitre Corporation, Bedford, MA 01730
"You can lead a horse's ass to knowledge, but you can't make him think"wenger@twain.rutgers.edu (Rephael Wenger) (07/17/90)
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?
bs@linus.mitre.org (Robert D. Silverman) (07/18/90)
In article <Jul.17.08.56.13.1990.1180@twain.rutgers.edu> 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 <std.disclaimer> Mitre Corporation, Bedford, MA 01730 "You can lead a horse's ass to knowledge, but you can't make him think"
msm@src.dec.com (Mark S. Manasse) (07/18/90)
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