mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Data

Reply
 
Thread Tools
Old 2003-11-18, 06:22   #1
dswanson
 
dswanson's Avatar
 
Aug 2002

3108 Posts
Default Missed small factors

k5gj, GP2, and I have been having a PM exchange about factors that were missed during trial factoring. This exchange was prompted by a message GP2 received from k5gj, who has been running P-1 on exponents that have long since been verified composite by LL testing:

Quote:
k5gj wrote:
GP2,

I do not know if you are interested in anomalies, however,
the following 16 digit factor is a great example of why we
should run P-1 tests.

[Sat Nov 15 16:25:13 2003]
P-1 found a factor in stage #2, B1=262144, B2=26214400.
UID: k5gj/4, M268813 has a factor: 1017111715779881


Here are three more 17 digit factors that I found last month.

[Thu Oct 09 02:02:53 2003]
P-1 found a factor in stage #2, B1=2048, B2=204800.
UID: k5gj/1, M2441083 has a factor: 75649430225324231
[Thu Oct 09 15:58:17 2003]
P-1 found a factor in stage #1, B1=2048.
UID: k5gj/1, M2448961 has a factor: 95075864569432231
[Tue Oct 28 05:04:50 2003]
P-1 found a factor in stage #2, B1=2048, B2=204800.
UID: k5gj/1, M2623141 has a factor: 23522191782267041
All four of these factors should have been found during trial-factoring. The bit depth of these for factors is
Code:
                      Bit     Report TF
    Exponent         Depth      Depth
 1017111715779881    49.85        57
75649430225324231    56.07        59
95075864569432231    56.40        59
23522191782267041    54.38        59
where the final column is the depth to which the nofactor.txt file stated that the exponent had been trial-factored. Hence, as both k5gj and GP2 pointed out, these "easy" factors were apparently missed during trial factoring, resulting in two unnecessary LL tests each (first test plus doublecheck).

I got pulled into this exchange because GP2 had recently run across a two-year old posting of mine in a mailing list archive:
Quote:
dswanson wrote:
You either have an extremely good memory, or you've been rereading old postings from the mailing list recently. Yes, about two years ago I found a range in which a bunch of factors seemed to have been missed. I found the first number in this range the same way - a P-1 result with an anomalously low bit depth. There was a discussion of this in Digest issues 887 through 890. If a thread gets started, it would probably be worth pasting the relevant items from those Digests into the thread.

If I recall correctly, I determined that the full range of incompletely factored exponents was 7019000 - 7055000. I subsequently factored a fraction of this range to 2^58, but didn't devote the resources to factor it any deeper. At the time the leading edge of doublechecks was within this range. To avoid poaching and unncessary work, I factored all exponents that were not yet assigned, plus any exponents that expired. I did not touch any exponents that were in progress, nor any that had already completed the second test.

Unless someone else subsequently factored this range, I am sure there are still missing factors between 2^56 and 2^64 [sic - final number should be 2^62].
For those with access to the mailing list digests, the discussion was in digest #887 - #890. For those without, I am posting the exchange below. There are a lot of interesting points made, most of which are still quite relevant.
dswanson is offline   Reply With Quote
Old 2003-11-18, 06:23   #2
dswanson
 
dswanson's Avatar
 
Aug 2002

C816 Posts
Default

Date: Sun, 30 Sep 2001 15:26:51 -0700
From: "Daniel Swanson" <email address deleted>
Subject: Mersenne: Factoring failure?

Yesterday I was assigned M7027303 to doublecheck. The number came with the
claim that it had no factors less than 62 bits. But my P-1 factorization of
the number found this 55-bit factor:

[Sun Sep 30 13:53:26 2001]
P-1 found a factor in stage #1, B1=35000, B2=463750.
UID: dswanson/nosnawsd, M7027303 has a factor: 31090234297428433

I thought this was mighty peculiar, so I stuck "Factor=7027303,0,0" into my
worktodo file to force a complete refactorization of the number. Sure
enough, about three minutes later out pops the result:

[Sun Sep 30 15:06:10 2001]
UID: dswanson/nosnawsd, M7027303 has a factor: 31090234297428433

Somebody wasted a lot of time doing a first-time LL test on this number.

Does anybody have any idea how common factoring errors might be in the
"exponents not factored" database, particularly since doublechecks are not
commonly done on the factoring results?

Dan
dswanson is offline   Reply With Quote
Old 2003-11-18, 06:24   #3
dswanson
 
dswanson's Avatar
 
Aug 2002

110010002 Posts
Default

Date: Sun, 30 Sep 2001 16:07:34 -0700
From: "Daniel Swanson" <email address deleted>
Subject: Mersenne: Re: Factoring Failure?

A follow-on to my previous message: I went through the Cleared Exponents
report looking for other examples of factors found during double-checks that
should have been found during the initial factorization. I found the
following 7 examples, including the one I just reported:

5977297 53 DF 6726544627832489 26-Aug-01 12:03 TempleU-DI C031EBA9B
6019603 57 DF 137024179940485697 18-Aug-01 18:55 TempleU-DI C031EBA9B
7019297 57 DF 160100125459121849 27-Sep-01 22:52 TempleU-DI TD01489_Cub1
7020641 58 DF 226230108157229263 30-Sep-01 02:05 RayPelzer Homebase
7025987 56 DF 74052063365823791 30-Sep-01 01:12 shaneamy P600A
7027303 55 DF 31090234297428433 30-Sep-01 20:58 dswanson nosnawsd
10159613 56 DF 68279769831982367 19-May-01 10:13 hornup lbe_pc

Seems to be a big clump in the 701xxxx - 702xxxx range. Given that this is
at the leading edge of numbers currently being assigned for double-checks,
I'd be willing to bet several more will turn up in the next few days.

Were numbers in this range all originally factored by the same user or
computer?

Another interesting note: Given the number of different computers working
double-checks, what are the odds that TempleU-DI/C031EBA9B would pick up TWO
of these?!?

Dan
dswanson is offline   Reply With Quote
Old 2003-11-18, 06:25   #4
dswanson
 
dswanson's Avatar
 
Aug 2002

110010002 Posts
Default

Date: Mon, 01 Oct 2001 15:01:05 -0400
From: George Woltman <email address deleted>
Subject: Re: Mersenne: Re: Factoring Failure?

Hi,

At 04:07 PM 9/30/2001 -0700, Daniel Swanson wrote:
>I went through the Cleared Exponents
>report looking for other examples of factors found during double-checks that
>should have been found during the initial factorization.
> 5977297 53 DF 6726544627832489
> 6019603 57 DF 137024179940485697
> 7019297 57 DF 160100125459121849
> 7020641 58 DF 226230108157229263
> 7025987 56 DF 74052063365823791
> 7027303 55 DF 31090234297428433
>10159613 56 DF 68279769831982367
>Were numbers in this range all originally factored by the same user or
>computer?

My logfiles from that long ago have been zipped and stored on CDROM.
It is possible that 7,010,000 - 7,030,000 were all factored by one person.
It was not uncommon for me to hand out large blocks for factoring to
users without Internet connections. While I no longer do this, there are
a handful of users pre-factoring the 20,000,000 - 80,000,000 area. I hope
their machines are reliable!! They probably are as they are finding the
expected number of factors.

Anyway, it doesn't appear to be a program bug as you were able to find
the factor with trial factoring. I'm guessing either bad hardware or an older
prime95 version had a bug. Either way, GIMPS has never considered
missing a factor as a big deal. It only means some wasted effort running
a LL test that could have been avoided.

Thanks for the interesting findings!

Regards,
George
dswanson is offline   Reply With Quote
Old 2003-11-18, 06:26   #5
dswanson
 
dswanson's Avatar
 
Aug 2002

23×52 Posts
Default

Date: Mon, 1 Oct 2001 22:23:38 +0200
From: "Jean-Yves Canart" <email address deleted>
Subject: FW: Mersenne: Re: Factoring Failure?

Hello all,

I have browsed some logs I archived long time ago and I have found this:

In may 1998, one user, "tomfakes", cleared around 80 exponents with factor
found = "1"
It was in the range 7013000-7055000.

Regards,

Jean-Yves
dswanson is offline   Reply With Quote
Old 2003-11-18, 06:26   #6
dswanson
 
dswanson's Avatar
 
Aug 2002

C816 Posts
Default

Date: Tue, 2 Oct 2001 19:52:42 -0000
From: bjb <email address deleted>
Subject: Re: FW: Mersenne: Re: Factoring Failure?

On 1 Oct 2001, at 22:23, Jean-Yves Canart wrote:

> I have browsed some logs I archived long time ago and I have found
> this:
>
> In may 1998, one user, "tomfakes", cleared around 80 exponents with
> factor found = "1" It was in the range 7013000-7055000.

Well, (s)he's not lying - 0 = n (mod 1) is a property of integers ;-)

In any event:

(a) this is the _opposite_ of the reported problem - what seems to
have happened is that "no factor found" was being reported,
sometimes erroneously;

(b) this won't get through now PrimeNet validates submitted
factors; the code I wrote for this purpose rejects as garbage any
single-digit factor, after stripping off any leading zeroes as well as
white space.

(Obviously a Mersenne number with a prime exponent p > 5 cannot
have any factors less than 10, and we know pretty much all there
is to know about exponents up to and including 5, so excluding
these is not a practical problem).

