Using Factors to Eliminate Candidates

[Mivacca2]

Ok maybe this is stupid or somebody already thought of this, but I was just thinking the other day to myself (calle me a math nerd if you want to) a prime number is a number that is divisible by one and itself correct?
Well what if we knew factors (IE the factors that we find for potential primes) and multiplied them with other factors enough (at least one, since our mersenne numbers shouldn't be multiples of eather other) until we are at the magnitude large enough to cancel out possible numbers waiting to be factored and just work in revers? If the program already does this, but i am not sure if it does or not. Would this be more tedious and time consuming than just sitting down and calculating the primality test? Or would you even need an entirely different program to make something like this work? If this isn't an original idea it really came to me the other day, and I apologize for stepping on anybody's toes, and for any lack of coherency, but i think that if somebody were to ask questions i might be able to respond more precisely. Thanks for your time, and I hope that this might turn out to be helpful eventually.
MiVacca

[cheesehead]

MiVacca, yours is a reasonable suggestion which could potentially speed our work a lot. Another way to say it (let me know if this is not what you meant) is that instead of expending a lot of effort on each Mersenne number to find one of its factors, try simply starting with potential factors, then rapidly compute the Mersenne numbers which each factor would divide, then efficiently check-off a large proportion of Mersenne composites, leaving few that have to be checked by more tedious means.

Yours is indeed the kind of idea that could be a breakthrough ... but ... yes, it's been thought-of and investigated earlier.

(The following two paragraphs were added/modified by editing.)

This was discussed on the Mersenne mailing list from 2002 March 20 to March 26 with the subject "Factors aren't just factors". The postings appear in Mersenne Digests #948-951. Note: the reverse-factoring idea as outlined above appears about halfway through that thread.

That earlier discussion found that your idea is efficient for smaller-exponent Mersenne numbers, but becomes less efficient as the numbers get larger. GIMPS's current work is up in the inefficient range.

(The following was my original inaccurate statement that I, working from memory, posted here before I found the previous discussion:

The earlier analysis found that after one considers certain mathematical and computational details of this method, it turns out, perhaps counter-intuitively, to be less efficient than the methods already used by GIMPS.

)

However, just because this idea has previously been investigated and analyzed does not necessarily mean that there is no value to this idea. It is possible that there was an oversight or error in the previous study, or that some variation of this idea or combination with some other idea that no one's yet contemplated might turn out to be a genuine significant improvement. Please consider pursuing it further if you read the previous work and still see some possibility for improvement.

[philmoore]

I don't know much about the details, but I do know that Will Edgington (and maybe others?) did something like this in the early days of GIMPS. They called it "reverse factoring", picking a prime q and finding out which Mersenne number 2^p-1 was the first which was a multiple of q. If p turned out to be prime, then 2^p-1 was eliminated as a Mersenne prime candidate. Now the question would be, how high did he go in q, and would today's faster computers (together with the increased time it now takes to do a Lucas-Lehmer test) justify extending this range? I would love to hear from someone who knows more about this.

[jocelynl]

I did some test on reversed factoring a couple years ago. And it turn out to be very slow. George pointed out then that it was too time consuming. Like finding a needle in a haye stack. I see it as finding the location of all stars to know were you`re located on earth. There are just too many! There are much faster ways to factor a number.

[philmoore]

Thanks, cheesehead, for researching this. One interesting post in the thread you cited is:
http://www.mail-archive.com/mersenne@base.com/msg07151.html

[Mivacca2]

Sorry guys for not doing the necessary requisite research... =) It was an idea though... maybe something can still come of it who knows.

THX mivacca

[Cyclamen Persicum]

All Mersenne Divisors is +/- 1 (mod 8) and is 2kp + 1

[Exluminis]

That's true. It's always good to produce your ideas. Now I will state mine--
All of the work is done in base 10.
Stored numbers in memory can be interpreted easily as base 2 or 16.
Why not find similarities in structures from base 3,7, 9 [common as last digits in these systems-- one of thousands of things that are easily observed] (disc. log conversions of - the base 10 and decimal systems)
Then from the data collected cross reference like the human brain.
Digital refresh of higher end relationships
It goes more into the non-logical functions of a non-deterministic system versus total randomness, bases of paradox and existence can be applied in this scenario
something
sorry..

Sorry my brain is a scatter right now. Maybe somebody from this project can email me tomorrow about this?
- ultimic@x-mail.net
- [ The theory of "Connectivity through Universal Proximity Factors and Redundancy" (*William Sawyer 1) ]
- Bye all. 34486710031212

[ewmayer]

Originally Posted by Exluminis

Sorry my brain is a scatter right now.

Have you considered switching to decaf?