Multiplication method for factoring natural numbers - Page 3

nesio · 2019-04-04, 14:21

Quote:

Originally Posted by DukeBG

They just meant "interesting", a mistranslation. "Program realization" was supposed to be "implementation", et cetera. Minor language barrier.

DukeBG! You are quite right. We meant curiosly, interestingly. Thanks.

Till · 2019-04-04, 14:26

nesio,

in fact we believe that Hart_Fast and Lehman_CustomKOrder are pretty fast.
If you have something better then just show it. Your SM pseudocode will hardly be it. The minimal improvement in iterations of RM is not impressive either.

Some comments on your points:
1. We do that in our implementations but did not in Hard_Nesio, because it is not in the SM pseudocode.
2. I demonstrated with my performance test that this is not helpful. 10080 seems to be the best multiplier for any n if you store the sqrt's. 3. We did understand that.
4. What do you mean with "fast multiplication", replace it with iterated addition? This makes hardly a difference in Java. Maybe the compiler is doing that for us.
5. That might be interesting.
6. Which one's?

nesio · 2019-04-04, 14:52

Quote:

Originally Posted by Till

nesio,

in fact we believe that Hart_Fast and Lehman_CustomKOrder are pretty fast.
If you have something better then just show it. Your SM pseudocode will hardly be it. The minimal improvement in iterations of RM is not impressive either.

Some comments on your points:
1. We do that in our implementations but did not in Hard_Nesio, because it is not in the SM pseudocode.

That was because we took Hart as is (we wrote above).

Quote:

2. I demonstrated with my performance test that this is not helpful. 10080 seems to be the best multiplier for any n if you store the sqrt's.

We meant flexible way (not constant).

Quote:

3. We did understand that.
4. What do you mean with "fast multiplication", replace it with iterated addition? This makes hardly a difference in Java. Maybe the compiler is doing that for us.
5. That might be interesting.
6. Which one's?

See
[1] R. Lehman, ‘Factoring Large Integers’. Mathematics of Computation, Volume 28, Number 126, April 1974, Pages 637-646.
[2] Hart, William B. ‘A one line factoring algorithm’, 2012. Journal of the Australian Mathematical Society, Volume 92 (Number 1), Pages 61-69.

Till · 2019-04-04, 15:03

On 2. It seems that you do not understand.
If 10080 is the best multiplier for all n, then your "flexible" approach can not be better.

On 6. We know the papers. I was asking for the magic recommendations you think we are missing.

nesio · 2019-04-04, 19:18

Quote:

Originally Posted by Till

On 2. It seems that you do not understand.
If 10080 is the best multiplier for all n, then your "flexible" approach can not be better.

We think that we understand "multiplication method" a little )) But maybe you know better how to choose a multiplier m for your program.

ThiloHarich · 2019-04-05, 13:57

a)
I have also done some investigations in optimal multipliers.
One way was just to factor many, many numbers and to record the multipliers which lead to a factorization. It turned out that some multipliers had a much higher chance to factor a number then others. Then after learning, when finding factors we iterate over the good multipliers (biggest number of factorizations) first. For moderate inputs (i.e. 'n' below 40 bits) using the list of good multipliers gives a reasonable speedup (~10%). The list of good multipliers has some kind structure for lower multipliers (lets say < 8000). But above a certain limit this structure seems to be gone.

b)
There are only c*k^1/3 multipliers. So we can easily create them before factoring numbers n < 2 ^ 54 and store them in an array off size 1.000.00 . This is what i have done in a). For numbers above 2^52 The Brent Pollard Rho algorithm is faster anyway.

c) An other way to avoid the cost of multiplying the k_i is to use a gray code style iterative iteration over the multipliers. Here in each iteration only one multiplier will be exchanged.

d)
Above n > 40 Bits choosing a fixed multiplier still works best. Without applying some mod 2^k arguments to improve the chosen 'a' (which is D^2 in your notation) multipliers like 720, 5040 work best.
Til and me apply some modifications to the after choosing the 'a'. We increase until there is a solution to a^2 - 4kn = b^2 mod 2^k. This generalized mod 2^k arguments improve the behavior of odd multipliers. Lehman also gives a special case of our generalization.
In our (Til and me) unpublished versions 315 (odd!) was the best multiplier. The approach in a was only faster below 40 Bits.

e) Due to the observations above, it seems like there is no gain in choosing special (smooth, ???) multipliers for numbers above 40 bits. But maybe my learning was to short, or it does not discover the real structure of the multipliers. A running algorithm to prove that choosing a special order of multipliers would be nice.

ThiloHarich · 2019-04-05, 18:36

Correcting
b)
There are only c*n^1/3 multipliers. c=1 for Lehman. c pretty low for Hart.

What I mean is we can find the good multipliers and just store them in an array. - > no complicated multiplication needed. And they are proven to be working good.

nesio · 2019-04-06, 23:42

Hi, Thilo!
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?

ThiloHarich · 2019-04-07, 11:20

Hmm.

why should my model be very rough?

I have trained it with 30 million Factorizations on hard numbers (no factor below n^1/3). For different fixed multipliers m and collection good k = k' * m.
We have only 10.000 = 2^13,33 = 2^(40/3) multipliers 'k' for n below 40 bits. So I think the model is well trained. Increasing the training does not improve the results.

Surprisingly I get best results for the fixed multiplier m = 45.
I do not get the same speed for m=1 or other multiplier below.

So my conclusion is:
It still looks like when factoring one number it is better to go with one fixed multiplier (for us 315), then to go with good multipliers working for other numbers.

Quote:

maximum(S/(m^1/3)) and m < n^1/3,

m < n^1/3 is clear , but i did not get the first limit. And limit on what?