> > At 04:07 PM 9/30/2001 -0700, Daniel Swanson wrote:
> > >I went through the Cleared Exponents
> > >report looking for other examples of factors found during
> > double-checks that
> > >should have been found during the initial factorization.
> > > 5977297 53 DF 6726544627832489
> > > 6019603 57 DF 137024179940485697
> > > 7019297 57 DF 160100125459121849
> > > 7020641 58 DF 226230108157229263
> > > 7025987 56 DF 74052063365823791
> > > 7027303 55 DF 31090234297428433
> > >10159613 56 DF 68279769831982367
> > >Were numbers in this range all originally factored by the same user
> > >or computer?
> >
> > My logfiles from that long ago have been zipped and stored on CDROM.
> > It is possible that 7,010,000 - 7,030,000 were all factored by one
> > person. It was not uncommon for me to hand out large blocks for
> > factoring to users without Internet connections. While I no longer
> > do this, there are a handful of users pre-factoring the 20,000,000 -
> > 80,000,000 area. I hope their machines are reliable!! They
> > probably are as they are finding the expected number of factors.

The primes from that block of 20,000 numbers represents quite a
bit of work and maps poorly onto the "missed" factors reported.

A few mistakes are inevitable but, since testing a factor takes of
the order of a microsecond on current systems, hardware glitches
shouldn't be much of a risk. (? Unless they get into the code
stream used to generate potential factors?) Reports of two
"missed" factors of exponents within spitting distance of 6,000,000
and no less than four just over 7,000,000 looks high for random
glitches to be responsible, even on really ropy hardware.
Remember that P-1 (which found the factors missed by trial
factoring) can only find a small proportion of the "small" factors,
especially when it's being run with "double checking" limits.
> >
> > Anyway, it doesn't appear to be a program bug as you were able to
> > find the factor with trial factoring. I'm guessing either bad
> > hardware or an older prime95 version had a bug.

If it _was_ Prime95. There are other factoring programs out there;
maybe there was a higher incidence of use about 3.5 years ago
when these exponents would have been the subject of factoring
assignments.

> > Either way, GIMPS
> > has never considered missing a factor as a big deal. It only means
> > some wasted effort running a LL test that could have been avoided.

True enough - though I'm concerned that the "no factors below 2^N"
database may be seriously flawed, from the point of view of GIMPS
it would seem to be a waste of time to go round redoing trial
factoring just to fix this problem.

However if it could be established that all the "missed" factors
reported were the work of one user, perhaps it would be worth fixing
the database to force rerunning of trial factoring for those factoring
assignments run by that user when the exponents are reassigned
for double checking (or LL testing).


Regards
Brian Beesley
dswanson is offline   Reply With Quote
Old 2003-11-18, 06:27   #7
dswanson
 
dswanson's Avatar
 
Aug 2002

23×52 Posts
Default

Date: Tue, 2 Oct 2001 23:09:31 -0500
From: "Steve Harris" <email address deleted>
Subject: Re: FW: Mersenne: Re: Factoring Failure?

> > Either way, GIMPS
> > has never considered missing a factor as a big deal. It only means
> > some wasted effort running a LL test that could have been avoided.

>True enough - though I'm concerned that the "no factors below 2^N"
>database may be seriously flawed, from the point of view of GIMPS
>it would seem to be a waste of time to go round redoing trial
>factoring just to fix this problem.


Yes, from the point of view of GIMPS (that is, searching for Mersenne
primes) it's not a huge deal... but there also exists an effort to fully
factor the candidates that are not prime, and this throws a big problem into
that project. Someone could be trial factoring an exponent from 2^59 to 2^65
and find a factor in that range after a smaller factor had been missed, and
it will go into the database as the smallest factor when it actually is not.
Might be decades before the smaller factor is discovered.

Oh well,
Steve
dswanson is offline   Reply With Quote
Old 2003-11-18, 06:28   #8
dswanson
 
dswanson's Avatar
 
Aug 2002

110010002 Posts
Default

Date: Wed, 3 Oct 2001 02:30:10 -0400
From: "Carleton Garrison" <email address deleted>
Subject: Re: FW: Mersenne: Re: Factoring Failure?

> At 04:07 PM 9/30/2001 -0700, Daniel Swanson wrote:
> >I went through the Cleared Exponents
> >report looking for other examples of factors found during
> double-checks that
> >should have been found during the initial factorization.
> > 5977297 53 DF 6726544627832489
> > 6019603 57 DF 137024179940485697
> > 7019297 57 DF 160100125459121849
> > 7020641 58 DF 226230108157229263
> > 7025987 56 DF 74052063365823791
> > 7027303 55 DF 31090234297428433
> >10159613 56 DF 68279769831982367
> >Were numbers in this range all originally factored by the same user
> >or computer?

> Either way, GIMPS
> has never considered missing a factor as a big deal. It only means
> some wasted effort running a LL test that could have been avoided.

