Mersenne: Re: Trial Factoring: Back to the math.
Bruce Leenstra wrote: What this list needs right now is a nice juicy math debate, so here goes: I was reading the faq about P-1 factoring, and it talks about constructing a 'q' that is the product of all primes less than B1 (with some multiples?) ... Right now Prime95 constructs a list of possible factors, filters it (before hand, or on-the-fly) and then uses the powering algorithm to calculate 2^p - 1 (mod q) for each factor. Sandy Harris [EMAIL PROTECTED] replied: Off-the wall question dep't.: How does the overhead for that compare to just calculating q, the product of all the primes of interest, and then gcd(q, target)? If you get 1, then q and target have no common factors. If you get anything else, your result is the product of the common factors. Actually, that's not off the wall (or out of left field, as fans of baseball refer to it) at all. In fact, Richard Crandall mentions such a scheme in at least one of his books (either Pomerance Crandall or Crandall's "Projects in Scientific Computing" or both.) Here's how it compares to the sieve-based factoring: assume we have many candidate factors of the number 2^p-1, having size = q bits. (Precisely speaking, we require an O(1) fraction of these being O(q) in size, but that's a technicality.) Assuming q bits is on the order of a computer wordsize, to test each one of these separately requires O(log2(p)) CPU operations (i.e. the O(log2(p)) modular squarings of a binary powering algorithm.) Using the gcd-based method, we multiply roughly p/q of the factor candidates together to get a product of = p bits, then gcd with 2^p-1. The fastest known gcd algorithms need O(p * ((log2(p))^2), i.e. are O(log2(p)) times as expensive as an FFT-based big-integer multiply of numbers this size. (That doesn't seem too bad at first glance, but the O() hides a much larger proportionality constant than the FFT, as well.) Dividing by the number of candidates that get processed per gcd we see that this method needs O((log2(p))^2) operations, where we've absorbed the q (which is assumed to be order of unity, since a computer wordsize is such) into the implied proportionality constant. That makes this method asymptotically slower than one-factor-candidate-at-a-time sieving, and the added overhead of the fast gcd imposes an additional speed penalty. Thus, this method (which does have the advantage that it can use floating-point FFT for the large-integer multiplies of the fast gcd) would only become attractive if integer multiply were grindingly slow or if one were dealing with some kind of vector hardware which could do floating-point FFT screamingly fast but were somehow constrained to being able to do just O(1) integer multiplies per cycle. Not a likely combination, but it's an interesting theme nonetheless. Note that one advantage of the gcd-based method is that factoring cost doesn't depend overmuch on the hardware wordsize, since we can break the factor product into whichever-sized chunks are convenient for the FFT. For the sieving method, as soon as q exceeds the hardware wordsize by even a single bit, we get hit with a 3-4x speed penalty. But given that the gcd method is probably around 100x slower than sieving for q no larger than a wordsize, it's going to take some very large factor candidates indeed to make the gcd method attractive. But keep those off-the-wallers coming - it's that kind of thinking that often leads to real algorithmic breakthroughs! Cheers, -Ernst
Mersenne: Missing assignement
In my personal account report of yesterday could be read: *** Individual Account Report 11 Feb 2002 21:57 (Feb 11 2002 2:57PM Pacific) --- Exponents Assigned --- Assignment overdue check-in is set at 60.0 days (0.0 days to expire) prime fact current days exponentbits iteration run / to go / exp date updated date assigned computer ID Mhz Ver -- - - --- --- --- .. 14421269 66 21.2 143.8 66.8 21-Jan-02 16:08 PII350-RDIES 351 v19/v20 .. ** But now this exponent is missing. How is it possible?? Saludos, Ignacio Larrosa Cañestro A Coruña (España) [EMAIL PROTECTED] ICQ #94732648 _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: Missing assignement
Looks like someone finished it: 14421269 66 0x6E664B5F86CB66__12-Feb-02 08:04 Team_Prime_Rib DSheets_50 PS - I'm just thrilled because I found a factor of an exponent that beat my previous record... 101 bit factor. I'm too lazy to look through the cleared exponents list, so does anyone know what the largest factor is that has been found by GIMPS lately? Of course there may be smaller factors for the same exponent, but I'm still impressed at finding such a huge factor to an even much huger number. -Original Message- From: [EMAIL PROTECTED] [mailto:mersenne-invalid- [EMAIL PROTECTED]] On Behalf Of Ignacio Larrosa Cañestro Sent: Tuesday, February 12, 2002 11:11 AM To: [EMAIL PROTECTED] Subject: Mersenne: Missing assignement In my personal account report of yesterday could be read: *** Individual Account Report 11 Feb 2002 21:57 (Feb 11 2002 2:57PM Pacific) --- Exponents Assigned --- Assignment overdue check-in is set at 60.0 days (0.0 days to expire) prime fact current days exponentbits iteration run / to go / exp date updated date assigned computer ID Mhz Ver -- - - --- --- --- .. 14421269 66 21.2 143.8 66.8 21-Jan-02 16:08 PII350-RDIES 351 v19/v20 .. ** But now this exponent is missing. How is it possible?? Saludos, Ignacio Larrosa Cañestro A Coruña (España) [EMAIL PROTECTED] ICQ #94732648 _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Missing assignement
Well, someone did help you. The cleared exponents report contains the following line: 14421269 66 0x6E664B5F86CB66__12-Feb-02 08:04 Team_Prime_Rib DSheets_50 Regards Achim -Ursprüngliche Nachricht- Von: Ignacio Larrosa Cañestro [EMAIL PROTECTED] An: [EMAIL PROTECTED] Gesendet: Dienstag, 12. Februar 2002 20:10 Betreff: Mersenne: Missing assignement In my personal account report of yesterday could be read: *** Individual Account Report 11 Feb 2002 21:57 (Feb 11 2002 2:57PM Pacific) --- Exponents Assigned --- Assignment overdue check-in is set at 60.0 days (0.0 days to expire) prime fact current days exponentbits iteration run / to go / exp date updated date assigned computer ID Mhz Ver -- - - --- --- --- .. 14421269 66 21.2 143.8 66.8 21-Jan-02 16:08 PII350-RDIES 351 v19/v20 .. ** But now this exponent is missing. How is it possible?? Saludos, Ignacio Larrosa Cañestro A Coruña (España) [EMAIL PROTECTED] ICQ #94732648 _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: Missing assignement
Answering my own question: (guess I wasn't so lazy after all) 14517229 103 F 9924470843259440116293839391239 10-Jan-02 15:35 00dbm Bertrand -Original Message- From: [EMAIL PROTECTED] [mailto:mersenne-invalid- [EMAIL PROTECTED]] On Behalf Of Aaron Blosser Sent: Tuesday, February 12, 2002 11:41 AM To: [EMAIL PROTECTED] Subject: RE: Mersenne: Missing assignement Looks like someone finished it: 14421269 66 0x6E664B5F86CB66__12-Feb-02 08:04 Team_Prime_Rib DSheets_50 PS - I'm just thrilled because I found a factor of an exponent that beat my previous record... 101 bit factor. I'm too lazy to look through the cleared exponents list, so does anyone know what the largest factor is that has been found by GIMPS lately? Of course there may be smaller factors for the same exponent, but I'm still impressed at finding such a huge factor to an even much huger number. _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Re: Trial Factoring: Back to the math.
Bruce Leenstra wrote: What this list needs right now is a nice juicy math debate, so here goes: I was reading the faq about P-1 factoring, and it talks about constructing a 'q' that is the product of all primes less than B1 (with some multiples?) ... Right now Prime95 constructs a list of possible factors, filters it (before hand, or on-the-fly) and then uses the powering algorithm to calculate 2^p - 1 (mod q) for each factor. Sandy Harris [EMAIL PROTECTED] replied: Off-the wall question dep't.: How does the overhead for that compare to just calculating q, the product of all the primes of interest, and then gcd(q, target)? If you get 1, then q and target have no common factors. If you get anything else, your result is the product of the common factors. One of the advantages of testing each potential factor individually, or even in pairs, is you can stop when you find a factor. With the gcd method you are always testing a large number of factors. This would be great if you wanted to completely factor the composite mersennes, it probably _would_ be faster for that. You could study the distribution of factors, combine that with overhead costs and speed comparisons to come up with the optimum number of factors to test at a time. But if most of the factors are usually smaller, the gcd method would always end up being slower. Regards, Bruce Leenstra _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Missing assignement
And for all other readers all(?) factors with more than 99 bits which are part of the latest cleared exponents report: 12523547 101 F 3476706399795678069475753699633 12-Feb-02 12:30 madpoo MainBoy 12736037 102 F 6150891764095478416426904114537 14-Jan-02 23:03 krypt fmpc494 13459613 102 F 4522251312746653413939484232703 19-Jan-02 12:00 MartinTraupe Home-PC 14219963 102 F 4925463503955430092920404146711 27-Dec-01 01:06 ps8 psw1 14308961 103 F 9394020965332917865679071542783 23-Dec-01 05:42 mfaunce FaunceServer 14315593 103 F 7816072315472078791442581868599 03-Jan-02 21:06 Sastre ASCR 14334623 103 F 829467477289264041716715663 25-Jan-02 08:37 zyd C82FC3DE3 14378827 103 F 9393632720558083108841526201431 02-Jan-02 06:22 SPICER A_DB_RO_EV 14517229 103 F 9924470843259440116293839391239 10-Jan-02 15:35 00dbm bertrand 14542817 100 F 1733277749555116882783777187313 15-Jan-02 20:17 jrg784367 plymouth 14591887 102 F 6576880966001661739783384443777 29-Jan-02 20:39 enorris L686-500 14744689 102 F 4881000298247603867496587734103 01-Feb-02 02:22 S00113 ardberandi.i 7317397 102 DF 4744532441925713497725815155457 04-Feb-02 20:40 shaneamy P4 7432517 101 DF 2885846120940443247382268170072 19-Jan-02 07:51 jocelynl Alba2 7456061 102 DF 4556983583431181768908045590841 19-Jan-02 02:47 TempleU-DI CJLab513 12789479 102 DF 6603803731240827668876448164239 16-Dec-01 12:56 akemg C5641719B Regards Achim PS: hope I didn´t miss one. -Ursprüngliche Nachricht- Von: Aaron Blosser [EMAIL PROTECTED] An: [EMAIL PROTECTED] Gesendet: Dienstag, 12. Februar 2002 21:06 Betreff: RE: Mersenne: Missing assignement Answering my own question: (guess I wasn't so lazy after all) 14517229 103 F 9924470843259440116293839391239 10-Jan-02 15:35 00dbm Bertrand -Original Message- From: [EMAIL PROTECTED] [mailto:mersenne-invalid- [EMAIL PROTECTED]] On Behalf Of Aaron Blosser Sent: Tuesday, February 12, 2002 11:41 AM To: [EMAIL PROTECTED] Subject: RE: Mersenne: Missing assignement Looks like someone finished it: 14421269 66 0x6E664B5F86CB66__12-Feb-02 08:04 Team_Prime_Rib DSheets_50 PS - I'm just thrilled because I found a factor of an exponent that beat my previous record... 101 bit factor. I'm too lazy to look through the cleared exponents list, so does anyone know what the largest factor is that has been found by GIMPS lately? Of course there may be smaller factors for the same exponent, but I'm still impressed at finding such a huge factor to an even much huger number. _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factoring top 10
Hi, At 11:41 AM 2/12/2002 -0800, Aaron Blosser wrote: PS - I'm just thrilled because I found a factor of an exponent that beat my previous record... 101 bit factor. I'm too lazy to look through the cleared exponents list, so does anyone know what the largest factor is that has been found by GIMPS lately? The top 10 - 39 digits for the biggest! 1433462339 56379662829467477289264041716715663 1318781335 63113922700063643342764849026462401 1075012734 4777866348588447235992766781311399 1293216734 4314676575733979321708362055504719 1050634734 2529967840093210987185485731119337 1345961334 2004522251312746653413939484232703 1454281734 1001733277749555116882783777187313 1234882933 972299186932443166370257195895087 1437882733 749393632720558083108841526201431 1311127132 35439060242916356936579100907769 _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factoring bits
Hi, At 09:18 PM 2/12/2002 +0100, Achim Passauer wrote: And for all other readers all(?) factors with more than 99 bits which are part of the latest cleared exponents report: 14308961 103 F 9394020965332917865679071542783 There are two minor shortcoming in the prime95 to primenet protocol. It reports the first 32 digits of a found factor. Thus, the report will never display more than 103 bits as the length of the found factor. Also if P-1 finds a composite factor prime95 reports this as one gigantic factor rather than two smaller factors. Naturally, this is all cleared up when it is entered into the master database. Its just that the primenet server reports can be a little misleading. _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: RE: Factoring top 10
Okay, those are HUGE factors. Have the predictions on the work eliminated by P-1 factoring been pretty much confirmed by the # of large factors found? In other words, is the extra processing time paying off? I'd hazard a guess that the time saving is indeed appreciable, but I wonder if anyone has done some cold hard stats on it. -Original Message- From: George Woltman [mailto:[EMAIL PROTECTED]] Sent: Tuesday, February 12, 2002 12:33 PM To: Aaron Blosser; [EMAIL PROTECTED] Subject: Factoring top 10 Hi, At 11:41 AM 2/12/2002 -0800, Aaron Blosser wrote: PS - I'm just thrilled because I found a factor of an exponent that beat my previous record... 101 bit factor. I'm too lazy to look through the cleared exponents list, so does anyone know what the largest factor is that has been found by GIMPS lately? The top 10 - 39 digits for the biggest! 1433462339 56379662829467477289264041716715663 1318781335 63113922700063643342764849026462401 1075012734 4777866348588447235992766781311399 1293216734 4314676575733979321708362055504719 1050634734 2529967840093210987185485731119337 1345961334 2004522251312746653413939484232703 1454281734 1001733277749555116882783777187313 1234882933 972299186932443166370257195895087 1437882733 749393632720558083108841526201431 1311127132 35439060242916356936579100907769 _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Preventing hacks
Well, After long and hard thought on this (approximately 30 seconds), I have the following suggestion: Each team account (could apply to accounts with just one machine as well) should have 2 passwords. A master password that could be used on the web pages to manage exponents on all team machines, and also a per-machine password (could be automatically generated when a new machine gets an exponent). There's really no reason I can think of why a password would be required to have a machine join a team, is there? I mean, someone could sign their machine up to some team and reserve a bunch of exponents with no intention of working on them, but hey, someone could do that anyway right now by just setting up their own team... So a team account master password could unreserved exponents on any machine, and then the machine password could be used to work with exponents for only that one machine. Well, at any rate, that would keep individual team members from wreaking havoc by this shared password scheme currently in place, while still allowing a team leader to unreserve exponents or do other things from the web page. Just a thought, and again, this is just my 30-second attempt to come up with an idea. I'm sure it can and will be improved upon. Aaron (aka I'm-not-a-hacker-I'm-a-math-geek) -Original Message- From: [EMAIL PROTECTED] [mailto:mersenne-invalid- [EMAIL PROTECTED]] On Behalf Of George Woltman Sent: Tuesday, February 12, 2002 12:29 PM To: [EMAIL PROTECTED] Subject: Re: Mersenne: Missing assignement Hi all, At 08:10 PM 2/12/2002 +0100, Ignacio Larrosa Cañestro wrote: In my personal account report of yesterday could be read: Assignment overdue check-in is set at 60.0 days (0.0 days to expire) But now this exponent is missing. How is it possible?? OK, the cat is out of the bag. In late January, one of the more productive teams was hacked. Prime95/Primenet has some security holes. One of these holes is that a team must make its password public for new members to join. Someone exploited this hole. This loser thought it would be cute to unreserve all the team's exponents (a few hundred) via the manual web pages. Brad Scott patched the manual forms and embarked on implementing a more permanent solution. A week ago, they struck again using prime95 itself to again unreserve some of the team's exponents. Unfortunately, rather than hurting the team, the hacker ended up hurting ordinary users. The server reassigned all the unreserved exponents. Since the team's computers had a head start on these exponents they are likely to finish them first. When they report a result, your assignment will disappear from the active assignments list. GIMPS, of course, can use your result for double-checking. Brad/Scott have now changed server so that none of this team's exponents can be unreserved. They are still working on making this feature available to all teams to prevent this in the future. Brad Scott are better able to comment on this, but I think that this is the first hacker attack on the reservation system. There have been many denial of service attacks and attempts at defacing the web pages (don't people have better things to do with their time?) Are there other security holes? Yes. For obvious reasons I don't know if we should discuss these in a mailing list. Beefing up security costs time and money. These are limited resources in an all-volunteer, not-for-profit, zero-revenue project. We'll try to do the best we can given our limitations. Always remember GIMPS is just for fun, George _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: RE: Factoring top 10
On 12 Feb 2002, at 12:41, Aaron Blosser wrote: Have the predictions on the work eliminated by P-1 factoring been pretty much confirmed by the # of large factors found? In other words, is the extra processing time paying off? I'd hazard a guess that the time saving is indeed appreciable, but I wonder if anyone has done some cold hard stats on it. Small sample, just my current account report: 15 factors found - 11 trial factoring, 4 P-1 on LL assignments, 0 P-1 on DC assignments 49 LL assignments 42 DC assignments completed - almost all of the LL assignments and about half of the DC assignments most of these have included the P-1 factoring phase. So it looks as though running P-1 on DC assignments has been wasteful, but on the other hand one shouldn't expect to get many successes with a predicted factoring rate of around 2% and a sample size of only about 20. Conversely, with a predicted factoring rate of around 5%, I've found almost twice as many factors as expected when running P-1 prior to LL assignments. On balance, I'm beating the odds - the factors I've found by running P-1 prior to LL DC assignments have saved about 3.5 times the amount of time I've put into running P-1. Regards Brian Beesley _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Preventing hacks
On 12 Feb 2002, at 13:21, Aaron Blosser wrote: After long and hard thought on this (approximately 30 seconds), I have the following suggestion: Each team account (could apply to accounts with just one machine as well) should have 2 passwords. A master password that could be used on the web pages to manage exponents on all team machines, and also a per-machine password (could be automatically generated when a new machine gets an exponent). That sort of works - but it's messy, and makes it hard for an individual team member to unreserve an exponent for some legitimate reason. A better solution is to have every PrimeNet client identified in three ways: system id, user name team name. Team name blank means the user is not a participant in any team. The password is associated with the user name, not the team. Now the user can do what the hell (s)he likes with his/her own assignments, but cannot bugger up assignments belonging to other team members. A side effect of implementing this is that team members can desert (maybe joining a different team) even in the middle of an assignment, so team total CPU time could not be computed by simply adding the CPU time contributed by current members. Instead it would be neccessary to keep seperate running totals for each named team, adding the contribution from each completed assignment to whichever team the user is currently attatched to (instead of, or as well as, to the individual user?) as and when results are submitted. In late January, one of the more productive teams was hacked. Prime95/Primenet has some security holes. One of these holes is that a team must make its password public for new members to join. Someone exploited this hole. This loser thought it would be cute to unreserve all the team's exponents (a few hundred) via the manual web pages. Brad Scott patched the manual forms and embarked on implementing a more permanent solution. A week ago, they struck again using prime95 itself to again unreserve some of the team's exponents. Unfortunately, rather than hurting the team, the hacker ended up hurting ordinary users. The server reassigned all the unreserved exponents. Since the team's computers had a head start on these exponents they are likely to finish them first. When they report a result, your assignment will disappear from the active assignments list. GIMPS, of course, can use your result for double-checking. So there's no loss at all, for LL assignments. Brad/Scott have now changed server so that none of this team's exponents can be unreserved. They are still working on making this feature available to all teams to prevent this in the future. As I pointed out above, there may be legitimate reasons for an individual team member to unreserve their own assignments. Brad Scott are better able to comment on this, but I think that this is the first hacker attack on the reservation system. There have been many denial of service attacks and attempts at defacing the web pages (don't people have better things to do with their time?) I think _every_ web site sees attempts to do such things. Some morons apparently consider operational, undefaced web sites in the same way as graffiti artists see a blank wall. Expect also to see sustained probing to find any of the large number of known vulnerabilities in software and/or insecure misconfigurations common to various web servers. Regards Brian Beesley _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Are problems more likely in the last 1% of a 10 gigadigit LL?
HELP! Until this evening I was expecting to see my first result from a LL test on a 10,000,000-digit Mersenne number tomorrow morning. When I got home from dinner tonight I was seeing a bunch of suminputs != sumoutputs, and after rebooting, the errors switched to round off [4] 0.40 Was I just unlucky about timing, with only about 0.3% left, or is there something systematic that could cause this, or any other guesses? Or did my stupid PC just decide to take now to blow it? As far as I know, the previous part of the LL was trouble-free. W98, Prime95 V2 21.2.1. 1.3 GHz P4, 384 MB RAM I am bummed. Any guess--RAM, CPU, Thanks for advice or condolences. Gerry -- mailto:[EMAIL PROTECTED] Gerry Snyder, AIS Director Symposium Chair, Region 15 RVP Member San Fernando Valley, Southern California Iris Societies in warm, winterless Los Angeles--USDA 9b-ish, Sunset 18-19 my work: helping generate data for: http://galileo.jpl.nasa.gov/ _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
