Flipping the task of factoring on its side

[Karfston]

I've been thinking . For me, that's a dangerous set of words, especially as I may be outside my depth more than a little here, but I'm hoping that in my naivety I'm also able to present things in an outside the box way.


I've been thinking alot, and I'm wondering if there's a completely different way to approach the problem of factoring Mersenne numbers. This may take a bit of explaining, so bear with me...


What is a Mersenne number? It's 2 to the power of a prime number, less one.
Or expressed another way, in base 2, it's a string of n 1s, where n is prime.


Lets set that aside and come back to it.
---
Prime numbers are numbers without factors.
Reversing that, prime numbers are numbers you cannot construct by multiplying two numbers.
I'll come back to that also...
--

I want to look for a moment at multiplication.

Usually, multiplication takes the form of.

12
x34
----
48
360
===
408


It works, it's quick and simple to do, but lacks for a bit of elegance.
I learned to multiply via a different process as a kid. The results are the same, but the process is a bit different, and I want to express it here to use in making a point...


I take one of the numbers, and right it horizontally...
I take the other number and write it vertically. I draw a grid giving each number a row or column.
I divide the grid further into diagonal rows, then I perform the individual multiplications.





Then paying attention to only the numbers results of those multiplications and the diagonal lines, I add up the digits in the diagonal rows to get the final result.



Same math, just framing the process a bit differently. But we're dealing with Mersenne numbers. They enjoy a special relationship with base 2... surely we should try looking at this problem in base 2?



In base 2 the problem is rather simpler. The result of any multiplication is only either 1 or 0. The other thing visible in base 2 that's not readily visible in other bases, is we want the result of the multiplication to be a row of 1s.



You might notice, I'm not trying division here.



For my first proposal, I don't want to be doing division, or in a sense, multiplicaiton either.

Not for the first idea I have. I want to know if there are rules I can use to construct a row of all 1s, or rules to one number and extend/modify/etc it so that I can multiply it by a second number to generate a row of all 1s. Can I turn this into a genuine logic game of 'light all the torches', with simple rules to make it playable? Are there rules for such a game that will let me construct factors for Mersenne numbers?

The other thought here is, if there are rules I can use to extend an existing pair of base 2 digit strings, to 'light all the torches' for consecutively larger Mersenne numbers, I'd then like to be able to pick an arbitrary starting number and add digits to it in an effort to construct a factor for larger and larger Mersenne numbers. I wouldn't be trying to find factors for a given Mersenne number. I'd be trying to find factors for 'any Mersenne number', walking out to larger and larger numbers. I'd see it as a difficult task that might mostly miss it's target, but even if each such walk to larger and factors only collides with a single Mersenne number, it may provide useful progress forward in narrowing the search for the next prime.

My end goal here is simply to present the well established problem in a different way. To present it not as a daunting challenge of "do math with really big numbers", but as a fairly straight forward puzzle of a completely different sort.

[Uncwilly]

To me it looks like you are mostly just playing around.
Do you know that factors for Mersenne numbers can only follow a specific form?
Did you know that there are ways to further eliminate candidates to further limit the testing?

And your "different way" of doing the multiplication is just a different way of arranging the data.

And how well does your idea work for a number 1000 decimal digits long? How much work is it vs traditional trial factoring?


edit: This may wind up in Misc Math soon. So don't rant too hard on the OP.

[kriesel]

Hi,
I suggest reading soon, https://www.mersenneforum.org/showpo...21&postcount=7 and https://www.mersenneforum.org/showpo...23&postcount=6 and then branching out to more of the content there.
There's a big learning curve; I've been at it for years.

[Karfston]

Originally Posted by Uncwilly

To me it looks like you are mostly just playing around.

To an extent, yes, that's what I'm doing. Perhaps I'm taking an old approach considered and discarded as having no value. Honestly, I'm seeing that for the most part the effort seems to be on factoring Mersnne numbers. Factoring is hard, and I'm by nature lazy.

Do you know that factors for Mersenne numbers can only follow a specific form?

Do you mean the factors of a specifc mersenne number? Yes.
Factors in general? Not so sure. .
Putzing through the output of a brute-force task I've currently got my computer trying out...
Mersenne - Factor (base 2)
m(3779) - 1110110000111
m(3803) - 1110110110111
m(3851) - 1111000010111
m(3863) - 1111000101111
m(3911) - 1111010001111
m(1321) - 1111011110111
m(4019) - 1111101100111
m(1361) - 1111111100111
m(1381) - 10000001011111
m(4211) - 10000011100111
m(4271) - 10000101011111
m(1453) - 10001000001111
m(4391) - 10001001001111


