Distributed Computing Projects

[DOSGuy]

It seems that DOS gamers are very tech savvy people, so I thought I would start a new thread about distributed computing projects, which as recently come up as a topic of conversation. I participate in the Seventeen or Bust project on Team Retro, but there are lots of other great causes to donate your unused CPU cycles to. If anyone wants to chat about distributed computing projects, this is the place!

[raman22feb1988]

My favorite projects are:

Prime95, which searches for Mersenne Primes, which I liked before, but which I don't like now, because it is very difficult to catch a Mersenne Prime to test.

The Cunningham project, is a project which tries to factor integers of the form (b^n)±1 for b = 2, 3, 5, 6, 7, 10, 11, 12 upto higher powers.

I like it than Prime95 because there is a result after our effort - getting the factor of the number. And not simply saying that the number is composite. (Almost all Mersenne Numbers, even any big number is mostly composite. Also, the probability of a sufficiently big number to be prime is very small).

The ECMNET project, which tries to find factors of Cunningham Numbers, by using the Elliptical Curve Method. I don't like it than NFS, because it is difficult to find factors by ECM, and almost all small factors (upto 50 digits) of Cunningham Numbers have already been eliminated by ECM.

The NFSNET project, which contributes factors to the Cunningham Project by using the Number Field Sieve. I like NFS to ECM because there is a result after the effort - getting the factor definitely after finishing NFS.

The Aliquot Sequences Project, which tries to verify if the Catalan's conjecture is true, i.e. whether if all the aliquot sequences terminate in a prime or an aliquot cycle.

For more on these projects and about contributing to them, you may better register and post in this forum.

The other distributed computing projects, which I don't like much than the above projects, because only they are not that much important, I do only feel so, and never contributed to them at all are:

The Zeta Grid Project, which tries to prove if the Riemann Hypothesis is true, by checking if all the zeros of the Zeta Function lie precisely on the critical line, Re(s)=½.

The Eleven Smooth Project, which tries to find as many factors of the number (2^3326400)-1.

The project, which searches for odd perfect numbers, if any do exist at all.

The project, which tries to factor Fermat Numbers, and then checks whether if any Fermat Prime exist at all after 65537.

I am currently factoring on for (6^305)-1 of the Cunningham Project with GGNFS. (Will anybody join with me?)

[DOSGuy]

That Odd Perfect Number project sounds interesting. Determining the possibility of such a number contributes to our understanding of how numbers work.

[raman22feb1988]

For everybody, I am very interested in Maths and Number Theory and especially in these topics.

That Odd Perfect Number project sounds interesting. Determining the possibility of such a number contributes to our understanding of how numbers work.

The Odd Perfect number search project has been going for over 300 years, since Euler proved that every even perfect number has the form (2^(n-1))((2^n)-1), where n is a Mersenne prime, and still nobody is able to prove that there are no odd perfect numbers or to find an odd perfect number. It has been checked that there are no odd perfect numbers at all till 10^300.

People conjecture that there will be no odd perfect number at all.

Similarly, nobody is able to prove the Riemann Hypothesis for over 140 years, or to find a zero of the Zeta Function off the critical line Re(s)=½ in the critical strip 0 < Re(s) < 1.

It has however been proved that there are infinitely many zeros in the critical line.
Also that, it has been proved that, so far, atleast 40% of the zeros in the critical strip lie precisely on the critical line.

The Zeta Grid project has verified that the first 1.5 billion zeros of the Zeta Function, lie so precisely on the critical line.

However, the trivial zeros for the Zeta function that are lying at -2, -4, -6, -8, -10, etc., (that is -2k, with positive integral values for k), are not at all being considered so for the statement and then the proof of the Riemann hypothesis, thus.

[raman22feb1988]

For a list of all the Distributed Computing Projects that are going on so far, see here.

[raman22feb1988]

And then one more project that I like which I left over above is that MM61 project, which searches for any small factors of (2^2305843009213693951)-1.

It has once been conjectured that if (2^p)-1 is prime, then 2^[(2^p)-1]-1 is also prime, but it is false.

