Missed small factors

[dswanson]

Date: Wed, 03 Oct 2001 18:50:21 -0700
From: Eric Hahn <email address deleted>
Subject: Mersenne: Re: MERSENNE: Factoring Failure?

>
><snip>
>> > 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.

Actually... IIRC... George noted once that the database of
smallest KNOWN factors was just that... and did NOT
necessarily mean that it contained the smallest factors of
any given exponent...

There was a bug in a previous version (v19??) which caused
Prime95 to not continue trial-factoring to find a smaller
factor after one had been found and it had been stopped
(or went to sleep)... There was also the advent of P-1
factoring which does not necessarily find the smallest
factor, but instead finds factors comprised of lots of
small factors, and can therefore miss smaller factors which
does not have lots of small factors...

In this case... the database would not necessarily have the
smallest factor for every exponent with a factor found... but
instead the smallest KNOWN factor... which is not necessarily
the smallest factor for that exponent...

Eric

[dswanson]

Date: Wed, 3 Oct 2001 21:09:48 -0700
From: "Daniel Swanson" <email address deleted>
Subject: Mersenne: Re: Factoring Failure?

Jean-Yves: Did you check to see if any or all of the exponents cleared by
"tomfakes" matches with the exponents I found in the 701xxxx-702xxxx range?

List: Three new small factors have been turned in in the past few days.
The list in the 70xxxxx range is now

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 22:14 dswanson nosnawsd
7028947 58 DF 203918491658210359 01-Oct-01 03:11 SW jobn164
7033963 56 DF 100945633281264553 03-Oct-01 07:36 TempleU-DI DellGXaGhost
7036409 58 DF 321885922408857601 04-Oct-01 02:54 MartinTraupe Maxsein

Dan

[dswanson]

Date: Thu, 04 Oct 2001 01:44:53 -0400
From: Nathan Russell <email address deleted>
Subject: Re: FW: Mersenne: Re: Factoring Failure?

On Wed, 03 Oct 2001 18:29:52 -0700, Gerry Snyder wrote:


>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.

It might be pointed out that we are still finding factors of numbers
in the same size range as some found to be prime in the 1950's, and
that it may well be (due to such things as the uncertainity principle,
the speed of light, and the need to not have to worry about whether
there actually is an electron crossing a closed switch when one ought
to) impossible to factor some of the numbers now being tested. Right
now, it's well under an hour's work to prove *any* 700 digit number
prime, but factoring general numbers of the same size in an hour would
be a very good way to get very rich (legally or otherwise) very
quickly.

>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.

If things are being done properly, they should be better off by far
doing their own tests, since the factoring bounds are chosen to stop
when it's no longer worthwhile to continue factoring in hopes of
averting both the first and second tests.

Nathan

[dswanson]

Date: Thu, 04 Oct 2001 01:52:32 -0400
From: Nathan Russell <email address deleted>
Subject: Re: FW: Mersenne: Re: Factoring Failure?

On Tue, 2 Oct 2001 19:52:42 -0000, bjb wrote:

>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).

Given the scale of the bad results (probably a fair bit over 60
exponents, at a rough guess), if I were king, I would just block the
responsible user until I got a reasonable exponent.

Many of the numbers listed in the original post, however, are already
behind the "main front" of double-checking. Of course, we would only
expect to be finding those that are, but I'd guess no more than
200-300 exponents are involved (and likely less). If it was a
computer error of some sort, I wouldn't expect to see that many
errors.

That said, I vaguely recall reading somewhere that some versions of
Windows always give the same memory range to the same program (the
context was that what appears to be an error in a given program may
cause major general problems under Linux). If that is the case, is it
possible that every time Prime95 on a given system started up its
executable was loaded on top of a bad range of memory in just such a
way as to make it impossible to find a factor (say, by changing the
expected output of the function when one is found). This is
speculation on my part, of course, but I think it's worth
mentioning....

Nathan

[dswanson]

Date: Thu, 4 Oct 2001 18:30:41 -0000
From: bjb <email address deleted>
Subject: Re: FW: Mersenne: Re: Factoring Failure?

On 3 Oct 2001, at 18:29, Gerry Snyder wrote:

> 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.

The counter-argument is that work submitted _in good faith_ should
be credited. However I quite agree that there is a nice judgement
here in how much "good faith" there is in users submitting results
from systems which are known to have serious hardware stability
issues.
>
> 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.

Might be a while, though... look at the effort needed to factor M727 -
finally succeeding about half a century after the determination of
compositeness, despite huge advances in mathematical
techniques and raw computational power.
>
> 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.

Precisely.
>
> 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.

I suspect that finding enough of those factors would cost the "very
competitive team" much more effort than it would to overtake the
opponent by applying their resources to running LL tests. If not, we
don't do enough factoring before proceeding to LL testing.

If you really want an insight into "competitiveness", just look at
what goes on in projects like RC5. Unauthorized use of systems
appears to be fairly common, as are counter-accusations of this
activity. Denial-of-service attacks on networks hosting systems run
by competitors are not unknown. Extreme overclocking to the point
of serious instability appears to be almost "de rigeur" (except on
systems "borrowed" from other users!).