...I'm honestly not sure what patterns I'd be looking for there...
The last digit is always a 1, but all the factors of Mersenne numbers are odd primes. The last string of digits in the above sample tend to be a series of 1s, but that's no pattern either - they'd have to pair with a number that ends with an equal string of 0s suffixed by a 1.

Is there a pattern for which numbers make good mersenne factors for >any< potential mersenne prime? Or is that for the special case of examining a single mersenne number?


(Edit: Oh right - any number that is a factor for a mersenne number is a factor for only the one Mersenne with a prime number of digits - the process I'm looking at makes use of that property...)

Did you know that there are ways to further eliminate candidates to further limit the testing?

Candidates >should< be odd, should be prime, and should be of the form, if memory serves, of the form np-1? Pretty sure that doesn't help me narrow how I'm trying to attack the problem by much.

And your "different way" of doing the multiplication is just a different way of arranging the data.

Yes. But I'm trying to get away from the maths and into the puzzle. Yes, it's a maths puzzle. I just want to ignore the forest and look at the trees, before returning to the forest. Look at it as a system of lights that can wink on or off, rather than strings of numbers. It's that pattern that would really help what I'm trying to do. Yes, I'm posting to a maths forum saying 'don't look at the maths', which is silly. But the part of the problem I'd personally find difficult is here, where the process is ruled by patterns that give rise to discrete rules backed by math.)

And how well does your idea work for a number 1000 decimal digits long? How much work is it vs traditional trial factoring?

Hard to say, it's not exactly an apples/oranges comparison. Without the function I want, takes less than a minute to start producing factors for numbers with 4k binary digits. My math library is probably not the most efficient way to handle it either - Java's BigInteger


m(7211) - factored by 11100001010111

It moves quickly, but the numbers are still small. The advantage I'm shooting for here though is it's not focusing on specific Mersenne numbers.

So far, it looks to me like it has a possible viable end goal is to create a sieve for Mersenne numbers.

Drawn up that way...

I'll want a function z(n), where when given an n it will give a second number that n can be multiplied by to produce a string of all 1s, in base 2. It doesn't have to be the smallest such number. It just has to be 'such a number'. From there we can easily get to 'the smallest such number' using prop

Let k equal how many 1s are in n * z(n)

Take the prime factors of k - those represent the Mersenne numbers to trial factor against the original number n.


If I have a hit, that lets me mark off a known factor for
that number, it fails the sieve and can be excluded from expensive testing

Advantages, not a laser focused search of a single prime candidate.

Disadvantages, may still be slower than existing methods.

--
This will likely remain nonviable without a efficient method of generating a multiple for arbitrary numbers that yields a string of 1s in base 2, but I'm confident that piece of the puzzle is solvable.
Even with that piece, I could see this easily scaling the needed effort wrong for the large mersenne numbers, but I'm not convinced that's a given.

edit: This may wind up in Misc Math soon. So don't rant too hard on the OP.

Your board, move it where you need it. Im merely poking my nose in where I'm prone to lose it. :P



I'll give the suggested reading a look.


m(10331) factors on 101000010110111
m(12203) factors on 101111101010111
m(12263) factors on 101111111001111
m(12959) factors on 110010100111111
m(13883) factors on 110110001110111
...

[Uncwilly]

Originally Posted by Karfston

Do you mean the factors of a specifc mersenne number? Yes.
Factors in general? Not so sure.

All factors of Mersenne numbers have a specific form and this allows us to eliminate a huge number of candidates. We don't have to try all primes. You need to go look up about Trial Factoring. (Like at on the Wiki).

Candidates >should< be odd, should be prime, and should be of the form, if memory serves, of the form np-1? Pretty sure that doesn't help me narrow how I'm trying to attack the problem by much.

Again, read up on Trial Factoring of Mersenne numbers.

Hard to say, it's not exactly an apples/oranges comparison. Without the function I want, takes less than a minute to start producing factors for numbers with 4k binary digits. My math library is probably not the most efficient way to handle it either - Java's BigInteger

Nope. George's handcrafted routines are faster. As are the ones for GPU's.

Advantages, not a laser focused search of a single prime candidate.

Any factor can only be the factor of a single Mersenne number, so you have to focus on a single one at a time.