SV: Mersenne: Factors aren't just factors
reaction to another mail about this This happens all the time in different shapes so I would expect some happy day we found a crosslinked factor. we will never find a factor who is a factor of Mx and also of My simply because every factor give only one count with my algoritm and is factor of one or zero mersenne numbers for example the factor 7 is a factor of 2^3-1 and 2^6-1 and 2^9-1 and 2^12-1 etc.. but only 2^3-1 of a mersenne number so a factor can never be factor of Mx and My both Yep, you're so truly right. After I used the reverse factoring algorithm a bit harder it is not difficult to see that when you arrive at 1 (and started at 1) the same pattern will repeat (after all we are multiplying by 2 and mod'ing the same value repeatedly from 1). Some how it is no longer a mystery that 13421 is a factor of any 2k*61 (2684 in this case) as 61 is the highest prime in the factorized values of 13420 (factors: 2*2*5*11*61). Again: 2*5*11 is only the k. And also I have found reverse factoring will find it self as a value for Mprimes, 31 is a factor of M5 and so is 127 a factor of M7, and most often just it self -1 for very uinteresting values, like 107 divides M106. :-( On the other hand this insight could make me/us construct interesting and primetested values beyond the scope of Mprime (eg. max 66 bits for numbers below 21.600.000) but in the scope of GIMPS (any prime apx.72.300.000). At least I got one machine for which mprime has no relevance as some uncontrolled reboots happens and I would like a sleep to occur every 10 seconds. Then I can write my own reverse facoring for this machine - it is on anyway for other purposes. Happy hunting tsc _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: Factors aren't just factors
Will Edgington writes: [...] But, for those who are interested, here's the current data on how far my runs of the program have gotten so far: M( 32768 )X: 13952750007 M( 1073741824 )X: 810019 M( 18446744073709551615 )X: 2224500019 [...,] the last line implies that all primes less than 2,224,500,019 are listed as a factor of some Mersenne number in my data (yes, I keep data for - essentially - _all_ Mersenne numbers, not just those with prime exponents). So have you selected the prime exponents out of your database and had them officially removed from the GIMPS candidate list? (I know, easier said than done.) And if so, shouldn't trial factoring start above 2^31? ;^) Regards,Bruce _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factors aren't just factors
Alex Kruppa wrote:
Bruce Leenstra wrote:
As luck would have it, this is nearly what I am doing right now:
tempvalue = (q+1)/2
count = 1
while tempvalue != 1 {
if tempvalue is odd tempvalue += q
shiftright tempvalue count++
}
v = count
I'm not sure I understand that code yet, but
Although it is academic at this point, (your timing of 1+ minutes vs. my timing of 7+
days ),
I arrived at my algorithm by entering the
2^(p+1) mod q = 2*2^p mod q
formula into a spreadsheet so each column was 2^row mod (some prime). Then I found a
formula that would recreate the columns from the bottom up. Notice it does ( /2 and +
q ) vs ( *2 and - q ). My goal was to eliminate the mod step and squeak a little
closer to the dword limit.
I also have a version that checks (mod 4) and combines two passes of the loop so p is
always odd.
Obviously the O(log2(q)) vs. O(q) eclipses any speedup I may have achieved.
However, I am working on your algorithm to address some of the issues Will brought up
. . .
Regards,Bruce
_
Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factors aren't just factors
Will Edgington wrote: Is it worthwhile mounting a formal attack on the Mersenne numbers between 20 million say 40 million using this technique? We're getting quite close to this I think Chris would not have bothered with these, since they were so far ahead of LL testing at that point (first tests around 6 million). I actually run the program I mention above regularly, but it isn't of much use in eliminating Mersenne prime candidates because it finds the factors in factor order rather than in Mersenne exponent order. Further, virtually all prime numbers are factors of Mersenne numbers with composite exponents rather than Mersenne numbers with prime exponents. My program only test prime p that divide f-1 so it only finds factors of prime exponent Mersennes. But the exponents are mostly very large, not that much smaller than f. Afaik, the chance that a prime of the form 2kp+1 divides M(p) is ~1/k, so the factors f where p is much smaller than f will be rare. The reverse factoring method mostly finds factors of frightingly large Mersenne numbers that are way outside the interval of Mersenne prime candidates of interest to GIMPS. I've made this very rough estimate: My K6-2 500MHz takes 4 minutes to factor a 20M exponent from 2^56 to 2^57. (All exponents in nofactor.txt are factored to at least 2^56) There are ~70 exponents in nofactor.txt that are factored to 2^56, so the K6 would take 2.8*10^6 minutes to factor all remaining exponents to 2^57 (this is an overestimate as the larger exponents are faster). I've made some modifications to ismersfac to speed things up (the new version takes 2 seconds for f10M). It takes 9 minutes for 2^29 f 2^30. When testing factors in [2^n, 2^n+1], the time seems to be proportional to about (2^n)^k where k is ~1.35 for n=29 but grows for greater n. Is surely is 1.4 for n=56. So for n=56, ismersfac should take at least (2^27)^1.4 = 2.4*10^11 times as long as for n=29, which is ~10^12 minutes. This estimate is very crude and probably off by orders of magnitude, but rather too low than too high. At any rate it shows that the reverse factoring method is probably not efficient to find larger factors of Mersenne numbers. Taking all of this into account, I'm fairly certain that the technique is not - or is at least no longer - useful for GIMPS's purposes. Will I agree with Will. Alex _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
VS: Mersenne: Factors aren't just factors
-Oprindelig meddelelse-
Fra: Torben Schlüntz
Sendt: lø 23-03-2002 02:54
Til: Bruce Leenstra
Cc:
Emne: SV: Mersenne: Factors aren't just factors
Bruce Leenstra wrote:
You'll notice that 'tempvalue == 1' is only the exit condition
for the loop above. This is because every prime is a factor of some
mersenne number M(v) { plus the set of M(kv), which are all composite
}. Of course GIMPS is only interested in those where v is prime. My
program will abort the loop and prompt me if count (q-1)/2, indicating
q isn't a factor of any M(v). It hasn't happened yet.
Yes I got it now, and with the same
multiply by 2 - take modulus of factor - check for 1 - check for
(q-1)/2 - repeat
just proved a low factor for M641 as well as the usual M29, 43
etc. :-)
And you're right - the algorithm tells - whenever a factor is
found, it will be factor again and again for other GIMPS uninteresting
composite M's, like 89 is a factor for M11 then M22 then M11*x. So there
is no SUPERfactor being a factor for several M's.
Last you say any prime will be a factor for some Mx, quite
interesting, and yes to pick one 641 is a factor of M64.
br tsc
_
Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factors aren't just factors
Don't be so hard on Phil, I made not only a mistake but one that was very easy to catch. I should know by now better than to trust my memory before sending something out. But it's hard to get used to being senile :-) I guess that also explains why I never pursued it... Steve -Original Message- From: Torben Schlüntz [EMAIL PROTECTED] To: Phil Moore [EMAIL PROTECTED]; [EMAIL PROTECTED] [EMAIL PROTECTED] Date: Wednesday, March 20, 2002 4:41 PM Subject: SV: Mersenne: Factors aren't just factors Actually I should have let Steve answer this, but I can't ignore to say that I already have pointed out that M89 is prime. So Steve had a mistake. Okay?! I do several mistakes every hour. snip _ 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: Factors aren't just factors
Hi,
I seem to remember about 3.5 years ago someone (I think it was Chris Nash)
had done something similar eliminated a lot of Mersenne numbers.
Is it worthwhile mounting a formal attack on the Mersenne numbers between 20
million say 40 million using this technique? We're getting quite close to
this I think Chris would not have bothered with these, since they were so
far ahead of LL testing at that point (first tests around 6 million).
Regards
Brian Beesley
On Thursday 21 March 2002 00:21, Alexander Kruppa wrote:
Bruce Leenstra wrote:
As luck would have it, this is nearly what I am doing right now:
tempvalue = (q+1)/2
count = 1
while tempvalue != 1 {
if tempvalue is odd tempvalue += q
shiftright tempvalue
count++
}
v = count
I'm not sure I understand that code yet, but
I've crunched through all q 2^23; [...] The program is really starting
to slow down.
There may be a faster method.
Let f be a prime factor of the prime exponent Mersenne number M(p).
f | M(p) =
2^p == 1 (mod f) =
ord(2) (mod f) | p = (since ord(n) = 1 = n = 1)
ord(2) (mod f) = p.
Thus, f is a factor of M(p) if and only if the group order of 2 (mod f)
is equal to p.
On the other hand, ord(2) (mod f) divides f-1, since f is prime.
We can thus test whether f is a factor of some prime exponent Mersenne
M(p) by testing all prime divisors p of f-1 and checking if 2^p == 1
(mod f).
I add a quick hack to exemplify. Please don't take this code too
seriously. I made no effort to make it efficient, for example all odd
and not only prime f are tested and the trial division is pathetic, too.
An order of magnitude speedup would be possible.
But the basic algorithm is reasonably fast:
time ./ismersfac /dev/null
real1m7.907s
user1m7.710s
sys
0m0.040s
for f 1000 =~ 2^23.25 , on a K6-II 500Mhz.
#include stdio.h
unsigned int powmod(unsigned int a, unsigned int b, unsigned int m) {
unsigned int t = 0, mask = 131;
if (b == 0) return 1;
while ((b mask) == 0) mask = 1;
mask = 1;
t=a;
while (mask) {
t = (unsigned long long) t * t % m;
if (b mask) {
t = (unsigned long long) t * a % m;
}
mask = 1;
}
return t;
}
unsigned int ismersfac(unsigned int f) {
unsigned int fm1 = f-1;
unsigned p;
while ((fm1 1) == 0) fm1 = 1;
for (p = 3; p*p = fm1; p+=2) {
if (fm1 % p == 0) {
if (powmod(2, p, f) == 1) {
return p;
} else {
while (fm1 % p == 0)
fm1 /= p;
}
}
}
if (fm1 1) {
if (powmod(2, fm1, f) == 1)
return fm1;
}
return 0;
}
int main() {
unsigned int i, p;
for (i=3; i 1000; i+=2) {
if ((p = ismersfac(i)))
printf(M( %d )C: %d\n, p, i);
}
return 0;
}
_
Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factors aren't just factors
Torben, I noticed something along those lines long ago: the first non-prime
Mersenne number is M11 which factors to 23 times 89. The very next non-prime
Mersenne number is M23, and M89 is also not prime. It occurred to me then
that possibly Mx is never prime if x is a factor of a Mersenne number, but
it was just an observation and I never got around to pursuing it. If so,
then it would (although only very slightly) reduce the number of candidates
to be tested. So I am just as curious as are you.
Jeroen, I am wondering about your phrase if kv is not prime then 2^(kv)-1
isn't also because kv is never prime, it has factors k and v (unless k=1,
of course), and 2^(kv)-1 always has factors 2^k-1 and 2^v-1. I don't know if
you meant something else or if I just misunderstood you. Sorry if that's the
case.
Regards,
Steve Harris
-Original Message-
From: Jeroen [EMAIL PROTECTED]
To: [EMAIL PROTECTED] [EMAIL PROTECTED]
Date: Tuesday, March 19, 2002 8:12 PM
Subject: Re: Mersenne: Factors aren't just factors
to find the value v where prime p is a factor of 2^v-1
tempvalue = p
count = 0
while tempvalue != 0
{
if tempvalue is odd
{
shiftright tempvalue
count++
}
else
{
tempvalue+=p
}
}
if the count is a primenumber then p is thus a factor of a mersenne prime
if the count is not a primenunber it isn't
if p is a factor of 2^v-1 then it is also a factor of 2^(2v)-1
or just 2^(kv)-1 for all value of k are integers above 0
if kv is not prime them 2^(kv)-1 isn't also, so each prime can only be a
factor of one mersenne numer or 0 mersenne numbers
the first question is now simple to solve, just find the 2^v-1 where Mx is
a factor of
*** REPLY SEPARATOR ***
On 20-3-02 at 0:21 Torben Schlüntz wrote:
Just of curiosity:
Has it ever happened that a factor for Mx later has proved to be a
mersenne prime itself?
Has the same factor been a factor for two different Mx and My?
In my humble oppinion both questions answers No; but GIMPS could have
proved otherwise.
Anyway, it must exist a great deal of low primes; which by now never can
become mersenne factors (by reason: 2kp+1). So with two types of primes,
those that are mersenne factors and those that never can be, do we have
any means of distinguish them?
Happy hunting
tsc
Btw: (M29 mod 1 + M29 mod 2 +..+ M29 mod 32) = 233which is 1.
factor of M29
_
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
_
Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
SV: Mersenne: Factors aren't just factors
M89 is prime! M89 = 618.970.019.642.690.137.449.562.111 with no known factors. So it would be lovely if we could rule out any possible Mx if x had earlier been a factor for any other My. :-) But no. M11 proves this so nicely: M23 has factors, M89 none. I've started looking for some factors, where f is both factor of Mx and of My. The chance is there as Mx calls for factors of the form 2kx+1 and My calls for 2Ky+1. Let's have an example: 547 is candidate for M7 as for M13: 2*(3*13)*7+1 and 2*(7*3)*13+1 or better: 83 is candidate for M79 and for M6329 as 2*(6329)*79+1 and 2*(79)*6329+1 both equals 83. This happens all the time in different shapes so I would expect some happy day we found a crosslinked factor. happy hunting tsc Torben, I noticed something along those lines long ago: the first non-prime Mersenne number is M11 which factors to 23 times 89. The very next non-prime Mersenne number is M23, and M89 is also not prime. It occurred to me then that possibly Mx is never prime if x is a factor of a Mersenne number, but it was just an observation and I never got around to pursuing it. If so, then it would (although only very slightly) reduce the number of candidates to be tested. So I am just as curious as are you. _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factors aren't just factors
Steve Harris claimed that M89 is not prime, but it is! So his conjecture about being able to eliminate a few Mersenne candidates because the exponent is a factor of a non-prime Mersenne number won't work. Phil Moore _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factors aren't just factors
Jeroen wrote:
to find the value v where prime p is a factor of 2^v-1
tempvalue = p
count = 0
while tempvalue != 0
{
if tempvalue is odd
{
shiftright tempvalue
count++
}
else
{
tempvalue+=p
}
} ...
(Uh, did you swap your 'if' and 'else' clauses? if temp is odd do you want to shift
the '1' off?)
As luck would have it, this is nearly what I am doing right now:
tempvalue = (q+1)/2
count = 1
while tempvalue != 1 {
if tempvalue is odd tempvalue += q
shiftright tempvalue
count++
}
v = count
q is therefore a factor of the mersenne number 2^v - 1. If v is prime then M(v) is
eliminated as a mersenne prime, so I keep a list of prime v's. I've crunched through
all q 2^23; soon I'll start submitting the high end of my list to GIMPS for removal
from the candidate list. The one drawback is this method finds alot of v where q = 2v
+ 1 (k = 1), which require q/2 times thru the loop. The program is really starting to
slow down.
Back to the discussion
TSC wrote:
Anyway, it must exist a great deal of low primes; which by now never
can become mersenne factors (by reason: 2kp+1). So with two types of
primes, those that are mersenne factors and those that never can be,
do we have any means of distinguish them?
Remember that every odd number can be written in the form 2kp + 1 (p prime, k may be
1), so that is not a limitation to being a factor.
You'll notice that 'tempvalue == 1' is only the exit condition for the loop above.
This is because every prime is a factor of some mersenne number M(v) { plus the set of
M(kv), which are all composite }. Of course GIMPS is only interested in those where v
is prime. My program will abort the loop and prompt me if count (q-1)/2, indicating
q isn't a factor of any M(v). It hasn't happened yet.
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: Factors aren't just factors
Bruce Leenstra wrote:
As luck would have it, this is nearly what I am doing right now:
tempvalue = (q+1)/2
count = 1
while tempvalue != 1 {
if tempvalue is odd tempvalue += q
shiftright tempvalue
count++
}
v = count
I'm not sure I understand that code yet, but
I've crunched through all q 2^23; [...] The program is really starting to slow
down.
There may be a faster method.
Let f be a prime factor of the prime exponent Mersenne number M(p).
f | M(p) =
2^p == 1 (mod f) =
ord(2) (mod f) | p = (since ord(n) = 1 = n = 1)
ord(2) (mod f) = p.
Thus, f is a factor of M(p) if and only if the group order of 2 (mod f)
is equal to p.
On the other hand, ord(2) (mod f) divides f-1, since f is prime.
We can thus test whether f is a factor of some prime exponent Mersenne
M(p) by testing all prime divisors p of f-1 and checking if 2^p == 1
(mod f).
I add a quick hack to exemplify. Please don't take this code too
seriously. I made no effort to make it efficient, for example all odd
and not only prime f are tested and the trial division is pathetic, too.
An order of magnitude speedup would be possible.
But the basic algorithm is reasonably fast:
time ./ismersfac /dev/null
real1m7.907s
user1m7.710s
sys
0m0.040s
for f 1000 =~ 2^23.25 , on a K6-II 500Mhz.
#include stdio.h
unsigned int powmod(unsigned int a, unsigned int b, unsigned int m) {
unsigned int t = 0, mask = 131;
if (b == 0) return 1;
while ((b mask) == 0) mask = 1;
mask = 1;
t=a;
while (mask) {
t = (unsigned long long) t * t % m;
if (b mask) {
t = (unsigned long long) t * a % m;
}
mask = 1;
}
return t;
}
unsigned int ismersfac(unsigned int f) {
unsigned int fm1 = f-1;
unsigned p;
while ((fm1 1) == 0) fm1 = 1;
for (p = 3; p*p = fm1; p+=2) {
if (fm1 % p == 0) {
if (powmod(2, p, f) == 1) {
return p;
} else {
while (fm1 % p == 0)
fm1 /= p;
}
}
}
if (fm1 1) {
if (powmod(2, fm1, f) == 1)
return fm1;
}
return 0;
}
int main() {
unsigned int i, p;
for (i=3; i 1000; i+=2) {
if ((p = ismersfac(i)))
printf(M( %d )C: %d\n, p, i);
}
return 0;
}
_
Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factors aren't just factors
to find the value v where prime p is a factor of 2^v-1
tempvalue = p
count = 0
while tempvalue != 0
{
if tempvalue is odd
{
shiftright tempvalue
count++
}
else
{
tempvalue+=p
}
}
if the count is a primenumber then p is thus a factor of a mersenne prime
if the count is not a primenunber it isn't
if p is a factor of 2^v-1 then it is also a factor of 2^(2v)-1
or just 2^(kv)-1 for all value of k are integers above 0
if kv is not prime them 2^(kv)-1 isn't also, so each prime can only be a factor of one
mersenne numer or 0 mersenne numbers
the first question is now simple to solve, just find the 2^v-1 where Mx is a factor of
*** REPLY SEPARATOR ***
On 20-3-02 at 0:21 Torben Schlüntz wrote:
Just of curiosity:
Has it ever happened that a factor for Mx later has proved to be a
mersenne prime itself?
Has the same factor been a factor for two different Mx and My?
In my humble oppinion both questions answers No; but GIMPS could have
proved otherwise.
Anyway, it must exist a great deal of low primes; which by now never can
become mersenne factors (by reason: 2kp+1). So with two types of primes,
those that are mersenne factors and those that never can be, do we have
any means of distinguish them?
Happy hunting
tsc
Btw: (M29 mod 1 + M29 mod 2 +..+ M29 mod 32) = 233which is 1.
factor of M29
_
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: Factors
Hoogendoorn, Sander writes: Torben Schlaqntz wrote: It seems to me that this k (in 2kp+1) is never: 4,12,20,28,36,46,52,60,68,76,84 at least for less than M416.947. Am I again a fool for a pattern already proved? It has been proven that k = 1 or 7 mod 8 Careful! It has been proven that _factors_ are of that form, not that the k's (of 2*k*p + 1 where 2*k*p + 1 is a factor of M(p)) are of that form. k, in fact, can be 0 mod 4, e.g., since, if a factor is 1 mod 8: factor = 2*k*p + 1 = 1 (mod 8) 2*k*p = 0 (mod 8) k*p = 0 (mod 4) k = 0 (mod 4) ... since p, being prime, is not 0 mod 4. This occurs, e.g., for M(11), as one of the factors is 89. Will _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factors
Torben Schlüntz wrote: I'd also like to know about any number fully factorized, whatever size it might be, and whatever size the factor(s) might be. Try Will Edgingtons's page, http://www.garlic.com/~wedgingt/mersenne.html . Use used to keep a comprehensive archive of known Mersenne factors. I am not sure how up to date this files are, but it is a good starting point. Besides I have the question: why does the advanced facor algortithm of prime95 somtimes find 2 factors? This happens eg. at M1289, has 108817410937 and 15856636079 as factors? I'm not quite sure which advanced factor algorithm you mean. There are two possibilities: P-1/ECM: These find all factors that have the required property, i.e. that the starting element in the group has a group order whose factors are only primes and prime powers =B1, and at most one prime =B2. It is perfectly possible to find several factors in one run, or even all factors, in which case the algorithm outputs the input number. Trial factoring: Trial factoring proceeds by trying candidate factors to see if they divide your input number. One normally tests a candidate factor f only after having tried all candidates f (or at least sqrt(f)), so that the candidates can be restricted to primes. For if d|f, d|the input number and should have been found before f. Restricting the f's to only primes is too expensive, so one strikes a balance by excluding only those f which have factors smaller than some limit, in a process called sieving. The optimal sieving limit depends on how fast the sieving can be performed, and how long it takes to test one surviving candidate. Thus, a composite factor can be found if all it's prime factors are above the sieving limit. I do not know what the current sieving limits in Prime95 are, but they surely are 15856636079 for all trial factoring depths. It would be rather easy to test factors for primality once they are found and not print them or comment them as not prime when printed. However, the main purpose of trial factoring in Prime95 is to find smallest factors to eliminate Mersenne prime candidates, here such a test is not neccessary as the smallest factor of a number is always prime. Alex _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: Factors
From: Alexander Kruppa [mailto:[EMAIL PROTECTED]] Torben Schlüntz wrote: ... Besides I have the question: why does the advanced facor algortithm of prime95 somtimes find 2 factors? This happens eg. at M1289, has 108817410937 and 15856636079 as factors? I'm not quite sure which advanced factor algorithm you mean. There are two possibilities: ... Trial factoring: ... balance by excluding only those f which have factors smaller than some limit, in a process called sieving. The optimal sieving limit depends on how fast the sieving can be performed, and how long it takes to test one surviving candidate. Thus, a composite factor can be found if all it's prime factors are above the sieving limit. I do not know what the current sieving limits in Prime95 are, but they surely are 15856636079 for all trial factoring depths. Another issue which used to generate multiple factors by trial division in prime95 (I don't know if it still does) is the following. All factors of Mersenne numbers fall into a small number of concisely describable sets. Prime95 used to test all of one kind of factor in a range before going on to test all those of a different kind in the same numerical range. The program also wanted to find the smallest prime factor. Consider now what happens if two factors in a range belong to different sets. You have to process all sets before you know which is the smallest. Having found any larger ones, it would be stupid not to report them too. Paul _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factors
Alexander Kruppa writes: Torben Schluntz wrote: I'd also like to know about any number fully factorized, whatever size it might be, and whatever size the factor(s) might be. Try Will Edgingtons's page, http://www.garlic.com/~wedgingt/mersenne.html . Use used to keep a comprehensive archive of known Mersenne factors. I am not sure how up to date this files are, but it is a good starting point. I still keep the data, but have not had time to update the online copies for a while now for several reasons that have nothing to do with GIMPS or other Mersenne stuffs. For example, the current primary cause of my lack of time is my new project at NASA/Ames: the AI-based planning software that I've been helping to develop for the past few years has been selected, this past Nov., for use by the upcoming Mars 2003 rover missions, to assist the human planners figure out what each rover can likely do during each Martian day. When I have time, I also maintain the mers package of programs - all in C source code and as portable as I know how to make them, which, of course, usually makes them slower than the other available programs - to do various things with Mersenne numbers, including verify that factors are prime, factor any composite factors, try to factor Mersenne numbers with Mersenne primes for exponents, etc., as well as the more typical tasks like Lucas-Lehmer tests, trial factoring, ECM, and P-1 of Mersenne numbers themselves. The URL given by Alexander is the primary one, which should have links to all sorts of other things, on my site and several others. Will _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
SV: Mersenne: Factors
Thanks is a poor word, but anyway thanks to all. I will move on, though my first idea such like: 2kp+1 is a factor when k is 2^x is already dead at M37. :-( damned! I will find another proposal, prove it or disprove it, and continuing getting new ideas. It seems to me that this k (in 2kp+1) is never: 4,12,20,28,36,46,52,60,68,76,84 at least for less than M416.947. Am I again a fool for a pattern already proved? On the other site you can watch this: k=2, 1875 factors in above mentioned space up till M416.947 spanding 35144 primes: k=4, 0 k=6, 1132 k=8, 715 k=10, 465 k=12,0 k=14,233 k=16,351 k=32,138 ... k=64, 65 ... k=72,123 k=74,33 remark, the overall high values of k=2^x factors and remark the low value of eg. k=74. Also remember these factors where obtained by prime95 Advanced factors first of all looking for a low or maybe the lowest value for the factor. So my point here is chance of k=2^x for a factor is high, espcially when p95 has run to the end regarding 64-70 bits low facoring and not found a factor. Now am I wrong in this conclusion and should I drop the the project or is still a small amount of light passing through the halfopen doorway? br happy hunting tsc Try Will Edgingtons's page, http://www.garlic.com/~wedgingt/mersenne.html . Use used to keep a comprehensive archive of known Mersenne factors. I am not sure how up to date this files are, but it is a good starting point. I still keep the data, but have not had time to update the online copies for a while now for several reasons that have nothing to do with GIMPS or other Mersenne stuffs. _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factors
I have downloaded the factor files suggested by GIMPS but it gives no meaning. How do I read the files *.cmp? And why is this not documented close to the source of the *.cmp files? I am also a bit disannoyed about numbers less than M751 that should be fully factorized seems unavaible, or am I looking the wrong places? Do you know a site which I don't? I'd also like to know about any number fully factorized, whatever size it might be, and whatever size the factor(s) might be. The next step for GIMPS is a faster factoring algorithm and the way to get that will be that someone - maybe a mathematician or some beer-drinking fool like me - finds the stones of immortality. :-) Besides I have the question: why does the advanced facor algortithm of prime95 somtimes find 2 factors? This happens eg. at M1289, has 108817410937 and 15856636079 as factors? Happy hunting tsc _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factors
Hi, At 11:59 PM 1/15/2002 +0100, =?utf-8?Q?Torben_Schl=C3=BCntz?= wrote: I have downloaded the factor files suggested by GIMPS but it gives no meaning. How do I read the files *.cmp? From the status.htm web page: You will need a special program to decompress the known factors data The special program is: ftp://mersenne.org/gimps/decomp.zip I am also a bit annoyed about numbers less than M751 that should be fully factorized seems unavaible, or am I looking the wrong places? Do you know a site which I don't? Go to the Cunningham project at: http://www.cerias.purdue.edu/homes/ssw/cun/index.html The next step for GIMPS is a faster factoring algorithm and the way to get that will be that someone - maybe a mathematician or some beer-drinking fool like me - finds the stones of immortality. :-) Good luck finding this algorithm. Many advances have been made the last two decades. We eagerly await the next one! Besides I have the question: why does the advanced facor algortithm of prime95 somtimes find 2 factors? This happens eg. at M1289, has 108817410937 and 15856636079 as factors? I don't remember. That code is no longer supported. Best regards, George _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factors Everywhere
Hi everyone, A few points about publishing known factors. 1) I don't see any particular need to make available files in human- readable format, provided that we provide a specification for the file, and also binary executables for common platforms for converting a machine-readable file to human-readbale format. On the other hand, it could be that "zipping" a human-readable format file provides near- optimal compression. 2) Since factors are of the form 2kp+1, it is only neccessary to list p k. This saves a significant amount of storage (compared with listing p and 2kp+1) and the proper factor is easily recovered. 3) If the data was held in variable-length records in a format similar to p,n,k1,k2,k3... where n is the number of known factors and k1, k2, k3,... are the multipliers for each of the known factors in turn, this would save much duplication compared with the current format (of factor.txt). 4) For values of p which fit into a (integer) CPU register and "small" values of k (up to approx. 64K), trial factoring is so fast that I doubt it would be any faster to search a file than to repeat the calculation - even if the file is already available locally. Therefore I suggest that, in order to reduce substantially the size of the frequently-updated publicly-available known factors file, "small" values of k are omitted, and a program be provided instead to generate the data (with binary executables for common platforms). Perhaps the file should contain a "flag" denoting that factors are known, but have been omitted for this reason. We should still have a large master file somewhere, but this need not be uploaded frequently. 5) Following on from (4), it seems to make sense to record the highest value of k tested by trial factoring, rather than the maximum number of bits. 6) PrimeNet trial factoring has moved well into the 10 millions, however George's factor.zip file contains data only up to 10 million. I know there is a problem with uploading the large files concerned; hopefully, the suggestions above will help to reduce the size of the file, sufficiently to make it feasible to expand the exponent range to cover (at least) the active Primenet assignments for long enough for cheap, high-speed Internet connectivity to become widespread. 7) I have several hundred megabytes of disk space available on my ftp server, which has reasonable Internet access - at least 8 Mbps connectivity to the Internet core - and would be happy to provide means for anyone interested to upload factoring data (or anything else, strictly relevant to Mersenne or closely-related numbers) for the purpose of making it publicly available. Regards Brian Beesley _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factors Everywhere
Brian J. Beesley writes: 1) I don't see any particular need to make available files in human- readable format, provided that we provide a specification for the file, and also binary executables for common platforms for converting a machine-readable file to human-readbale format. I, personally, have no way of producing executables except for Intel CPUs, and presently only for Linux (I just yesterday got a old P100 machine up running Win98 (and Prime95, of course:)). I have thought about a binary data format off and on for a while now, but mostly in terms of making updates easier by designing a format that can be updated in place (at least most of the time), which is a different problem. On the other hand, it could be that "zipping" a human-readable format file provides near-optimal compression. Most likely, and this avoids having to provide executables to read it: they're already out there. 2) Since factors are of the form 2kp+1, it is only neccessary to list p k. This saves a significant amount of storage (compared with listing p and 2kp+1) and the proper factor is easily recovered. Unfortunately, it's only this simple when p is odd. For even p, factors can be one more than any multiple of p, not just one more than even multiples of p. And I'd really rather not have a different format for even exponents ... 3) If the data was held in variable-length records in a format similar to p,n,k1,k2,k3... where n is the number of known factors and k1, k2, k3,... are the multipliers for each of the known factors in turn, this would save much duplication compared with the current format (of factor.txt). This is also a good idea, but a few of the lines would be _very_ long, which some text editors and other programs will have problems with. I'd also suggest dropping n; including it doesn't really add anything and it can be computed quickly from the other data. Perhaps something like: n p,pk1 ,pk2 ,pk3 Note that M(n) has no known factors. 4) For values of p which fit into a (integer) CPU register and "small" values of k (up to approx. 64K), trial factoring is so fast that I doubt it would be any faster to search a file than to repeat the calculation - even if the file is already available locally. Yes, but then there's no way to be sure whether the factor is already known or not. There was a bug in an early post-GIMPS-start factorer of mine that caused it to miss _exactly_ one factor, of M(47). If I hadn't had an explicit list of factors to compare with, I would have never found the bug. Perhaps the file should contain a "flag" denoting that factors are known, but have been omitted for this reason. This might be enough, though. But note that this can already be done using the DATABASE format, if you're willing to omit all factors. Hm; so perhaps a DATABASE file with all the exponents and trial factoring extents and a second, human readable, file, as above, is a possibility. And I've long thought about a small program ( function) to do fast, binary lookups in large Mersenne data files like these (human readable or binary), akin to the common UNIX "look" program for dictionary files, but, of course, doing a numeric search rather than a dictionary search. We should still have a large master file somewhere, but this need not be uploaded frequently. I update my local copy about twice a week usually; it takes only a couple hours on my new PIII/450MHz machine and was well under a day even on my old P233MMX system. These times include automatically downloading data out there every few days to a month, as appropriate for the particular file. 5) Following on from (4), it seems to make sense to record the highest value of k tested by trial factoring, rather than the maximum number of bits. This is lacking in the DATABASE format, but my format implies this info. And, for a year or more, I've actually been treating the "distance" in k's to get to the next power of two as a "gap" in the trial factoring data and thus most of it is just above powers of two. Note also that exponents with known factors can be worked on by Prime95 again, after mersfacgmp or some other factorer pushes the extent past the next power of two above a factor. 6) PrimeNet trial factoring has moved well into the 10 millions, however George's factor.zip file contains data only up to 10 million. Yup. This also means that my factors and his for exponents above 10 million have not been compared for some time. I know there is a problem with uploading the large files concerned; hopefully, the suggestions above will help to reduce the size of the file, sufficiently to make it feasible to expand the exponent range to cover (at least) the active Primenet assignments for long enough for cheap, high-speed Internet connectivity to become widespread. Or perhaps George should simply shift to the factors of the exponents
Mersenne: Factors Everywhere
Eric Hahn writes:
[I've already replied in detail to Eric privately.]
I've come up with this SWAHBI (like a SWAG, but an idea
instead of a guess).
Hm, "silly, wild *ssed, half-baked idea" ? That's not an acronym I've
seen before.:)
What I'm looking for is the following two items for *all*
Mersenne numbers 2^p-1 where p is prime and p1:
1) All known factors (including, but not limited to,
the smallest known factor (noted if it isn't))
My data contains some prime exponents with as many as eight known
prime factors.
2) Largest potential factor attempted
I have this as well, but there are also some gaps in the trial
factoring efforts to date, which I also keep track of and try to
close.
I ask that the two items are human-readable at the
very least.
The format I use is described in the mersfmt.txt file; it is human
readable, being primarily alphanumeric plus parentheses and colon (:).
Conversion to just about any other printable format is easy; UNIX has
lots of tools that allow this sort of text manipulation.
I've pulled a couple of files off mersenne.org
(FACTORS.ZIP and NOFACTOR.ZIP) as well as off
Alex Kruppa's page. While the files appear complete
as far as I can tell, they only cover the ranges
of p between 11 - 9,999,991 and 33,219,281 - 35,999,993.
Correct. George has still not asked me for my data for exponents
above 10 million, but it's probably almost as easy to retest as to
have me send (my data isn't very deep for the exponents above 21
million or so), and makes for a good double check.
They also don't cover *all* known factors!
Correct; since GIMPS is mainly looking for Mersenne primes, Prime95
stops at the smallest factor (which is not always the first factor it
finds for an exponent because of the 16 pass approach in the sieving
code).
Any and all information on the ranges between 10M - 33.22M and
above 36M is greatly appreciated, as well as any known factors not
listed in the files I've pulled.
My prime exponent data for all ranges is now about 111 MB; this
includes all known factors, each exponent's largest attempted trial
factor, and all the ECM and P-1 effort (but no P-1 save files). The
gaps data is another 9MB, and the P-1 save files, mostly from
Factor98, are about another 110 MB. All but the P-1 save files use
the format described in:
http://www.garlic.com/~wedgingt/mersfmt.txt
... which is human readable and accepted by the mers package programs.
The P-1 save files are understood by the mers package's extract enough
to print most everything but the "residue" itself, including the beta
release's extract understanding the new P-1 save file format of George
Woltman's Prime95 v19. Extract's understanding of the P-1 save file
formats will be extended, when I get around to it, to converting from
one P-1 format to another.
Conrad Curry writes:
Will Edgington maintains this information, but it may be
hundreds of megabytes in size. If a website, such as
Entropia, has the space it will be useful to make this database
available (in many small compressed files) so that others may
use it.
Yes, but the first problem is that my 56Kb modem is in the way.:(
But I would be willing to upload it a range at a time over a month or
so, going back to the start to update ranges that have changed since
their last upload, if someone out there has enough web disk space
for it.
And what GIMPS needs, the list of prime exponents with some data but
no known factors, is still quite small, especially in the binary
DATABASE format (which extract can print in the mersfmt.txt format);
that DATABASE file for all prime exponents with data but no factors is
only 2MB presently. It is produced by the contract program during my
updates and put in the mersdata.{zip,tgz,tar.gz} file.
Eric Hahn writes:
If no information is known where p100M, then what can I do??
I have some data for exponents over 2^31. The smallest prime exponent
with no data is only 21556027 presently (though I increase it some
with every update), however, and most of the data is below that.
Also, generating new data for a given prime exponent under about 2^60
(if your machine has an eight byte integer type available in C) or so
is easy using mersfacgmp; all it takes is CPU time.
Will
http://www.garlic.com/~wedgingt/mersenne.html
mers.tgz
mers.tar.gz
mers.zip
mersfmt.txt
mersdata.tgz
mersdata.tar.gz
mersdata.zip
_
Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factors Everywhere
On Sat, 18 Sep 1999, Eric Hahn wrote: What I'm looking for is the following two items for *all* Mersenne numbers 2^p-1 where p is prime and p1: It can be proven that there are an infinite number of these. 1) All known factors (including, but not limited to, the smallest known factor (noted if it isn't)) 2) Largest potential factor attempted I ask that the two items are human-readable at the very least. Will Edgington maintains this information, but it may be hundreds of megabytes in size. If a website, such as Entropia, has the space it will be useful to make this database available (in many small compressed files) so that others may use it. _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factors Everywhere
What I'm looking for is the following two items for *all* Mersenne numbers 2^p-1 where p is prime and p1: It can be proven that there are an infinite number of these. Yeah, right, I knew that... I guess I should've clarified and said for all of them that the information is known :( If no information is known where p100M, then what can I do?? 1) All known factors (including, but not limited to, the smallest known factor (noted if it isn't)) 2) Largest potential factor attempted I ask that the two items are human-readable at the very least. Will Edgington maintains this information, but it may be hundreds of megabytes in size. If a website, such as Entropia, has the space it will be useful to make this database available (in many small compressed files) so that others may use it. Isn't the majority of the information he has in machine-readable format though?? I can't make much use of it, if I can't read it... Eric Hahn _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factors Everywhere
Ok, I've come up with this SWAHBI (like a SWAG, but an idea instead of a guess). What I'm looking for is the following two items for *all* Mersenne numbers 2^p-1 where p is prime and p1: 1) All known factors (including, but not limited to, the smallest known factor (noted if it isn't)) 2) Largest potential factor attempted I ask that the two items are human-readable at the very least. I've pulled a couple of files off mersenne.org (FACTORS.ZIP and NOFACTOR.ZIP) as well as off Alex Kruppa's page. While the files appear complete as far as I can tell, they only cover the ranges of p between 11 - 9,999,991 and 33,219,281 - 35,999,993. They also don't cover *all* known factors! Any and all information on the ranges between 10M - 33.22M and 36M is greatly appreciated, as well as any known factors not listed in the files I've pulled. Eric Hahn _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factors of DecMega
Scott/all, I downloaded the newest beta for Prime95V19, and set it to ask for 10,000,000 digit Mersennes. In my worktodo.ini file, I got the line: Test=33219379,32 This surprised me! I had tested this number to 2^47, and Alex Kruppa had tested it to at least 2^55 (further investigation revealed 2^60). You should update primenet's files pertaining to this off of those at http://www.informatik.tu-muenchen.de/~kruppa/M33M/index.html -Lucas Wiman _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