I wonder if by using configuration settings, people are able to skip as
many, if not all, factoring stages?

I believe the idea of trying to skip P-1 factoring was talked about within
the last 3 or 4 months. Apparently there are people who would just prefer
to get credit for doing LL work than to find factors. Until factoring time
(while one is LL testing) is at credited at the same same rate as LL
testing, let alone getting credited not at all (most of the time no factors
are found), results like the above could become common place.
dswanson is offline   Reply With Quote
Old 2003-11-18, 06:28   #9
dswanson
 
dswanson's Avatar
 
Aug 2002

23×52 Posts
Default

Date: Wed, 3 Oct 2001 02:41:27 -0500 (CDT)
From: ribwoods <email address deleted>
Subject: Mersenne: Re: Factoring Failure?

Daniel Swanson wrote:
> 5977297 53 DF 6726544627832489
> 6019603 57 DF 137024179940485697
> 7019297 57 DF 160100125459121849
> 7020641 58 DF 226230108157229263
> 7025987 56 DF 74052063365823791
> 7027303 55 DF 31090234297428433
>10159613 56 DF 68279769831982367

I'm pretty sure the second column is the previous trial-factoring
limit, in units of power-of-2.

For M7019297, the found factor 160100125459121849 is larger than 2^57
(= 144115188075855872), and for M7025987, factor 74052063365823791 is
greater than 2^56 (= 72057594037927936). Unless I'm misinterpreting
something, those two cases don't indicate a trial-factoring failure.

[dswanson comment on this posting: ribwoods is correct about the bit depth of the found factor. For example, the bit depth of 160100125459121849 is 57.15, which rounds down to the "57" listed. But ribwoods missed the point, which is that nofactor.txt had claimed that this exponent had no factor below 2^62. So it is indeed a trial-factoring failure.]
dswanson is offline   Reply With Quote
Old 2003-11-18, 06:29   #10
dswanson
 
dswanson's Avatar
 
Aug 2002

23×52 Posts
Default

Date: Wed, 3 Oct 2001 12:40:29 -0400
From: "Carleton Garrison" <email address deleted>
Subject: Re: FW: Mersenne: Re: Factoring Failure?

> > I believe the idea of trying to skip P-1 factoring was talked about
within
> > the last 3 or 4 months. Apparently there are people who would just
prefer
> > to get credit for doing LL work than to find factors.
>
> This is why I like that you loose credit for a LL-test if someone else
> finds a factor later, or if two other independant checks prove your
> result to be wrong.

Me too. I understand that George's top producer page does this, while the
PrimeNet stat page does not. PrimeNet really needs this capability.

Carleton Garrison LL#163 F#295 G#253 www.teamprimerib.com
dswanson is offline   Reply With Quote
Old 2003-11-18, 06:30   #11
dswanson
 
dswanson's Avatar
 
Aug 2002

23·52 Posts
Default

Date: Wed, 03 Oct 2001 18:29:52 -0700
From: Gerry Snyder <email address deleted>
Subject: Re: FW: Mersenne: Re: Factoring Failure?

Carleton Garrison wrote:
>
> [? wrote:]
> >
> > This is why I like that you lose credit for a LL-test if someone else
> > finds a factor later, or if two other independant checks prove your
> > result to be wrong.
>
> Me too. I understand that George's top producer page does this, while the
> PrimeNet stat page does not. PrimeNet really needs this capability.

To me, there is no question that an LL test that is shown to be wrong
should not count for anything. The number still required two more LL
tests, so that it as if the erroneous one had not been done.

But, at least in theory, every Mersenne number proven non-prime will
eventually be factored. Again, to me, so what? At least the LL test
showed that further factoring activity would eventually succeed.

I have nothing against George doing things that way. (When I play ball
with him, I play by his rules or I don't play at all. You know why?
Because it's his ball, that's why.) Seriously, I can see some point to
doing things that way, but I would do probably do it differently.

But even more seriously, I'm just glad to be in the game, and I am
grateful to George and all the others who have made it easy and fun to
participate.

Gerry

PS I just got a chuckle from imagining a very competitive team tearing
down an opponent by finding what numbers the opponent had done LL tests
on, and factoring them.
dswanson is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
More missed factors lycorn Data 76 2015-04-23 06:07
Missed factors TheMawn Information & Answers 7 2014-01-10 10:23
Optimal Parameters for Small Factors patrickkonsor GMP-ECM 16 2010-09-28 20:19
Awfully small factors.... petrw1 Lone Mersenne Hunters 17 2009-11-20 03:40
Small factors Kees PrimeNet 6 2006-11-16 00:12

All times are UTC. The time now is 20:04.

Mon May 10 20:04:45 UTC 2021 up 32 days, 14:45, 1 user, load averages: 3.20, 3.56, 3.47

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.