Personally I would far prefer not to have league tables at all
because they do tend to encourage these sorts of antisocial
behaviour, though I do accept that they can and do also encourage
legitimate users to "try harder".

The effort people like me put in to trying to find factors of "small"
Mersenne numbers is _for fun_ - an effective way of using
resources which are not suitable for LL testing for one reason or
another. Given the tiny credit for running LL tests on small
exponents, any damage to individual users' ratings in George's
tables is likely to be imperceptible.

Finally, and here's the point: though, from the point of view of
someone trying to find first factors, it doesn't matter whether a
known factor is actually the smallest, it _is_ highly desirable that
the database of previous unsuccessful factoring effort is
_reasonably_ accurate. Finding a "missed" small factor using an
advanced technique may or may not be successful, but it's an
expensive way of doing the job.


Regards
Brian Beesley

[dswanson]

Date: Tue, 9 Oct 2001 23:23:19 +0200 (MET DST)
From: Reto Keiser <email address deleted>
Subject: Mersenne: Re: Factoring Failure?

Hi all,

Daniel Swanson wrote:
> 7019297 57 DF 160100125459121849 27-Sep-01 22:52
> 7020641 58 DF 226230108157229263 30-Sep-01 02:05
> 7025987 56 DF 74052063365823791 30-Sep-01 01:12
> 7027303 55 DF 31090234297428433 30-Sep-01 22:14
> 7028947 58 DF 203918491658210359 01-Oct-01 03:11
> 7033963 56 DF 100945633281264553 03-Oct-01 07:36
> 7036409 58 DF 321885922408857601 04-Oct-01 02:54

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

Actually, when a factor is found, the primenet server returns the size
of the factor in bits, but it rounds the value Log2(factor)
mathematically to the next integer and not always upwards what would
make more sense. Therefore the factor can be bigger than 2^n shown in
the second column.

There are some people doing broadband factoring, what means that they
extend the factoring limit on a big range of numbers by 1 or a few bits
using the factoroverride option. Hence, it is very likely, that the
fault happened during that process and not by the person who was doing
the first LLTest (At that time the P-1 Test was not available yet, and
the factoring limit beyond the factor).
While completing some trial factoring in the 60 million range I noticed,
that the prime95 checksum of factoring from 65 to 66 bits and from 66 to
68 bits are the same (I did this two parts of the same exponent on
different computers). That means that it is easily possible that some
mistakes can happen, when someone writes the 'Factor=' line into the
worktodo file. Another reason might be, that one person ran a broadband
factoring range from 55 to 58 bits on one computer, from 58 to 59 on
another (to split up the work) and forgot to check in the former
results. As there is no information about the starting bit in the result
file, the primenet server is not able to detect that problem.

I think the easiest way to fix this problem is to recheck these ranges,
which were completed by the user(s) where more than one factor appeared.
As the server also logs the id, that would not be too difficult to
realize.

Probably that problem might become worse in future:
George told me, that primenet shows the clients, that a p-1 is already
done, by adding 0.5 to the factoring limit. Prime95 detects that
correctly, but in the reports these values are rounded to the next digit
(64.5 -> 65 and so on). If someone takes the factoring information from
these lists, if would cause a gap of one bit in the factoring process. I
suggest to change the rounding behavior of the primenet server or to
decrease the value which indicates a completed p-1 test from 0.5 to 0.4.

I hope that we will find the missing factors without too much effort.

Regards,

Reto

[garo]

This has made think up another task for GP2. Would it be possible to go through the list of found factors - upto 20 million or whatever and verify that the number of factors found at each bit is what is expected?

[geoff]

Perhaps we could develop a torture-test specifically for factoring. For example, find the sum of all factors in a mixture of bit ranges on a given list or range of exponents.

It could also serve as a factoring benchmark, which might be of interest to Lone Mersenne Hunters.

It wouldn't need any change to Prime95, it could be done in a script language that reads the results.txt file and compares it to data from the factors.cmp file.

[GP2]

Originally posted by garo
This has made think up another task for GP2. Would it be possible to go through the list of found factors - upto 20 million or whatever and verify that the number of factors found at each bit is what is expected?

I did some preliminary checking.

I see an unexpectedly low number of "large" factors at 21.9M. However, this range is entirely absent from the summary.txt report (it jumps from 21.8M to 22.0M) since it's a manual range. Maybe the guy should check in his interim factors found.

I see an unexpectedly high number of "large" factors at 33M. But that's normal because that's the 10-million digit range, so there has been P-1 factoring that finds additional factors.

Finally, I see some mild evidence of too few factors in the range 5.98M to 6.00M (and maybe slightly beyond on each side).

I'm experimenting with different histogram bin sizes and different cutoffs for "large" factors to try to get the clearest graph.

[GP2]

Originally posted by GP2
Finally, I see some mild evidence of too few factors in the range 5.98M to 6.00M (and maybe slightly beyond on each side).

The standard bit depth in this range is 62.

There are 512 unfactored exponents in this range, and my guess is that we could be missing 20 - 50 factors that should have been found during TF.

A really thorough check would be from 5.94M to 6.02M.

[Uncwilly]

Sounds like a job for the "Mersenne-aries".