20190404, 14:21  #23 
Apr 2019
40_{8} Posts 

20190404, 14:26  #24 
"Tilman Neumann"
Jan 2016
Germany
443 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? 
20190404, 14:52  #25  
Apr 2019
2^{5} Posts 
Quote:
Quote:
Quote:
[1] R. Lehman, ‘Factoring Large Integers’. Mathematics of Computation, Volume 28, Number 126, April 1974, Pages 637646. [2] Hart, William B. ‘A one line factoring algorithm’, 2012. Journal of the Australian Mathematical Society, Volume 92 (Number 1), Pages 6169. 

20190404, 15:03  #26 
"Tilman Neumann"
Jan 2016
Germany
443 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 20190404 at 15:04 Reason: use original numbering 
20190404, 19:18  #27 
Apr 2019
2^{5} Posts 
We think that we understand "multiplication method" a little )) But maybe you know better how to choose a multiplier m for your program.

20190405, 13:57  #28 
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. 
20190405, 18:36  #29 
Nov 2005
145_{8} 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. 
20190406, 23:42  #30 
Apr 2019
2^{5} 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? 
20190407, 11:20  #31  
Nov 2005
101 Posts 
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:
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 20190407 at 11:20 

20190407, 12:46  #32 
Apr 2019
100000_{2} Posts 

20190407, 15:22  #33 
Nov 2005
65_{16} 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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Diamond multiplication and factorization method  datblubat  Computer Science & Computational Number Theory  6  20181225 17:29 
The natural progression of (even perfect numbers)*3  Dubslow  Aliquot Sequences  6  20180515 15:59 
Montgomery method in Prime Numbers: ACP  SPWorley  Math  5  20090818 17:27 
Elliptic Curve Method factoring  Fermat numbers  philmoore  Math  131  20061218 06:27 
Prime Numbers: Nothing but Errors in Multiplication???  Pax_Vitae  Miscellaneous Math  15  20051114 12:41 