mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2019-04-04, 14:21   #23
nesio
 
Apr 2019

1000002 Posts
Default

Quote:
Originally Posted by DukeBG View Post
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.
nesio is offline   Reply With Quote
Old 2019-04-04, 14:26   #24
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

1B216 Posts
Default

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?
Till is offline   Reply With Quote
Old 2019-04-04, 14:52   #25
nesio
 
Apr 2019

25 Posts
Default

Quote:
Originally Posted by Till View Post
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.
nesio is offline   Reply With Quote
Old 2019-04-04, 15:03   #26
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

2×7×31 Posts
Default

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
Till is offline   Reply With Quote
Old 2019-04-04, 19:18   #27
nesio
 
Apr 2019

25 Posts
Default

Quote:
Originally Posted by Till View Post
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.
nesio is offline   Reply With Quote
Old 2019-04-05, 13:57   #28
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

101 Posts
Default

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 is offline   Reply With Quote
Old 2019-04-05, 18:36   #29
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

101 Posts
Default

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.
ThiloHarich is offline   Reply With Quote
Old 2019-04-06, 23:42   #30
nesio
 
Apr 2019

25 Posts
Default

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?
nesio is offline   Reply With Quote
Old 2019-04-07, 11:20   #31
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

101 Posts
Default

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.

Last fiddled with by ThiloHarich on 2019-04-07 at 11:20
ThiloHarich is offline   Reply With Quote
Old 2019-04-07, 12:46   #32
nesio
 
Apr 2019

25 Posts
Default

Quote:
Originally Posted by ThiloHarich View Post
Hmm.

why should my model be very rough?
.
I have suggested you to test new rough model on your data that I wrote about.
nesio is offline   Reply With Quote
Old 2019-04-07, 15:22   #33
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

6516 Posts
Default

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.
ThiloHarich is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 14:36.

Tue Apr 13 14:36:43 UTC 2021 up 5 days, 9:17, 1 user, load averages: 2.34, 2.88, 2.85

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.