(2^3)-1, (2^7)-1, (2^31)-1, (2^127)-1 are all known to be prime.
However, (2^8191)-1, (2^131071)-1, (2^524287)-1, (2^2147483647)-1, all of these are all composite. But, small prime factors are known out for all of these numbers.

(2^8191)-1 has factors 338193759479, 210206826754181103207028761697008013415622289
(2^131071)-1 has factors 231733529, 64296354767
(2^524287)-1 has factors 62914441, 5746991873407, 2106734551102073202633922471, 824271579602877114508714150039
(2^2147483647)-1 has factors 295257526626031, 87054709261955177, 242557615644693265201, 178021379228511215367151

However for (2^2305843009213693951)-1, (2^618970019642690137449562111)-1, (2^162259276829213363391578010288127)-1, (2^170141183460469231731687303715884105727)-1, but, no small prime factors are known out for any of these numbers at all. Yet, the status of all of these numbers remain unknown still. But, anyway even the probability for atleast any one of these numbers to be prime is very small!

(2^65537)-1 has factors 513668017883326358119, 883852340565787164089923172087

The first few Mersenne composite numbers with no known prime factors yet at all still are
(2^1061)-1
(2^1237)-1
(2^1277)-1

But, for any number can be very easily said to be prime or composite using the Fermat's Little Theorem. But, factoring of a number which has the penultimate prime factor to be large enough is very difficult! Is it not so only?

[raman22feb1988]

(3^499+1)/4 has been factored up today.

The factors are
50291482856324544404027093373360635121063081581216864654202148086500144195079163724148106275521673861082817129401
60249253834468029722846922340566907742203320456026527837840758742969239944910379299755028256308064416617431085523496168044367

This is one of the largest SNFS factorizations.
No factor other than the trivial factor 4 was known before.
Use Google Search to find out more details about it up.

(3^487+1)/4 is prime.

And then the factors of (3^491+1)/4 are (done in 2004)
60892643104482757573306223567662688740985969197465290654173842691745096014633691396823
7584225732080355558890845446061753463262878714821596148001491056100087309958570295404636944342271195034363779010951175907411916995516251500675474169

[raman22feb1988]

Yes, that I have finished off the factoring of one number for the Cunningham Project.
See # 5566 over here in this website at
http://homes.cerias.purdue.edu/~ssw/cun/page107

I am right now, currently, starting up with another number in the Cunningham Tables as my next project, presently, by now itself, it is up so, only so, right up that way, according to that fact up.

[raman22feb1988]

Prime95, which searches for Mersenne Primes, which I liked before, but which I don't like now, because it is very difficult to catch a Mersenne Prime to test.

GIMPS, the Great Internet Mersenne Prime Search,
on August 23 and September 6, discovers two new
Mersenne Primes, which are (2^43112609)-1 and
(2^37156667)-1 respectively.

GIMPS wins the $100000 award from the Electronic
Frontier Foundation for discovering the first known
10 million digit prime.

For more information, visit http://mersenne.org

[DOSGuy]

Indeed they did. They found a 12 978 189 digit prime and an 11 185 272 digit prime a few days apart. Try to wrap your head around the idea of a 13 million digit number. I mean, think about it expressing it, how much space that would take. Take that massive, unimaginably large number, and now realize that someone tested every possible factor and proved that the number is a prime number. There are no two numbers between 1 and that 13 million digit number that can be multiplied to produce that number. It boggles the mind. Computers are absolutely amazing.

[raman22feb1988]

Take that massive, unimaginably large number, and now realize that someone tested every possible factor and proved that the number is a prime number. There are no two numbers between 1 and that 13 million digit number that can be multiplied to produce that number. It boggles the mind. Computers are absolutely amazing.

Hello, do you know what an algorithm is? If by brute force, you tested every possible factor, it would certainly be impossible, even on the fastest computer. There are better algorithms to prove that the number is prime. Running time of an algorithm matters a lot.

For Mersenne Numbers, which are of the form (2^p)-1, there are powerful algorithms to prove that the number is prime.
For Mersenne numbers, the algorithm is called the Lucas-Lehmer test.

