Multiplication method for factoring natural numbers

[ThiloHarich]

Sorry.

The sum of all divisors - not only the prime divisors I thought of - can be higher then the number itself. So I misinterpreted your model.

So yes abundant numbers https://en.wikipedia.org/wiki/Abundant_number are good candidates.
But for example 105 and 15 are no such numbers but are good 'k'.

[nesio]

Originally Posted by ThiloHarich

Sorry.

The sum of all divisors - not the prime divisors I thought of - can be higher then the number itself. So I misinterpreted your model.

So yes abundant numbers https://en.wikipedia.org/wiki/Abundant_number are good candidates.
But for example 105 and 15 are no such numbers but are good 'k'.

Sum means here the amount, quantity.

[Till]

Originally Posted by nesio

Sum means here the amount, quantity.

We have some language problems here. Just to clarify:

12 has divisors 1, 2, 3, 4, 6, 12. Is 6 the result you mean, or is it 28?

Originally Posted by ThiloHarich

why should my model be very rough?

The rough model is the one he proposed, not yours:

Originally Posted by nesio

You can check this rough (very rough) model of m on your source data of n:
maximum(S/(m^1/3)) and m < n^1/3,
where S - the sum of all divisors of m.
Here are S and m^1/3 have equal weights in maximum function.
What will be?

I interprete this as follows:

The quality of a multiplier m is about S/(m^1/3), where we consider m < n^1/3 only.


S might be
a) the sum of divisors of m, or
b) the number of disivors of m.
My first question in this post aims to clarify which of the two options is the correct one.

nesio, do I get that right so far?

[nesio]

A rough model of m:
Find the maximum of (S/(m^1/3)) when m < n^1/3,
where S - the number of all divisors of m (excluding 1 and m).
Here are S and m^1/3 have equal weights in maximize function.

[Till]

Originally Posted by nesio

S - the number of all divisors of m (excluding 1 and m).

Ok, now we understand that one.

Originally Posted by nesio

A rough model of m:
Find the maximum of (S/(m^1/3)) when m < n^1/3,
where S - the number of all divisors of m (excluding 1 and m).
Here are S and m^1/3 have equal weights in maximize function.

I'ld say this is not a model of m, but a procedure to choose the best m. A model would give a kind of score to any m. (at least)

Originally Posted by nesio

What will be?

A simple weighting function giving a "plus" for smooth m, a "minus" for big m.


This is no rocket science. We tested dozens of ways to arrange k's according to such principles, and many other constellations...

[nesio]

Is it working on your data and what are the results?

[Till]

Unfortunately, none of our attempts to sort k's by such measures worked well.

I believe that you did not try an efficient implementation yet.
Theory (aka computational complexity, counting iterations being a simplified version of) and reality (measuring speed) are quite different for "small" factoring algorithms.
After all, this is the only reason why Lehman or Hart algorithms have a right to exist. Otherwise NFS would wipe out all other algorithms at any number scale.

If you try to optimize Hart/Lehman for small n, say n<=60 bit, then you will realize that instructions that are very fast on that number scale have a big or even decisive impact on the general performance. Complexity theory is often not strong enough to capture such influences. Storing the sqrts of k or of km is such a point. Without it, you will not be able to get a really fast Hart/Lehman implementation. Using congruences is a theoretical improvement, but also necessary.


You can disprove my assumption that you did not try an efficient implementation yet by posting a fast piece of software ;-)

[nesio]

For example such rough model (procedure) gives these values m from n
n m
555 6
5555 12
55555 36
555555 60
5555555 120
55555555 360
555555555 720
5555555555 1680
55555555555 2520
555555555555 5040
5555555555555 5040
55555555555555 5040
555555555555555 5040
It is light and quite workable way for m in "multiplication method" we hope.

Til!
Our work is a research and a paper about Recursive Multiplication algorithm and its relation to Simple Multiplication algorithm.
Your work is improving Lehman and Harts algorithms.
You asked us about our vision regarding m. We wrote then.
Something does not suit you in our discussion?
Let's not continue to cross the red and wet ;-)
We think you and Thilo should write a paper about your work that may be interesting not only in that forum.

[Till]

Hi nesio,
sorry if I have been unpatient. I do not understand Russian, so I cannot get all information from your paper. And it took some time to get some interesting information from you.



I will try to implement your particular proposition of sorting m by

score(m) = S(m) / n^(1/3) with S(m) = sum of divisors(m) without 1 and m

this evening.


Maybe we made an error so far in our evaluations of the smoothness of m's. We will see.


You said that the computation of score(m) above is a very rough model. What would a more elaborate model look like?

[chalsall]

Originally Posted by Till

What would a more elaborate model look like?

Just to share, it's been wonderful watching you two work with each other. Inspiring!

[ThiloHarich]

- Choosing the right m depends on the implementation.

Til and me used some adjustments/improvements for odd multipliers m -> in our algorithm the good multipliers are not only even, best multipliers are odd.

the numbers from nesio model : 6,12,36,60,120,360,720,1680,... do not appear in the list of good multipliers for this tuned algorithm in the top

- the number of divisors is the product of the exponents + 1 of its prime factors

If the exponents are all 1 then this is just 2^(number of prime factors of m). Having a factor with an exponent greater then one reduces the number of divisors. -> it looks like a good measure for good multipliers. But our best multiplier 315 = 3^2 * 5 * 7 has an exponent 2.

When finding the best multipliers for numbers starting at 2^54 (and only factoring numbers with factors above n^1/3) I get a complete different list then when factoring numbers starting at 2^55.