Mersenne Digest Sunday, March 11 2001 Volume 01 : Number 827 ---------------------------------------------------------------------- Date: Sun, 11 Mar 2001 17:21:25 -0500 From: Nathan Russell <[EMAIL PROTECTED]> Subject: Re: Mersenne: Ways to increase recruitment. On Sun, 11 Mar 2001 12:03:47 -0500, Joshua Zelinsky wrote: >The vast majority of computers still aren't doing any form of distributed >computing. Here are a few suggestions to help increase GIMPS participation: > >1. Get people at major universities + colleges to become "active >recruiters," posting messages on announcement boards, talking to friends and >faculty. We should all be doing this sort of stuff anyways, but if we could >get people to volunteer/coordinate efforts, we might get a lot out of it. I've always discussed GIMPs with my friends, in and out of college. I think the problem is that it's harder to understand what GIMPS actually does than it is with, e.g., seti@home. >2. Give people/teams some form of credit for recruiting people. This could >be done as competition separate from the main one, or somehow connected. We >could probably have people list an option of listing a "sponsor" or >"sponsors" already on GIMPS when they join. Competition almost always makes >things work better. GIMPS has never worked that way, nor has any (not-for-profit) distributed computing project of which I am aware. In fact, the only programs I am aware of that /do/ work that way are for-profit distributed computing efforts like processtree, and earn-for-surfing programs. >3. Post periodic announcements to sci.math and other discussion groups. In >particular, if someone asks a question about Mersenne primes someone should >answer it and throw GIMPS in as well. I'm alrwady doing this, but I can't >get every group. If we organize to split them up, assigning different groups >to different people, it might help out a lot. That's an interesting idea - the only concern is making sure the 'periodic announcements' aren't resented by the users of said groups. > >Sincerely, >Joshua Zelinsky >[EMAIL PROTECTED] Nathan _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 11 Mar 2001 23:32:03 +0100 From: "Martijn Kruithof" <[EMAIL PROTECTED]> Subject: RE: Mersenne: Security of prime95 + electricity costs. I have verified the possibility of a buffer overflow exploit in primenet.c (used in linuxs mprime) It seems NOT vurneralbe (so it seems safe to me) NO buffer overflow is likely to occur. Notwithstanding I am running mprime as user mersenne with virtually no rights and no shell. _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 12 Mar 2001 00:20:12 +0100 From: Alexander Kruppa <[EMAIL PROTECTED]> Subject: Re: Mersenne: prime95 - v21 progress "Brian J. Beesley" wrote: > (1) Removing these assignments from PrimeNet and managing them > seperately. Anyone who is prepared to make special arrangements to > acquire these assignments is unlikely to default by reason of lack of > commitment. Someone is (or was?) doing something similar - David Campeau (sp?), aka diamonddave, who set up scripts to grab small exponents right after the Primenet servers recycle run and completed them in ascending order of size. And boy, did he get flamed for it. Right, flamed - because some only looked at the 20 or so small exponents he had reserved and tought he was holding them back. Maybe those who complain about slow "linear" progress could take on a similar approach? (except for the getting flamed part, I hope.) Write a script that (or get up early/stay up late to) get exponents right after the servers recycle run and immediately release the biggest ones so you have enough work for, say, 30 days. Maybe David can help with the scripts or general tips for maintaining the exponents list, *especially* safe guards so that reserved exponents dont pile up in an uncontrolled manner. If everyone sticks to the rules - donīt poach, dont hog exponents - this should solve most of the problem with the least possible hassle. Those who want to see milestones soon can help to get there, the rest can just go on with their regularly assigned work. This doesnīt help with the exponents that are currently reserved with a expected run time of several years - but if the user abandons them, the server will recycle them 60 days after the last update from the user which doesnīt seem like an overly long delay for the project. If the users chooses to complete the exponent on a slow machine or on a machine that is not in use very often, then I donīt see why he shouldnīt be allowed to do so, delaying a milestone or not. Ciao, Alex. _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 11 Mar 2001 16:21:58 -0600 From: [EMAIL PROTECTED] (Mikus Grinbergs) Subject: Re: Mersenne: Security of prime95 + electricity costs. On Sun, 11 Mar 2001 20:11:33 -0000 "Daran" <[EMAIL PROTECTED]> wrote: > Hi all. I'm new to the list, but I've been GIMPING for just over two years. > I'd been thinking about possible security risks myself just before I joined > the list, so it's a bit of a coincidence that this was the first thread I > read. Let me suggest there are two situations to be evaluated for exposure: 1. Attacks using the Prime95 communication protocols - I believe it is the CLIENT that initiates all GIMPS communications. In other words, there is __no__ daemon which is listening to random incoming messages. (Buffer overflow attacks are usually directed at programs which accept messages from anywhere on the internet.) To make use of the GIMPS communication protocols, the attacker might have to WAIT for the user's Prime95 program to initiate contact, and would then have to SPOOF being the Primenet server. In my opinion, there are easier pickings on the 'net for attacks. In my opinion it would be easier to spoof the "Manual Entry" Primenet server, which uses a browser interface rather than the "below-the-covers" interface of the Prime95 client. But the risk of using a browser to access Primenet should be no greater than the risk of using a browser to access any other site on the 'net. 2. Attacks facilitated by being on-line in the first place - I cut my teeth at distributed computing with the RC5 project, which has much shorter reporting intervals. Because I live in the boonies, I do __not__ have a reliable connection to the 'net. I found that allowing RC5 (or Prime!) to AUTOMATICALLY connect to the server would randomly become a horror story (my name for the spectacle is to call it a "stark-raving-mad dialer" aberration). So for BOTH projects, my computers have run OFF-LINE, and WITHOUT any automatic reporting or check-in. When I need new work, I connect to the internet, then connect to the server, then communicate, then disconnect. That does not leave much time for an attacker to start probing my ports, or to send ovesize buffers. The good part about both RC5 and GIMPS is that work assignments can be downloaded "ahead of use" (that is, at a time when I have verified that my connection is good, rather than at a time when the computer has reached a certain point). I've looked at some other distributed networks - they only send the next unit after the previous unit is completed - participants in such a network might "run out of work to do" if they happen to be off-line. My opinion: Compared to someone who is off-line most of the time, someone who chooses to stay connected in order to participate in a distributed project __will__ be at security risk of being attacked, MERELY because there exists an IP-address to be probed. The ONLY help I know of is to interpose the most paranoid firewall one can find !!! mikus _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 11 Mar 2001 18:48:51 -0500 From: Nathan Russell <[EMAIL PROTECTED]> Subject: Re: Mersenne: Security of prime95 + electricity costs. On Sun, 11 Mar 2001 23:32:03 +0100, Martijn Kruithof wrote: >I have verified the possibility of a buffer overflow exploit in primenet.c >(used in linuxs mprime) >It seems NOT vurneralbe (so it seems safe to me) >NO buffer overflow is likely to occur. > >Notwithstanding I am running mprime as user mersenne with virtually no >rights >and no shell. I wish I had that option. My mprime runs from my Windows drive, and needs to be able to access other files in the GIMPS directory. I can't see any way to do this without giving it access to the entire windows drive, but that doesn't greatly worry me since the same is true of every program I run under Windows. Nathan _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 11 Mar 2001 18:51:01 -0500 (EST) From: Jason Stratos Papadopoulos <[EMAIL PROTECTED]> Subject: Mersenne: Primitive roots for Galois transforms? Hello again. After working out how to do integer FFTs on the Alpha, I'm considering additional code that uses Fast Galois Transforms (FGTs), e.g. for complex integers in GF(p^2) for p a prime congruent to 3 mod 4. Bill Daly mentioned this idea before on the list (end of 1998) but unfortunately didn't give enough details for me to work out the rest. I'm considering a 64-bit version for the Alpha and maybe a 32-bit version using MMX and two primes on the Pentium. As usual, though, I need some pointers with the theory. The first big question is how you find a primitive root for transforms of this type. Richard Crandall gives a closed-form expression when p is a Mersenne prime, but if I'm not using a Mersenne prime for p I would still need primitive roots. The next question involves eighth-roots of 1 modulo p. For FFTs in complex numbers, these eighth roots have a special form that need less arithmetic than a complex multiply. Is this also the case in GF(p^2) for general p? Or do you need a special primitive root to get these savings? In principle, an eighth-root of this form could mean a radix-8 FGT is possible that uses no integer multiplies. Finally, how in blazes do you find a root of two with these strange complex integer things? I managed to answer this halfway by myself for more conventional integer FFTs, but I have no clue where to begin here. In a more general sense, if someone can manage Pentium-optimized all-integer convolution code that's within a factor of two of the speed of Prime95, could it be used as an alternative for double-checking? Would there be any interest in such code? Thanks in advance, jasonp - ---------------------------------------------------------------------- >From [EMAIL PROTECTED] Date: Wed, 16 Dec 1998 21:08:46 -0500 From: Bill Daly <[EMAIL PROTECTED]> To: "[EMAIL PROTECTED]" <[EMAIL PROTECTED]> Subject: Mersenne: Integer FFT The usual concept of an integer FFT is to choose a prime q such that q-1 is divisible by a reasonably large power of 2, say N = 2^n, find a primitive (integer) N-th root of 1 mod q, say w, then use w and arithmetic mod q to calculate the FFT. If it also happens that there is an integer N-th root of 2 mod q, then the FFT can be converted into a DWT suitable for implementing multiplication mod 2^p - 1 for some large prime p. For example, with q = 2^64 - 2^32 + 1, we have both roots for N up to 2^26, and for that matter we can also use an FFT/DWT of order N = 5*2^n up to 5*2^26. However, this requires calculating products of the form a*b mod q where a and b are 64-bit integers, which, while straightforward, will probably take more time than the corresponding complex floating-point multiply in the ordinary FFT/DWT. It is also hard to find appropriate primes q for which this works. Richard Crandall has proposed implementing an FFT in the Galois field GF(q^2), where q is itself a Mersenne prime, e.g. q = 2^61 - 1. He calls this the fast Galois transform (FGT). The idea is that for any prime q = 3 mod 4, the field of Gaussian integers a + b*i mod q is isomorphic to GF(q^2), thus we can simply replace complex real values with complex integers mod q. The multiplicative order of GF(q^2) is q^2-1, thus for q = 2^61 - 1, q^2 - 1 will be divisible by 2^62, thus we can find a complex integer w such that w^2^62 = 1. Also, since the order of 2 in GF(q^2) is 61, there will also be a value r such that r^2^62 = 2. We can use r and w to implement a complex integer DWT mod q, which requires code to add, subtract and multiply mod q. However, we still have the problem that the calculation of a*b mod q is likely to take more time than we would really like. I have a suggestion. The FGT requires only a prime q = 3 mod 4, for which q+1 is divisible by a reasonably large power of 2. Let's consider primes q = k*2^n - 1 which are slightly less than 2^32. The idea here is that this will require only 32-bit integer arithmetic. If we use two such primes, q1 and q2, and we calculate separately the two sets of convolution sums z1[0..N-1] mod q1 and z2[0..N-1] mod q2, then we can use the Chinese Remainder Theorem to calculate the convolution sums z[0..N-1] mod q1*q2. This is less difficult than it might seem, since we can precalculate values u1 and u2 such that u1 = 1 mod q1, u1 = 0 mod q2, u2 = 0 mod q1, u2 = 1 mod q2. Then if we have, from the two FGT calculations, values z1[j] and z2[j] such that z[j] = z1[j] mod q1 and z[j] = z2[j] mod q2, we have z[j] = u1*z1[j] + u2*z2[j] mod q1*q2, which is easily verified to be correct. This calculation can be further simplified because of the fact that u1 + u2 = 1 mod q1*q2 (in fact, u1 + u2 = q1*q2 + 1). Thus, (u1+u2)*(z1[j]+z2[j]) = z1[j]+z2[j] mod q1*q2, and z[j] = u1*z1[j] + u2*z2[j] = (z1[j] + z2[j] + (u1-u2)*(z1[j]-z2[j])) / 2 mod q1*q2. This requires only a single multiply (u1-u2)*(z1[j]-z2[j]) mod q1*q2, together with some shifts and adds mod q1*q2. The rationale for this is that the efficacy of an integer FFT depends on the size of the modulus. If the modulus is slightly less than 2^32, then for N in the range used by GIMPS we may be able to use only 6-bit coefficients, whereas with a modulus slightly less than 2^64, in this case q1*q2, we will be able to use 22-bit coefficients, thereby increasing the range of validity by a factor of nearly 4, in exchange for using two FGTs instead of one and the Chinese Remainder step at the end of each iteration. It is worth noting also, in the particular case of the Pentium, that there is an efficient method of calculating a*b mod q, for q < 2^32, using the floating-point unit. This is nice because FMUL is faster than MUL on the Pentium, and because we can interleave integer adds and subtracts mod q with floating-point multiplies mod q. Here is a concrete example for N = 3*2^18: N-th root of 1 N-th root of 2 q1 4293525503 2908044543+2957159114*i 960683048 q2 4292083711 4225761219+3412039801*i 1768092337 With these values, we can construct an FGT for both q1 and q2. To obtain the convolution sum z[j] from z1[j] and z2[j], we have u1 = 11727005047594504564 u2 = 6701165826594877070 q1*q2 = 18428170874189381633 u1-u2 = 5025839220999627494 We then multiply (u1-u2)*(z1[j]-z2[j]), which is the product of a signed 63-bit number by a signed 32-bit number. It is best to save the signs of u1-u2 and z1[j]-z2[j] and use their absolute values, since a 64x32 unsigned multiply can be implemented with two 32x32 unsigned multiplies to produce a 96-bit unsigned result. Reducing this mod q1*q2 is a bit messy but doable; essentially, we want to use the FPU to calculate an estimate of floor(product/q1*q2), then reduce product to product - floor(product/q1*q2)*(q1*q2), then if necessary iterate until the result is reduced mod q1*q2. Then, depending on the saved signs, we either add or subtract this product from z1[j]+z2[j] mod q1*q2 and halve it, again mod q1*q2, to obtain z[j]. Note that, as is the case for the complex floating-point DWT, the N-th root of 2 for the FGT is a real number. Thus, scaling by powers of the N-th root of 2 requires multiplying a real integer by a complex integer, which is more efficient than a full complex multiplication. Regards, Bill _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 11 Mar 2001 16:06:28 -0800 From: "Stephan T. Lavavej" <[EMAIL PROTECTED]> Subject: Mersenne: Re: Mersenne Digest V1 #826 Hey, > 1. Get people at major universities + colleges to become "active > recruiters," posting messages on announcement boards, talking to friends and > faculty. We should all be doing this sort of stuff anyways, but if we could > get people to volunteer/coordinate efforts, we might get a lot out of it. Hmmm, that is a good idea. I will try to remember to design a little poster on a sheet of paper and post some copies around campus before 3rd term starts at Caltech. - -*---*------- Stephan T. Lavavej _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 11 Mar 2001 18:25:39 -0600 From: "Steve" <[EMAIL PROTECTED]> Subject: Re: Mersenne: prime95 - v21 progress I said the idea to set the DEFAULTS lower was a good one. Anyone who is serious about the project could very easily change those defaults. I have several machines with dialup access which don't connect with the server for weeks at a time, but a 7-day default would not affect me in the least. I change the settings on each machine depending on its circumstances; I have some set for 39 days. (Even a 1-day default wouldn't bother those machines, but I did say I thought 7 days might be a little drastic.) The people who abandon exponents are the ones who would not bother changing the defaults, hence returning them sooner. Steve Harris - -----Original Message----- From: Brian J. Beesley <[EMAIL PROTECTED]> To: Steve <[EMAIL PROTECTED]> Cc: [EMAIL PROTECTED] <[EMAIL PROTECTED]> Date: Sunday, March 11, 2001 2:44 PM Subject: Re: Mersenne: prime95 - v21 progress On 11 Mar 2001, at 7:55, Steve wrote: > >> Another solution that will work: Have as default a 7 day check in period > >> at most and only a grace period > >> of 7 days (not 60). Let the user set the check in period to a higher > >> value only via the expert menu and > >> after results have been checked in. That way abandoned exponents get > >> released in 14 instead of 80 days. > > > >That idea sounds the least painful of all that have been discussed so far > >(to me at least), and since the discussion of what people want in a new > >version of Prime95 has also been floating arround... this sounds like a > good > >suggestion to be submitted. It would not only take care of a problem, but > >would also not be so harsh to those who own slower machines. A win-win > >situation from those points of view. Great idea, Martijn!! > > I agree this is a good idea, although the 7-day grace period may be a little > drastic. But even reducing that just from 60 to 30 days (along with a 7-day > default check in) would release abandoned exponents in 37 days instead of > 88. This would recycle them more than twice as fast, greatly enhancing the > odds of someone eventually getting the assignment who will actually finish > it. The downside is that there would probably be a great increase in the number of assignments which are still running but don't complete before the expiry date. Clearly there is a balance to be struck somewhere, but 7 days seems to me to be _ludicrously_ short. In fact, as assignments take progressively longer to run, the "grace period" should be extending, rather than contracting. We should also bear in mind the very valuable contributions made by those people who do not have permanent (or near-permanent) network connections, and those people who are using clients without the PrimeNet communication protocol. Requirement to check in frequently is off-putting to these people. (Some would put it a lot stronger than that!) I don't think we want to risk driving these people out of the project. > As others have mentioned, the problem is NOT slow machines but > rather abandoned exponents, which has nothing to do with machine speeds. I fail to see how reducing the check-in interval would have any impact on the "problem". Those people who are checking in every 28 days aren't running into the 60-day expiry deadline. The 60 day expiry value is a server parameter, not a client parameter. In any case, as I explained above, I think that a drastic reduction in the value would be dangerous. Might I suggest a couple of alternative approaches. Both of these would require the identification of exponents which are "seriously lagging" - perhaps the 100 smallest outstanding LL and the 100 smallest outstanding DC assignments. (1) Removing these assignments from PrimeNet and managing them seperately. Anyone who is prepared to make special arrangements to acquire these assignments is unlikely to default by reason of lack of commitment. (2) Alternatively, awarding double PrimeNet CPU time credit for the completion of these assignments. The downside to this is that, as well as requiring changes to the server software, recycled "small" exponents would have to be released at random times of the day, to prevent them being systematically "grabbed" by a few users. Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 11 Mar 2001 19:27:35 -0500 From: Nathan Russell <[EMAIL PROTECTED]> Subject: Re: Mersenne: Security of prime95 + electricity costs. On Sun, 11 Mar 2001 19:59:56 -0000, Brian J. Beesley wrote: >On 11 Mar 2001, at 8:59, Martijn wrote: > (BIG snip) >> and would the temperature of an idle >> system not be lower than that of a system running mprime/prime95 > >Yes, but you have to engineer the cooling to cope with the worst >possible case. However many laptops appear to turn on an extra >cooling fan almost immediately a program which makes use of the FPU >starts. My desktop does the same - the sound changes noticably when a distributed computing program is running. Nathan Russell _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 12 Mar 2001 07:19:26 +0100 (MET) From: [EMAIL PROTECTED] Subject: Re: Mersenne: Primitive roots for Galois transforms? Jason Stratos Papadopoulos <[EMAIL PROTECTED]> writes > Hello again. After working out how to do integer FFTs on the Alpha, I'm > considering additional code that uses Fast Galois Transforms (FGTs), > e.g. for complex integers in GF(p^2) for p a prime congruent to 3 mod > 4. Bill Daly mentioned this idea before on the list (end of 1998) but > unfortunately didn't give enough details for me to work out the rest. > I'm considering a 64-bit version for the Alpha and maybe a 32-bit version > using MMX and two primes on the Pentium. As usual, though, I need some > pointers with the theory. > > The first big question is how you find a primitive root for transforms of > this type. Richard Crandall gives a closed-form expression when p is a > Mersenne prime, but if I'm not using a Mersenne prime for p I would still > need primitive roots. Assuming the prime p is fixed at compile time, you can specify a primitive root g (of prder p-1) in the binary. You can try g = 3, 5, 7, ... until you succeed. You will need the prime factorization of p-1 when you test whether g is really a primitive root, but that is easy for 64-bit values of p. A symbolic algebra program such as Maple can assist you in the calculation. Later, if you want to do an FFT of length n where n divides p-1, your primitive root (of order n) can be g^((p-1)/n) (mod p). > The next question involves eighth-roots of 1 modulo p. For FFTs in complex > numbers, these eighth roots have a special form that need less arithmetic > than a complex multiply. Is this also the case in GF(p^2) for general p? > Or do you need a special primitive root to get these savings? In > principle, an eighth-root of this form could mean a radix-8 FGT is > possible that uses no integer multiplies. Over GF(p^2) the primitive root g will have order p^2 - 1 rather than p-1. Again a small search will suffice. You raise this to the power (p^2 - 1)/n where n divides p^2 - 1. If p == 7 (mod 8), then there exists a value sqrt(1/2) in GF(p) such that 2*sqrt(1/2)^2 == 1 (mod p). The primitive 8th roots of 1 modulo p are +- sqrt(1/2) +- i*sqrt(1/2), just as in the complex case. You can optimize (a + b*i) * (sqrt(1/2) + i*sqrt(1/2)) to (a - b)*sqrt(1/2) + i*(a + b)*sqrt(1/2) (with two multiplications modulo p), just as in the complex case. > Finally, how in blazes do you find a root of two with these strange > complex integer things? I managed to answer this halfway by myself for > more conventional integer FFTs, but I have no clue where to begin here. Assume p == 7 (mod 8). Then 2 is a square mod p, but -1 is not. The two values of sqrt(2) will be negatives of each other. Exactly one of these will itself be a square; select that value for sqrt(2). Then choose sqrt(sqrt(2)) to itself be a square. Continue until you have the root you want. In other words, if n is a power of 2, you are looking for a value x mod p such that x^((p-1)/2) == 1 (mod p) x^n == 2 (mod p) The last argument shows that a common solution exists. The exponents n and (p-1)/2 are coprime. If n*n' == 1 (mod (p-1)/2), then x == 2^(n') (mod p). When n is not a power of 2, such as if p was chosen with p == 1 (mod 105) to allow transforms of lengths 3, 5, 7, then you will need to check (when p is chosen at compile time) whether 2 is an appropriate power. Ernst Mayer and I exchanged many mailings about using GF(p^2) when p = 2^61 - 1. I thought he had implemented it, as part of a mixed integer/complex FFT. Peter Montgomery _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 12 Mar 2001 07:56:25 +0100 From: "Shot" <[EMAIL PROTECTED]> Subject: Mersenne: Quitting GIMPS Hello. Please, ready your stones/curses/mail viruses ready - I'm quitting GIMPS. Well, not exactly. I plan on switching from GIMPS to distributed.net's search for Optimal Golomb Rulers for about month or two, and consider differencies and similarities of these two projects. If you're interested why I'm switching - please, read on, if not - please, answer my (easy) question and you're free to read other mail. ;?) Question: from reading readme.txt I understood that when I select Advanced | Quit GIMPS tomorrow night (after the end of the M11567513 test) I'll return all the queued work, but still be able to rejoin GIMPS at a later time, right? Reasons I started looking for another distributed project (in no particular order): - - LL tests take a long time to complete. Current exponent will take four months on my machine - a little too much for me. Yes, I know, I can do double checks of factor, but, let's face it - _for me_ double checks are not *that* thrilling, and only 10% of factoring time is 'counted' (right?). - - Errors. I recently added some more RAM to my computer, and the first module I bought was bad - before I managed to run the torture test it affected (or not) my four months of searching with sum(inputs) != sum(outputs) and round off errors. It was my mistake (I should've turned Prime95 off before inserting the new RAM), but it was unreversable. - - Ranking. Well, distributed.net's way of counting work is much more 'sexy' - in distributed.net I'll be returning work much more often, and I'll get credited for it every day. Maybe if PrimeNet could count every iteration (and switch for daily, instead of hourly, statistics - there are reasons for doing it), or we could come with some other way to credit work more often... - - Money. No, I'm not in it for money - OGR is the only distributed.net's project that has no cash prize. At least that much... ;?) Any comments to above are welcome - I'm not going to quit reading GIMPS mailing list (at least not it the list moderator decides to unsubscribing me). ;?) I'll try to write a letter in a month or two with my thoughts about differencies between GIMPS and OGR search. Cheers, - -- Shot - -----------------------------------------------> http://shot.prv.pl/ GCS/CC/IT/O d- s:>+: a-->? C++(+++) ULS P+ L(+) W++>$ N>++ w(--) PS+(++) PGP- t 5 X- R tv- b++>+++ DI D G++ e>* h-->--- r++>+++ y+** - ---------------------> Geek Code Decoder: http://www.ebb.org/ungeek/ I think there is a world market for maybe five computers. - -- Thomas Watson, IBM chairman, 1943 _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 12 Mar 2001 01:58:50 -0500 (EST) From: Jason Stratos Papadopoulos <[EMAIL PROTECTED]> Subject: Re: Mersenne: Primitive roots for Galois transforms? On Mon, 12 Mar 2001 [EMAIL PROTECTED] wrote: > Assuming the prime p is fixed at compile time, you can specify > a primitive root g (of prder p-1) in the binary. You can try g = 3, 5, 7, ... > until you succeed. You will need the prime factorization of p-1 > when you test whether g is really a primitive root, but that is > easy for 64-bit values of p. A symbolic algebra program > such as Maple can assist you in the calculation. > > Later, if you want to do an FFT of length n where n divides p-1, > your primitive root (of order n) can be g^((p-1)/n) (mod p). <Blush> this is exactly the same as the more conventional number-theoretic transforms. I promise to think next time before asking. Doesn't the above imply g is real? How can you get a complex integer out of successive powers of g? > Over GF(p^2) the primitive root g will have order p^2 - 1 > rather than p-1. Again a small search will suffice. > You raise this to the power (p^2 - 1)/n where n divides p^2 - 1. > > If p == 7 (mod 8), then there exists a value sqrt(1/2) in GF(p) > such that 2*sqrt(1/2)^2 == 1 (mod p). > The primitive 8th roots of 1 modulo p are > > +- sqrt(1/2) +- i*sqrt(1/2), > > just as in the complex case. You can optimize > > (a + b*i) * (sqrt(1/2) + i*sqrt(1/2)) > > to > (a - b)*sqrt(1/2) + i*(a + b)*sqrt(1/2) > > (with two multiplications modulo p), just as in the complex case. That's good to know. I don't suppose sqrt(1/2) is necessarily a power of two when p is not a Mersenne prime, is it? Or is it that this is possible with an even more carefully chosen primitive root g? > In other words, if n is a power of 2, you are looking for > a value x mod p such that > > x^((p-1)/2) == 1 (mod p) > x^n == 2 (mod p) > > The last argument shows that a common solution exists. > The exponents n and (p-1)/2 are coprime. > If n*n' == 1 (mod (p-1)/2), then x == 2^(n') (mod p). Neat! > Ernst Mayer and I exchanged many mailings about > using GF(p^2) when p = 2^61 - 1. > I thought he had implemented it, as part of a > mixed integer/complex FFT. As I remember, he *had* implemented it but the project is in limbo now for several reasons: first, the Alpha compiler wouldn't interleave the integer and floating point instructions, and also Ernst mentioned that non-power-of-two transforms in GF(p^2) had some subtle difficulty (something about the order that you applied the various radices being important). Last I heard he was embarking on implementing a mixed integer/complex FFT in assembly language, but that was quite a while ago and he likely has moved on. Thanks again, jasonp _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 12 Mar 2001 05:50:57 -0000 From: "Daran" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Security of prime95 - -----Original Message----- From: Martijn Kruithof <[EMAIL PROTECTED]> To: Daran <[EMAIL PROTECTED]>; [EMAIL PROTECTED] <[EMAIL PROTECTED]> Date: 12 March 2001 00:45 Subject: RE: Mersenne: Security of prime95 + electricity costs. >I have verified the possibility of a buffer overflow exploit in primenet.c I downloaded the source code today, but didn't know in which file to look. Thanks for the pointer. >(used in linuxs mprime) >It seems NOT vurneralbe (so it seems safe to me) >NO buffer overflow is likely to occur. I agree, although coming 'cold' to the source code I can't be 100% certain I understand what it's doing. Nevertheless, I'd prefer to see the buffer length #defined, rather than those '1000's and '999's lying around. If that value were ever to be changed, then it would only take one missed instance of the value to create a vulnerability. A unnoticed fingerslip which added an extra digit would have the same effect. >Notwithstanding I am running mprime as user mersenne with virtually no >rights >and no shell. Every program has at least one right that an attacker doesn't:- the right to run on your computer. From there, a subverted program could spawn it's own shell if necessary, or any other program in /bin, /usr/bin, etc. Even if there are no other security holes, you should at least deny all world access to the home directory areas. Even more paranoid (I am, as you've probably noticed. :-) ) would be to run mprime as user:group mersenne:mersenne, create a new group 'local', chown the */bin directories to this group and deny all world access to them. That might break some of the daemons, but you should be able to fix them on a case by case basis by making them group 'local'. (You'd also have to give all your users local group membership.) I haven't tried this, but as I can't talk to the Internet from Linux, that doesn't matter so much. When I get my new box with a real modem I will try it out. Regards Daran G. _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 12 Mar 2001 06:02:48 -0000 From: "Daran" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Security of prime95 - -----Original Message----- From: Nathan Russell <[EMAIL PROTECTED]> To: Martijn Kruithof <[EMAIL PROTECTED]> Cc: [EMAIL PROTECTED] <[EMAIL PROTECTED]> Date: 12 March 2001 00:23 Subject: Re: Mersenne: Security of prime95 + electricity costs. >>Notwithstanding I am running mprime as user mersenne with virtually no >>rights >>and no shell. > >I wish I had that option. > >My mprime runs from my Windows drive, and needs to be able to access >other files in the GIMPS directory. > >I can't see any way to do this without giving it access to the entire >windows drive, but that doesn't greatly worry me since the same is >true of every program I run under Windows. I'm in the same position. At the very least, you should move the mprime executable onto your Linux drive. Recent versions of mprime (19 IIRC. It's in the WHATSNEW file) allow you to do this and still access the data files on your Win drive. Having the executable there gives an easy way into your *nix to anyone who manages to crack your Win. (Just by replacing it with a trojan.) A competent cracker will get in anyway. A scriptkiddie might not be able to otherwise. Better would be to include in your start-up scripts code to copy the data files from your prime95 directory into your mprime directory, while copying in the reverse direction when you shutdown. >Nathan Daran _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 12 Mar 2001 06:03:13 -0000 From: "Daran" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Security of prime95 - -----Original Message----- From: Brian J. Beesley <[EMAIL PROTECTED]> To: Daran <[EMAIL PROTECTED]> Date: 11 March 2001 22:48 Subject: Re: Mersenne: Security of prime95 + electricity costs. >You are of course correct. But to make this work requires a lot of >knowledge about how the application is coded, and it's more or less >pointless when the program which you _might_ be able to hack in to >has no particular priveleges... As I said in my other replies, the source code is freely available, and anyway, security through obscurity is deprecated, and rightly so. The client has one crucial privilege:- the right to run on that machine. If prime95 can be made to execute arbitrary hostile code then the entire system is breached. Things are better on a properly secured NT/*nix, but a breach is a breach, and a hostile program running locally can attack daemons which don't listen to the network. As far as the amount of work is concerned, well, crackers - real ones, not scriptkiddies - are patient and hardworking, and if a vulnerability is discovered then it will be exploited sooner or later. >...and is running at idle priority. At idle priority, mprime gets over 99.9% of my CPU when I'm not doing anything else. When I am, it averages at about 96%. Prime95 gets about 99.5% on an idle system, as low as 50% when busy, but that's Windows for you. Either way, that's more than enough time to do as much damage as it wants. >Even if there is a theoretical possibility, I think the chance >of an attack succeeding is about the same as that of the Queen Mother >(God bless her - she's 100 years old) has of being killed by a >meteorite whilst standing naked on the summit of Mount Everest. If there is a vulnerability, (and I don't think there is, from looking at the source), then I see no reason why it should be any more difficult to implement that any other buffer overflow exploit, yet such exploits have been implemented and used to breach security. In fact, I can't see any reason why an exploit written for another program shouldn't be used, with minor modifications, for any other. >I rather suspect that a _really determined_ attack would be more >likely to be "successful" in crashing the TCP driver than it would be >to actually compromise the system through the client. An attacker could easily set up a 'development' system with a client to practice his attacks on. [...] >Yes, the server is at more risk than the clients. There is an obvious >threat from denial-of-service attacks, for a start. However, even if >a cracker got into the server, I don't think he'd be able to launch >an attack against client systems which it wouldn't be able to launch >using telnet on an arbitary host. Yes he could. While the client /system/ may have other vulnerabilities that could be attacked using telnet, he couldn't attack the client itself, because it's only listening to Primenet, and then for no more than a few seconds at a time. What puts the Primenet server in a unique position to attack is that the clients connect to it. They tell it when they're listening to it. [...] >Well, being diagnosed paranoid doesn't prove no-one's persecuting you >... I think it makes sense to run Tripwire (or something equivalent); >you _can't_ be sure that a system has no vulnerabilities, but you >_do_ want to be able to detect & eject any successful gatecrashers. Agreed, but you can also be aware of the likely sources of risk, and how to minimise them. >Actually browsers are a significant security hazard, especially if >you fail to disable Java / Javascript / ActiveX / any plugins. All disabled. There are other known vulnerabilities in IE4 for which there are no patches - you're expected to upgrade to IE5. Unfortunately my system is so old and unstable that the last upgrade (to IE4) caused a major crash. I dare not do another. So for the time being I'm conscious of being vulnerable. Another reason for getting a new system with Linux and a real modem. >Anyone >who feels reasonably running a browser, or an e-mail client, should >have no concerns in respect of mprime/Prime95. That may be true, but it is the for the user to decide what risks he is prepared to tolerate, not the GIMPS admins and programmers. /Their/ job is to make that risk as small as possible. I have no idea how or whether you are involved in that effort, but - no offence intended - I have found your replies to this thread shockingly complacent. It's not just the users that stand to lose in the event of a security breach. The entire GIMPS project - and distributed computing in general - would be devastated if a client were implicated in a serious security breach at, say, a large company or a major university. > I don't know the security models for WIN98/NT/ME But I expect something > similar would be possible. WIN95 and earlier can't be secured in this way. Eh? ME & 98 are the same as 95 from the security point of view - I'll take your word of it. I've never used either. Regards Brian Beesley Daran G. _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ End of Mersenne Digest V1 #827 ******************************