Let S(1)=4
For i=2 to p-1
{
S(i)=S(i-1)²-2 (mod (2^p)-1)
}
(2^p)-1 is prime if and only if S(p-1)=0.

I will be posting about various algorithms for primality testing and factoring.

[DOSGuy]

You're right, they didn't actually test every factor. An algorithm that is known to correctly determine if a number is prime or not has "proven" that this number has no factors.

[raman22feb1988]

I participate in the Seventeen or Bust project on Team Retro, but there are lots of other great causes to donate your unused CPU cycles to. If anyone wants to chat about distributed computing projects, this is the place!

I would recommend everyone to join in some distributed computing project.
To name a few: 1) Seventeen or Bust/Riesel Sieve 2) GIMPS 3) NFSNET/Cunningham Project/ECMNET 4) Aliquot Sequence/Home Prime Search 5) Zeta Grid 6) Eleven Smooth/Odd Perfect Number Search 7) Fermat Number Factorization 8) MM61 9) Factorization of Euler and Bernoulli Numbers, near repdigits, Smarandache Numbers, RSA numbers, Cyclotomic Numbers, etc.

Seventeen or Bust and Riesel Sieve

In 1960, Sierpinski proved that there exist infinitely many odd integers k, for which k(2^n)+1 is prime for all n>=1. And he gave 78557 as an example for it. Such values of k are called Sierpinski Numbers.

It is now conjectured that 78557 is the smallest value of such k. Seventeen or Bust is the distributed computing project that tries to prove that 78557 is the smallest Sierpinski number. It is named so because when the project was started, there were 17 such values of k, to be examined.
4847, 5359, 10223, 19249, 21181, 22699, 24737, 27653, 28433, 33661, 44131, 46157, 54767, 55459, 65567, 67607, 69109

Similarly, in 1956, Riesel proved that there exist infinitely many odd integers k, for which k(2^n)-1 is prime for all n>=1, with 509203 as an example. Such values of k are called Riesel Numbers. The Riesel Sieve project tries to prove that 509203 is the smallest Riesel Number. There are 64 candidates yet to be examined, for this case.
2293, 9221, 23669, 31859, 38473, 40597, 46663, 65531, 67117, 74699,
81041, 93839, 97139, 107347, 121889, 123547, 129007, 141941, 143047, 146561,
161669, 162941, 191249, 192971, 206039, 206231, 215443, 226153, 234343, 245561,
250027, 252191, 273809, 304207, 315929, 319511, 324011, 325123, 327671, 336839,
342847, 344759, 353159, 362609, 363343, 364903, 365159, 368411, 371893, 384539,
386801, 397027, 398023, 402539, 409753, 415267, 428639, 444637, 470173, 474491,
477583, 485557, 494743, 502573

[raman22feb1988]

The Cunningham project, is a project which tries to factor integers of the form (b^n)±1 for b = 2, 3, 5, 6, 7, 10, 11, 12 upto higher powers.

The Cunningham Project was started in 1925 when Western and Cunningham made a list of all the base 2 factors, that were being known so at that time, thus.

Any factor of the Cunningham ((a^p)-1)/(a-1) will always be of the form 2kp+1, where p is prime and a ≥ 2, except when p is a factor of (a-1). In this case, ((a^p)-1)/(a-1) will be divisible by p itself.

However, there are natural factors of Cunningham numbers, that are rather direct, and can be eliminated first. They are of two types:

Algebraic Factorizations
If p is a factor of n, then (a^p)±1 is a factor of (a^n)±1. It is rather straightforward, but still another special type of natural factorization is called the Aurifeuillian Factorization.

Aurifeuillian Factorizations
Aurifeuille discovered this type of factorization, for base 2
(2^(4k-2)+1) = (2^(2k-1)-2^k+1) (2^(2k-1)+2^k+1)
and its general form was given subsequently by Lucas for other bases.

(3^(6k-3)+1) = (3^(2k-1)+1) (3^(2k-1)-3^k+1) (3^(2k-1)+3^k+1)