I understand that constructing 'k' as a product of small numbers sounds promising, since it covers many u*v of u/v ~ q/p. But my tries in using this fail. I tired:
- increase multiple different m in parallel
- construct smooth numbers
- use good 'k' from other factorizations.

nesio · 2019-04-07, 12:46

Quote:

Originally Posted by ThiloHarich

Hmm.

why should my model be very rough?
.

I have suggested you to test new rough model on your data that I wrote about.

ThiloHarich · 2019-04-07, 15:22

You can create the list of good multipliers "k" on your own easily and check if the numbers fit to your model. I can also send you a txt file with all the k in proper order if you want to.

I try to understand you model:

The sum of divisors of m is maximal if m is prime. So you expect prime numbers to be good "k"?
Or did you mean the number of divisors? Or number of different divisors?

Here are the multipliers "k" (in order) with leads to factorizations without extra multiplier m:

1155,105,165,330,210,255,285,273,15,390,21,345,561,495,195,231,435,462,315,385,33,510,420,30,715

Smooth numbers with exponent 1 are more likely yes. But I'm not able to predict the not so likely numbers.

2019-04-04, 15:03	#26
Till "Tilman Neumann" Jan 2016 Germany 110110010₂ Posts	On 2. It seems that you do not understand. If 10080 is the best multiplier for all n, then your "flexible" approach can not be better. On 6. We know the papers. I was asking for the magic recommendations you think we are missing. Last fiddled with by Till on 2019-04-04 at 15:04 Reason: use original numbering

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Diamond multiplication and factorization method	datblubat	Computer Science & Computational Number Theory	6	2018-12-25 17:29
The natural progression of (even perfect numbers)*3	Dubslow	Aliquot Sequences	6	2018-05-15 15:59
Montgomery method in Prime Numbers: ACP	SPWorley	Math	5	2009-08-18 17:27
Elliptic Curve Method factoring - Fermat numbers	philmoore	Math	131	2006-12-18 06:27
Prime Numbers: Nothing but Errors in Multiplication???	Pax_Vitae	Miscellaneous Math	15	2005-11-14 12:41

2019-04-04, 14:26	#24
Till "Tilman Neumann" Jan 2016 Germany 2·7·31 Posts	nesio, in fact we believe that Hart_Fast and Lehman_CustomKOrder are pretty fast. If you have something better then just show it. Your SM pseudocode will hardly be it. The minimal improvement in iterations of RM is not impressive either. Some comments on your points: 1. We do that in our implementations but did not in Hard_Nesio, because it is not in the SM pseudocode. 2. I demonstrated with my performance test that this is not helpful. 10080 seems to be the best multiplier for any n if you store the sqrt's. 3. We did understand that. 4. What do you mean with "fast multiplication", replace it with iterated addition? This makes hardly a difference in Java. Maybe the compiler is doing that for us. 5. That might be interesting. 6. Which one's?

2019-04-05, 13:57	#28
ThiloHarich Nov 2005 101₁₀ Posts	a) I have also done some investigations in optimal multipliers. One way was just to factor many, many numbers and to record the multipliers which lead to a factorization. It turned out that some multipliers had a much higher chance to factor a number then others. Then after learning, when finding factors we iterate over the good multipliers (biggest number of factorizations) first. For moderate inputs (i.e. 'n' below 40 bits) using the list of good multipliers gives a reasonable speedup (~10%). The list of good multipliers has some kind structure for lower multipliers (lets say < 8000). But above a certain limit this structure seems to be gone. b) There are only c*k^1/3 multipliers. So we can easily create them before factoring numbers n < 2 ^ 54 and store them in an array off size 1.000.00 . This is what i have done in a). For numbers above 2^52 The Brent Pollard Rho algorithm is faster anyway. c) An other way to avoid the cost of multiplying the k_i is to use a gray code style iterative iteration over the multipliers. Here in each iteration only one multiplier will be exchanged. d) Above n > 40 Bits choosing a fixed multiplier still works best. Without applying some mod 2^k arguments to improve the chosen 'a' (which is D^2 in your notation) multipliers like 720, 5040 work best. Til and me apply some modifications to the after choosing the 'a'. We increase until there is a solution to a^2 - 4kn = b^2 mod 2^k. This generalized mod 2^k arguments improve the behavior of odd multipliers. Lehman also gives a special case of our generalization. In our (Til and me) unpublished versions 315 (odd!) was the best multiplier. The approach in a was only faster below 40 Bits. e) Due to the observations above, it seems like there is no gain in choosing special (smooth, ???) multipliers for numbers above 40 bits. But maybe my learning was to short, or it does not discover the real structure of the multipliers. A running algorithm to prove that choosing a special order of multipliers would be nice.

2019-04-05, 18:36	#29
ThiloHarich Nov 2005 101 Posts	Correcting b) There are only c*n^1/3 multipliers. c=1 for Lehman. c pretty low for Hart. What I mean is we can find the good multipliers and just store them in an array. - > no complicated multiplication needed. And they are proven to be working good.

2019-04-06, 23:42	#30
nesio Apr 2019 2⁵ Posts	Hi, Thilo! 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?

2019-04-07, 15:22	#33
ThiloHarich Nov 2005 65₁₆ Posts	You can create the list of good multipliers "k" on your own easily and check if the numbers fit to your model. I can also send you a txt file with all the k in proper order if you want to. I try to understand you model: The sum of divisors of m is maximal if m is prime. So you expect prime numbers to be good "k"? Or did you mean the number of divisors? Or number of different divisors? Here are the multipliers "k" (in order) with leads to factorizations without extra multiplier m: 1155,105,165,330,210,255,285,273,15,390,21,345,561,495,195,231,435,462,315,385,33,510,420,30,715 Smooth numbers with exponent 1 are more likely yes. But I'm not able to predict the not so likely numbers.