Posts by Kevin

1) Message boards : NFS Discussion : EM43 (Message 485) Posted 8 Jun 2010 by Kevin Post: "The next (hopefully small) roadblock is EM47, a 256-digit number (thus out of GNFS range) with no prime factor smaller than 20 digits." Hopefully it isn't a p128 * p128 or similar, or else that would take you a few years. On the flip side, it would give a new world record if it were indeed a p128 * p128.
2) Message boards : NFS Discussion : Factor this! (Message 484) Posted 7 Jun 2010 by Kevin Post: "Even having equal size factors that are too close together can make the number easy to factor by the Fermat method." True.. But that's only if it's within sqrt(n)- (n^(1/4)) Also, there are non-math means to break an RSA key. (Ex: Timing attacks)
3) Message boards : NFS Discussion : Factor this! (Message 483) Posted 7 Jun 2010 by Kevin Post: I took the time to research.. It turns out I was incorrect on all counts. A sad day for me. The BOINC program slowed my computer to a crawl, to be honest..
4) Message boards : NFS Discussion : Factor this! (Message 481) Posted 7 Jun 2010 by Kevin Post: "Those are the homogeneous Cunningham numbers. See http://www.leyland.vispa.com/numth/factorization/anbn/main.htm " Is this where there is a list of 732 of them? "Perhaps, but likely not." Nope. There's a 100% chance that it has at least one of the properties I listed. "Actually, in this case "common sense" is leading you astray. If the smaller number was 60-65 digits or less, then ECM would make factoring the number much easier. However, a C240 = P96 * P145 is no easier than a C240 = P120 * P120. And if the number has no special form, then it is harder than the current record GNFS factorization." If the smaller factor were in fact a c31 to c36, any average joe would be able to factor it in about an hour using ECM. How is it equally difficult? A difference in size of 49 digits makes it in fact far easier than p120 * 120. Think of it this way: Suppose you had to sift through 96 objects to find a certain object out of 240 in one pile, and you had to sift through 120 objects in another pile. It'll be easier to sift through 96 objects than 120 objects. In fact, it would be faster attempting to pick out a p96 factor than it would be trying to pick out a p120 factor. The point of that (somewhat mediocre) analogy is that semiprimes whose factors are of identical size are more difficult to factor. That's the main reason why RSA moduli are generated using primes of similar/identical size. Because it's more difficult to factor a semiprime composed of primes of similar or identical size than it is to factor a semiprime whose prime factors vary in size. Because the running time needed for a factoring algorithm depends on the size of the smallest prime factor (Almost all (if not all) factoring methods work this way.). You can't dismiss the painfully obvious. :\| "And in fact it is. That is a large part of the point of this project. RSA-512 is totally broken. There has been one successful factorization of RSA-768, and we hope to improve our software to be able to factor more numbers of that size soon." RSA-768 style numbers? I think you should give it 15 ± 10 years. "That size is currently out of reach of GNFS. But there are people working on it." If they're not using SNFS, I don't know what it is that they're using.. Fermat's, Dixon's, Trial division, MPQS, QS, SIQS are not recommended for p77 factors... "He is referring to a factor of 68-digits, not a composite of 68-digits. The current world record ECM factor of a number of a form other than 2^n +/- 1 is 68-digits." Is this referring to a semiprime? If not, can you list ECM's world record for that?
5) Message boards : NFS Discussion : Factor this! (Message 478) Posted 6 Jun 2010 by Kevin Post: "No offense is intended, at least from me anyway :-)" Excellent! :) "but there are a large number of unfactored numbers that are of interest to mathematicians, computer scientists, and laymen that will keep us busy for a very long time" The Cunningham project? You could just add to it by contributing a random b^n + 1 or a^n + b^n Ex: 5^300 + 1, or 6^429 + 11^429. "We are mainly working on the Cunningham project numbers for now, but there are many other candidates of interest." I think there are somewhere between 730 and 1200 of those.. That's going to keep you busy for a long time indeed, and that's not even factoring in the new a^n + b^n you contribute to the site each and every day. "Factoring a randomly generated semiprime with no special significance is not a good use of the volunteer computer time. " No special significance? That's outrageous! Perhaps, at some point, the number I posted is a cofactor of a number of the form a^n + b^n, or a^n + 1. That seems significant to me. Perhaps it's the cofactor of a number n where n^2 + 1 is prime. Perhaps it's the cofactor of a fibonacci number. The number can also be a cofactor to a Lucas number, the cofactor to an n^2-1 number, the cofactor to an n^2 + 1 number, among many (hypothetical) other properties that I can list. That doesn't seem "insignificant" to me. And, by that logic, apply the same reasoning to your own members, as I said before. Your reasoning, turned on you: "Factoring a randomly generated a^n + b^n number is not a good use of volunteer computer time." "You have a c240 or maybe c241 (96+145). Is the intended point that it's no easier to factor than a prospective RSA number pq, with p and q both primes with 120-digits?" It's c240. And, that point would be false, a difference in size between the prime factors makes it easier to factor. That can be determined by common sense alone. "Since the current record for RSA numbers is RSA768, 233-decimal digits; factoring the number you've posed isn't much different than asking for a new record factorization of an RSA number, with 240-digits." But this would not count, as it would be too easy (Because of the difference in size of the prime factors in question) "I don'thave know your background, but have you looked at the resources needed for setting some of the previous records?" All previous records and RSA-768 were all factored using SNFS or GNFS. " Numbers of comparable difficulty (size, for gnfs) with the snfs numbers we're working on here might have 180-digits; with 170-digits not-so-difficult, and 190-digits harder than our current resources." You might as well begin trying to break someone else's RSA keys. (155 digits, or a typical 512-bit RSA modulus, would be incredibly easy to do, by that reasoning.) "There's already a challenge number of this type, with 1024-bits (c. 310-decimal), which is known to be of the form p1p2p3p4, where each pi is a prime (i = 1,2,3,4) with 256-bits. Factoring this previous challenge number by a method easier than factoring a 1024-bit RSA-key requires a method, easier than sieving (gnfs or snfs) that would be able to make use of having a 77-digit prime factor (c. 256-bits). Perhaps this previous challenge is easier than yours (p77 instead of p96)?" Four 77-digit numbers? Wouldn't this be easier by searching for factors in the range of 10^76 or 10^77? And why not use GNFS/SNFS? It's your best method for numbers of that size. (It is unlikely that there will be any methods better than GNFS/SNFS for factoring.) And as for it being an easier challenge, I would be inclined to agree that it is easier, but it's four 77-digit numbers. Repeating the process to find three of the four factors? That will take you a few months. Factoring p96 * p145 would be somewhat easier given the difference in factor size, and the fact that you only need to find one factor out of the two to complete the factorization. But it is 19 digits larger, so I'm guessing that the two factorizations would take an equal amount of time. "The person proposing this earlier challenge heads one of the top factoring research labs, and they have made some progress by finding p73 factors; setting a record for ecm, with the slight issue that the 73-digit primes are quite far from being random" Hmm. Interesting. I think that a p80 might be found by ECM sometime soon. (By sometime soon, I mean 10 ± 5 years.) And, of course, it was found from 2^1181-1. "uhm, guess you're not going to be impressed, their primes all divide numbers 2^n -1. If you want random, the best we can do is 68-digits." This is well-known, and.. 68 digits? I can do that in 5 minutes!
6) Message boards : NFS Discussion : Factor this! (Message 471) Posted 24 May 2010 by Kevin Post: 1. Random generation using random primes (Factors = p96 * p145) 2. Wait, wait, wait.. you only factor numbers of the form b^n + 1? By that reasoning, ask that question to everyone participating. Sorry for trying to contribute to the site.. Sheesh. O_O
7) Message boards : NFS Discussion : Factor this! (Message 469) Posted 24 May 2010 by Kevin Post: 682934139764871621059294670540409779256277785405904002174839913653988630704152088904136121991617552380023455259399723952023653153643548060833653509153580215597699356690840851264278901841510478481653190812472058220200188105772756389172416253

Home | My Account | Message Boards