(5^(10k-5)-1) = (5^(2k-1)-1) (5^(4k-2)-5^(3k-1)+3.5^(2k-1)-5^k+1) (5^(4k-2)+5^(3k-1)+3.5^(2k-1)+5^k+1)

(6^(12k-6)+1) = (6^(4k-2)+1) (6^(4k-2)-6^(3k-1)+3.6^(2k-1)-6^k+1) (6^(4k-2)+6^(3k-1)+3.6^(2k-1)+6^k+1)

(7^(14k-7)+1) = (7^(2k-1)+1) (7^(6k-3)-7^(5k-2)+3.7^(4k-2)-7^(3k-1)+3.7^(2k-1)-7^k+1) (7^(6k-3)+7^(5k-2)+3.7^(4k-2)+7^(3k-1)+3.7^(2k-1)+7^k+1)

(10^(20k-10)+1) = (10^(4k-2)+1) (10^(8k-4)-10^(7k-3)+5.10^(6k-3)-2.10^(5k-2)+7.10^(4k-2)-2.10^(3k-1)+5.10^(2k-1)-10^k+1) (10^(8k-4)+10^(7k-3)+5.10^(6k-3)+2.10^(5k-2)+7.10^(4k-2)+2.10^(3k-1)+5.10^(2k-1)+10^k+1)

(11^(22k-11)+1) = (11^(2k-1)+1) (11^(10k-5)-11^(9k-4)+5.11^(8k-4)-11^(7k-3)-11^(6k-3)+11^(5k-2)-11^(4k-2)-11^(3k-1)+5.11^(2k-1)-11^k+1) (11^(10k-5)+11^(9k-4)+5.11^(8k-4)+11^(7k-3)-11^(6k-3)-11^(5k-2)-11^(4k-2)+11^(3k-1)+5.11^(2k-1)+11^k+1)

(12^(6k-3)+1) = (12^(2k-1)+1) (12^(2k-1)-2^(2k-1).3^k+1) (12^(2k-1)+2^(2k-1).3^k+1)

The distributed computing projects, ECMNET and NFSNET each contribute to the Cunningham Project, by factoring the Cunningham numbers, using the Elliptic Curve Method and the Number Field Sieve respectively.

ECM is used to eliminate factors upto 50 or 60 digits, after which NFS is the best algorithm, that is being available so, to factor such numbers. NFS is indeed, a general purpose factoring algorithm. SNFS is faster than GNFS for the inputs of the same size, but SNFS is applicable only for Cunningham numbers, and special numbers of a special algebraic form. GNFS is faster after inputs that are 100 digits or so, in size, below which Quadratic Sieve is faster than GNFS, to analyze so.

[raman22feb1988]

Just simply, to fill up the gap with the details about the other distributed computing projects, in the above list, that I left over to mention about so,

The Aliquot Sequence is the sequence formed so, by iterating the sum of all the factors of a number, except itself.
In the Home Prime Sequence, the number for the next iteration is formed so, by concatenating all the prime factors of the number in the current iteration.

Smarandache numbers are the numbers that are being formed so, by concatenating all the numbers from 1 to N, in increasing order. If it is being done so in decreasing order, it does form so, Reverse Smarandache numbers.

RSA numbers are being formed so, by taking the product of two similar sized primes, that are being chosen randomly, such that the number is being made so, difficult to factor. RSA numbers are thus, out of reach of ECM, and GNFS is the best algorithm, that is being applicable so, straightforward for such of these RSA numbers.

Repdigits are numbers, which contain so all of the digits same, in their decimal representation. If it contains so, N digits, then all of the N digits will be the same, and then the same digit will be repeated so N times, and thus will be so, being a multiple of the repunit of N digits, (the repeated digit, number of times). The Repunit of N digits, contains so, all ones in its decimal representation, exactly N ones, and hence the digit 1, will be repeated so, N number of times.

So, to be correct, the repunit of N digits = [(10^n)-1]/9
and then, to be complete, the repdigit of N digits = (the repeated digit) * [(10^n)-1]/9, thus.