Posts by bdodson*
|
1)
Message boards :
News :
3,766+ factored
(Message 1509)
Posted 18 Mar 2015 by bdodson* Post: 3,766+ has been factored. It is the product of 66-digit, 75-digit, and 76-digit prime numbers. This is a new Cunningham project champion for GNFS. Let's now set a new record with 3,697+! In lieu of a much needed status update, 3,697+ was completed and reported to the Cunningham site during February as c221=p67*p76*p78
as compared with
for the previous record. That was
for the smallest factor. Current ecm-pretesting is fairly reliably finding p65's, using standards set in pretests for these nfs@Home gnfs's at c216, c221. Seems like one of these might have been found, with a bit more luck. Cunningham numbers currently reserved for nfs@Home include
If I recall, 3t60 =c. 15t55 was applied to these two record gnfs's. I was muttering at the time that adding an additional 2t60 to a completed 3t60 (for a c. t65) seemed too likely to be unproductive; but I've since gotten used to it (more or less!). -bdodson* (still 4th in total sieving creds; maybe 4th in ecm? after four consecutive records) |
|
2)
Message boards :
Questions/Problems/Bugs :
Work to do
(Message 1085)
Posted 28 Jan 2013 by bdodson* Post: That's a possibility, but not during this grant year. I proposed a fairly aggressive schedule, so I don't want to take computers away from those numbers. Following 2,1049+, I've proposed three GNFS factorizations of 202, 207, and 212 digits, presuming they survive ECM pretesting. As I was remarking over on mersenneforum Dec 28 09:43 dec27-cu26987-p60up-5t55-10M770 Jan 1 11:21 dec31-cu25200-p60up-5t55-10M770 Jan 8 15:46 jan07-cu26986-p60up-5t55-10M770 corresponding to c. 3t60 ran on the C212. (That's 79K curves with B1 = 400M, gmp-ecm default B2.) I also had t60's on the C202 and C207, which are from the recent base-3 extension, where Sam was saying that he ran t60's before adding them to the regular list. I'd say that these have already survived ECM testing. -Bruce (Incidently, 7p373 C303 has also survived a t60 (with B1 = 600M), and I'll run a bit further.) |
|
3)
Message boards :
NFS Discussion :
3,637+ factors
(Message 1032)
Posted 17 Oct 2012 by bdodson* Post: bdodson , I'm happy to see Greg in first place. The University discontinued the semi-public linux labs that I was using for most of the nfs@Home computing I was doing. Those were commodity quadcores. I ran some on the replacement research machines, but nfs sieving was causing them to need occasional rebooting, which meant asking sysadmin assistance instead of heading over to a lab where I could hit reboot. I'm still doing gnfs sieving on our research machines, just not on Boinc - they're run under a PBS scheduler, and don't allow interactive logins. -Bruce (11p301 tested to t60, working on 11m301) |
|
4)
Message boards :
NFS Discussion :
3,637+ factors
(Message 1023)
Posted 10 Oct 2012 by bdodson* Post: How much ecm was done on this integer? Same thing I was wondering on seeing p63*p66. Looks like 26,987 curves with Using B1=400000000, B2=5821851770290, polynomial Dickson(30) with GMP-ECM 6.3 (Dec 2011) and 6.4 (May, 2012). This was supposed to be a test sufficient to find a p60 to probability of 62%; the limits are non-trivially above p60-optimal (B1=260M), but well below p65-optimal (B1=850M). This was a 15e number? If I recall, I went to 2t60 on the most recent 16e pretest, but even that wouldn't have given very substantial odds at finding one of p63, p66. Maybe 50-50, if I'd doubled my curve count. Good you've asked though; how much do we have on 11p301 and 11m301? I've just finished .6t60 on the c210 and .4t60 on the c261 as initial passes for this recent extension to the Cunningham lists. Not sure whether Sam got his "usual" t60 before adding the extension; as these two most recent ones were added early (to catch the p79 record!). Perhaps it's worth adding some more? -bdodson (not sure that my p70 will stay in the top5 for 2012!) |
|
5)
Message boards :
NFS Discussion :
p52 ecm factor of 7, 749L, complete
(Message 905)
Posted 10 Jun 2012 by bdodson* Post: i am not understand this forum The numbers being factored in this project are factored using a sieving method; specifically by the "Number Field Sieve" = NFS. This is a method intended to be applied to "worst case" factorizations, a number with only two or three prime factors, the smallest with at least 55-digits, preferably at least 60-digits. If you look under "Status of Numbers" you have to go all the way back to Nov 17, 2010 to find a prime factor below 60-digits (2,2086L factored as p55*p149; the smallest prime factor having 55-digits). Until recently almost all of the numbers being factored are taken from the Cunningham project, with a few exceptions for numbers of interest from other projects. These are not manufactured numbers, like RSA-keys, designed to have just two large prime factors. If one picks a random composite number with between 155-digits to 310-digits (that's 512-bits to 1024-bits) very few will fail to have a prime factor below 25-digits. For a number with smallest prime factor between 25-digits and c. 60-digits the Number Field Sieve is not the best method. That factorization from Nov 2010 was referred to as an "ecm miss" because the 55-digit prime was not found by the best method. There are other boinc projects devoted to using ecm to find these "mid-sized" prime factors; again NFS is intended only for worst-case factorizations. This "forum", the thread "p52 ecm factor ...", is a report of an ecm success. The number 7,749L was a candidate selected by Greg as a possible number for NFS@Home to factor with the number field sieve, but I was fortunate to find the 52-digit prime during pretesting, before sieving started. Hope this helps. -bdodson* |
|
6)
Message boards :
Questions/Problems/Bugs :
Some questions
(Message 815)
Posted 25 Mar 2012 by bdodson* Post:
Among the google hits from "special-q factoring" you may find links to mersenneforum, as well as several technical reports on which special-q have been used in various "number field" and SNFS ("special" number field) factorizations. They are used in the "lattice sieving" step in the "number field sieve". This is a message board for a boinc project that uses special-q for lattice sieving. There are many prerequisites necessary for even a general description, which are outside of this project's focus on people intending to request and complete sieving tasks. You might try wikipedia for "spring break". -bdodson* ----- @Bob --- We discussed the selection of 5p433, and here's Greg's view
M1007 was a candidate from the list of targets of the EPFL effort using ECM on their PS3 cluster. We had just recently completed M1031, and even then were hoping that M1061 would finish in the next few weeks. The other numbers weren't in consideration on our list. |
|
7)
Message boards :
Questions/Problems/Bugs :
Some questions
(Message 807)
Posted 18 Mar 2012 by bdodson* Post: Your previous post answers all my questions, except part of number 2. Until recently, this was M1237, but there was a spectacular ECM factor with 70-digits found using a network of PS3's. The cofactor has 303-digits, and is composite, so it could be a very long time before we know the rest of the factors. There's currently an effort on mersenneforum to factor M929, after which M947 will be the smallest not completely factored. Note that M1007 is currently fourth, in about the same range as 2p1000, which is first on the 2+ list, and 10th on the Cunningham Most Wanted list. So anyway, the GIMPS report currently lists M1277 as the next smallest after M1061, then M1619. The exponent range there is up to 10000 looks more than 50 less than 100 http://www.mersenne.org/report_factoring_effort
I thought you knew that. So long as tasks for 2p1000 are being distributed, that means that Greg doesn't need more reports to start the matrix step. These 15e projects are smaller numbers, and the matrix is most likely running on the cluster at Cal State -bdodson* (still NFS@Home's number 1 contributor, hoping that both Greg and I will get bumped by someone else!) |
|
8)
Message boards :
Questions/Problems/Bugs :
Some questions
(Message 805)
Posted 16 Mar 2012 by bdodson* Post: I have some questions regarding this project: Parts of these two questions are related. The Cunningham number 5, 433+ is the project that is intended to follow 2, 1061-, once 2, 1061- is completed. If you're receiving tasks for 5p433, that's a good indication that 2, 1061- has completed sieving, or will soon; provided that the next step is up and running (the matrix step, a non-bonic calculation, done under the terragrid grant, on a national supercomputing site). In particular, 5p433 is the next number that uses the 16e siever.
The other numbers listed on the status page are all 15e projects (that's why 5p433 is being added), and one expects that they'll be done in order, 2,1000+ first then the next, 11,290+, then ... I can't speak to plans for visual apps or non-Cunningham numbers; I would expect that a fair part of Greg's attention is going to the next step for 2,1061- (a record- setting number; and the most wanted Mersenne number --- the last one from George Woltman's list of 2, n- with n <1200 having no known factor). -bdodson* |
|
9)
Message boards :
Questions/Problems/Bugs :
200 digits number from the book "In Code: A Mathematical Journey"
(Message 725)
Posted 3 May 2011 by bdodson* Post: That book was written a decade ago, ... I cannot justify spending this much of the NFS@Home participants' and supercomputer time for a number that's just a curiosity. Sorry. I'm not curious, even. For comparison, the largest GNFS currently on NFS@Home's list is 183.7. I hear that adding five digits to the size in GNFS in this range doubles the difficulty (runtime, in particular); that's three doublings (at a minimun), 8-times as difficult. Also, I wondered on reading the original post how closely the person posting had looked at the two numbers referred to, RSA200 and then RSA768 (at 232-digits, maybe 233?). Both numbers were done by a single non-public group, with dedicated hardware; a group that includes the people that wrote the original lasieve code, using completely different linear algebra code, that I don't believe is yet in the public domain. The current NFS@Home project on SNFS is the first pass at a public approach to the records set by that group; Bonn (GNFS200), Bonn-NTT-EPFL (SNFS1024) then Bonn-NTT-EPFL again (GNFS232) over a decade-or-more's work. We're just now about to meet, and then break, their SNFS record --- check the status page --- 2,1031- SNFS 310.7 and 2,1061- SNFS 319.7, respectively. For a comparable public project on GNFS, mersenneforum may have the best chance; having recently completed GNFS187, and just starting on GNFS197. The first attempt at the GNFS matrix failed, after months of computing; and we were very happy that the second attempt succeeded. A suggestion that GNFS200 is now on the borderline of being routine, as a public project, just isn't correct. Finding and multiplying two 100-digit primes is indeed a plausible project for a computing beginner; hardly even requiring a math coding prodigy. Breaking 200-digit composites isn't yet in that range. -bdodson (still NFS@Home's top contributor; first past 50M credits) |
|
10)
Message boards :
Questions/Problems/Bugs :
All work error out?
(Message 713)
Posted 24 Mar 2011 by bdodson* Post: I shifted my host to the smaller lasievee (v1.08)till this is sorted out. Yes. The 16e tasks all errored out in under 10 seconds; many people had settings to take other tasks if there weren't any 16e's left (that's 16e = lasievef); so the 15e tasks are all done also. We need Greg's attention on this one. -Bruce |
|
11)
Message boards :
NFS Discussion :
AndrOINC
(Message 691)
Posted 27 Jan 2011 by bdodson* Post: Are you sure that even with your alghorithm, thousands of computers and GPU support it will still take ages? I thought that sieve is a really fast method so we can crack RSA 1024 with huge power(~4000 computrs working on it) within few years.. In a gnfs factoring project, the result of the sieving effort is a sparse matrix problem, that has to be solved to break the key. Computations on the matrix problem (even in the distributed version used to break RSA768) are parallel, with heavy data transfer between compute nodes --- that is to say, an expensive supercomputer calculation. NFS@Home is currently working on 1024-bit SNFS, while RSA keys require GNFS. There has recently been a five-or-more year gap between the SNFS record and the corresponding GNFS record for the same number of bits. So SNFS768 was set in 2000, RSA768 in Dec 2009; SNFS512 in 1993, RSA512 in 1999. For 1024-bits, SNFS1024 was first broken in 2007, but not by a public project. Switching from bits to digits, 768-bits is 233-decimal and 1024-bits is 310-decimal (resp. 512-bits, 155-decimal). NFS@Home has been working up towards the 310-digit _public_ SNFS record, and most recently broke 295-digits (Nov 29, 2010). The matrix for 300-digits is currently running under a terragrid grant --- for example, previous sparse matrices from NFS@Home were run on the first of these two clusters http://www.tacc.utexas.edu/resources/hpc/ The software being used has not been tested in this range --- we're the first. And that's 295-digit, 300-digit and then 310-digit, for public SNFS. And then another 5-10 years from SNFS to GNFS, on a computer that hasn't been built yet. Hope this clarifies matters. -bdodson* |
|
12)
Message boards :
Questions/Problems/Bugs :
4 sieving and 2 not yet started. What's next???
(Message 683)
Posted 14 Jan 2011 by bdodson* Post: Why 2,979+ instead of 2,947+? Why not do the holes in order? We're currently doing 1040+ and 1099+ by gnfs (15e), and 997+ and 1031- by snfs (16e), and you're still unhappy that the numbers from 2+ and 2- aren't being done in order? Also, I wonder whether you object to the Wagstaff-Selfridge lists of Wanted and Most Wanted numbers? They're not just taken in order, with 1061- as a recent addition. Will you object if Greg follows 1031- with 1061-, instead of taking the 2- list in order? I'm fairly certain that you won't mind!, Regards, Bruce* |
|
13)
Message boards :
NFS Discussion :
p52 ecm factor of 7, 749L, complete
(Message 681)
Posted 14 Jan 2011 by bdodson* Post: ... I had to look this one up. Mersenneforum reports
One of those factors is 7L, the other 7M. The first post by Raman in the thread "Aurifeuillian Factorizations" under the subforum "Cunningham Tables" (it's not a sticky thread; you need to scroll down a page or three). Uhm, sub-subforum, under "Factoring Projects". (And 14k-7 = 749, so 14k = 742 and k = 73.) Greg would have picked these seven numbers up from "Appendix C" on the main Cunningham page, which lists composite cofactors after removing all known factors. The "Main Tables" lists the known factors and then C238 in the 7+ table, under 749; where C238 is the number I factored, given in appc1210 (the latest update to Appendix C). The other six numbers are ready to be sieved (as 15e projects), with ECM having failed to find any other factors after an effort sufficient to find/remove 55-digit prime factors. If you scroll through the factorizations found by NFS@Home on the "Status of Numbers" link, you'll see one 54-digit prime, and one 55-digit prime. Those were ECM misses; reflecting the fact that ECM is a probabilistic method. The next smallest prime found looks to be a 58-digit prime, perhaps a borderline case. I don't claim to be able to reliably find/remove primes at/above 60-digits (to 62%, or to 80%, respectively). I do make a larger effort on numbers for the large memory 16e projects; perhaps sufficient to find 57-digit primes. The current 16e project was subjected to an intensive ECM effort on a network of PS3's, which we believe was sufficient to find a 65-digit prime factor (an average 65-digit prime, to 62% chance, so 2-out-of-3). -bdodson* |
|
14)
Message boards :
NFS Discussion :
p52 ecm factor of 7, 749L, complete
(Message 680)
Posted 13 Jan 2011 by bdodson* Post: somewhat dumb questions here: Primality proofs are "easy", certainly through 1000-decimal digits; the record (for a random probable prime) is 20,000-digits. Check out any text on computational number theory; or Pomerance-Crandal for the cannonical math reference. Here's wiki: A primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. As of 2010[update], factorization is a computationally hard problem, whereas primality testing is comparatively easy (its running time is polynomial in the size of the input). Some primality tests prove that a number is prime, ... and, under "Fast Deterministic tests": Near the beginning of the 20th century, it was shown...The first deterministic primality test significantly faster than the naïve methods was the cyclotomy test; its runtime can be proven to be O((log n)clog log log n), where n is the number to test for primality and c is a constant independent of n. Many further improvements were made, but none could be proven to have polynomial running time. The elliptic curve primality test can be proven to run in O((log n)6), but only if some still unproven (but widely assumed to be true) statements of analytic number theory are used[which?]. Similarly, ... In 2002 the first provably polynomial time test for primality was invented by Manindra Agrawal, Neeraj Kayal and Nitin Saxena. The AKS primality test, runs in Õ((log n)12) (improved to Õ((log n)7.5) in the published revision of their paper), which can be further reduced to Õ((log n)6) if the Sophie Germain conjecture is true.[3] Subsequently, Lenstra and Pomerance presented a version of the test which runs in time Õ((log n)6) unconditionally.[4] AKS is slow in practice; ECPP is the method of choice for a random number. If you're looking for more online info, there's Chris Caldwell's prime pages, which has 211 references: http://primes.utm.edu/links/ -bd |
|
15)
Message boards :
NFS Discussion :
p52 ecm factor of 7, 749L, complete
(Message 671)
Posted 26 Dec 2010 by bdodson* Post: Here's a number that's not going to get to the Status page, previously not having gotten much attention as composite with 238-digits, 7,749L factors as
An ecm success; one fewer number to sieve. Not to worry, Greg has another six candidates, presently in ecm pre-testing. -bdodson* (newest member of team Sicituradastra) |
|
16)
Message boards :
Questions/Problems/Bugs :
Error's while Computing ?
(Message 656)
Posted 18 Dec 2010 by bdodson* Post: unlike Paladin/.Steve with his #1 _world_ Whoa!! The number 1 Ranking is a fantastic acomplishment; I'm a huge fan. Of the boinc contributors with what appears to be nearly unlimitted resources (top 100, say), you're one of our most interesting contributors. You were one of the first boinc contributors to contact me, and I spend quite a bit of time trying to learn from what you do. You can be somewhat abrasive, but that's not necessarily a bad thing; among friends. I'm 110% certain that I don't dislike you. Puzzled sometimes, perhaps; but in a good way.
One of the things I've learned is the extent to which projects that have apps the make good use of GPUs have an advantage in attracting contributors. I'm guessing, but I wonder whether 95% (or more) of your credit is from GPU contributions? I was just reading that you favor 580's. I'm stunned to hear that you purchase all of the Pharm with your own funds. That's some Retiree Pension, we all should have been so lucky; I'm just about to turn 61, but it looks like I'll need an extra 5-7 years after my age 66 to make-up for our 401k's having become 201k's. And besides, I'm fairly sure that you've been very well informed in deciding how to spend the funds you have available. Uhm, you couldn't choose to direct your GPU resources here; since we don't know how to do number-field-sieving (nfs as in snfs/gnfs, used in the lasieve's) with GPUs. I've been trying to convince anyone I can that finding polynomials is a really good thing; but I'm not sure that I've succeeded at convincing myself --- doesn't appear to be a couple of orders of magnitude of a bump, the way a really killer GPU app should be. So we're discussing the remaining 05% of your resources; and they're for sure yours to allocate as you choose. And, uhmmm, "fear of animosity"? Hmm; I hope not. So, anyway, after a year-or-so of watching your GPU acomplishments, I did in fact convince our HPC committee to purchase two Nvidia cards (actually, that's not my fault; the engineering faculty wanted double prec. floating point, so what we got was the tessla 20s). They seemed fairly happy about the $9K purchase; a large blurb on the main web page. I'm happy to be able to report that I've just today managed to get primegrid's Proth Prime sieve to run; and it's already running credit circles around my NFS@Home credit; looks like 100K credit from a rather large pool of x86_64's by CPU; vs 500K credit from just the two cards -- looks like they're just a tad slower than the 580's. So even I won't be 100% NFS, with just a week of two of Proth sieving. You carry a lot of weight. By right of having earned it. I'll only be one of 100's if I manage to break into the top 1000. So what can I do to make amends for having left the wrong impression in my posts? Would switching teams help? I'm not getting much, if anything, from BonicStats. With warmest regards, your Friend, Bruce/bdodson. |
|
17)
Message boards :
Questions/Problems/Bugs :
Error's while Computing ?
(Message 653)
Posted 14 Dec 2010 by bdodson* Post: You're right. This number does have an unusually high failure rate of about 10% on Windows but not on Linux, and it's not the usual memory error. ...it will be a few weeks before I can get to it. Thanks for letting me know! Thanks for the report (if Greg will pardon my presumption) and the wishes. I wasn't able to tell whether the computing errors were bothering you (unlike Paladin/.Steve with his #1 _world_ bonic ranking, who likely doesn't need any extra distractions). I do run lasievef/16e tasks on our large linux workstations; but have the five with lower memory (1Gb/core) working on the smaller lasievee/15e tasks (a total of 20 xeon cores). As I sometimes teach an intro course on (mathematical) cryptography, and have been contributing to applied cryptographic computing since 1995 (starting with the first RSA120); I have more than enough education, much of it since my pure math phd (1976). I'm not entirely sure that I can make a case for snfs projects under 15e, as compared to snfs projects under 16e. But we have two serious gnfs projects next in the 15e queue (found in the "Status of Numbers" link, on the main NFS@Home page). First, the math part of a gnfs project is substantially more elaborate than what is required for snfs ("512-bits in 1993" for snfs -vs- "512-bits in 1999" for gnfs; and then, "768-bits in 2000" for snfs -vs "768-bits in 2010" for gnfs!). Next, the current computing issues are very interesting. In particular, the project definition for these two 180-digit gnfs numbers was found (by Greg) using GPU computing on nvidia/tessla graphics cards. You won't see a difference in the WUs (unless you locate the "gnfs polynomial" used in the project definition), but these results will be at least as interesting as the current 16e snfs. Regards, bdodson (No promises about the _next_ 16e snfs, and the one after that, which are the reason for Greg's push to larger/harder projects; but those may be even worse for low memory computing.) |
|
18)
Message boards :
Questions/Problems/Bugs :
Error's while Computing ?
(Message 634)
Posted 9 Nov 2010 by bdodson* Post: If your running Linux the 2 Lines that read in the App File >>> primegrid_ppsieve_1.30_windows_intelx86__cuda23.exe <<< must read as the Linux executable that your using ... That was exciting. I switched these two lines to match the linux binary I downloaded primegrid_ppsieve_1.30_i686-pc-linux-gnu__cuda23 and that ran through several 10's of "computation errors". My primegrid account gives the error message <message> process exited with code 22 (0x16, -234) </message> <stderr_txt> execv: No such file or directory </stderr_txt> Likewise, the boinc Manager message says (repeatedly) starting pps_sr2sieve_... starting task pps_... using pps_sr2sieve version 130 computation for task ... finished output file pps...0_0 for task pps...0 absent I suppose, sooner-or-later, someone should object to this off-topic exchange; even between 2 of the present top3 on NFS@Home, but I wonder that we're still making progress? Looks like the error message just reports that the expected output file is missing? -Bruce |
|
19)
Message boards :
Questions/Problems/Bugs :
Error's while Computing ?
(Message 632)
Posted 9 Nov 2010 by bdodson* Post: Are you running Linux ? Yes. Although I was noticing that the Berkely site lists instructions ("yum ...") I don't understand for fedora7; while we use a ("close") variant "centos" (as do many university sites with heavy computational interests). The linux versions 56, 58 don't seem to run nearly as well as 6.10 used to; and I was hoping to get a recent version more likely to be GPU aware.
Now that would catch some eyeballs. The people looking at this are computing types; while this boinc NFS project adapted an initial version set up by hackers for breaking RSA-keys on calculators (TI...). I'd probably best get the fermi cards back to gnfs polynomials. The current 15e project, G2p1195, uses a polynomial Greg found using their tessla cards. We've been working with the people that wrote the GPU code; and appear to have gotten a marginal improvement on the polynomial for the next project, 5M895. -Bruce |
|
20)
Message boards :
NFS Discussion :
3,607- factors
(Message 631)
Posted 9 Nov 2010 by bdodson* Post: Is this number be factored use degree 6, ... I'm somewhat curious as to which article you were reading; you're most likely careful about sources, but the phrase "I read it on the internet" (which you didn't use, I know) is often followed by info that's not very reliable. Another possible issue is that the 16e siever we're currently using has some improvements (and/or corrections) in the assembly code due to our friend Batalov. The initial source code of Franke/Kleinjung is not very portable, and notoriously intricate, so that even a usually reliable author may not have had the best code to work with. Establishing a well docummented public source of data is one of the points of this boinc project. There are very few public SNFS factorizations above difficulty 280; and the author is quite likely making use of relatively limited simulations, rather than examining the "entire sieving range yield". -bdodson |