20190401, 16:59  #1 
Apr 2019
2^{5} Posts 
Multiplication method for factoring natural numbers
Hi! If someone is interested in the subject and knows the Russian language then you can see a new publication here: https://arxiv.org/ftp/arxiv/papers/1903/1903.12449.pdf
It's abstract (https://arxiv.org/abs/1903.12449): We offer multiplication method for factoring big natural numbers which extends the group of the Fermat's and Lehman's factorization algorithms and has runtime complexity O(n^1/3). This paper is argued the finiteness of proposed algorithm depending on the value of the factorizable number n. We provide here comparative tests results of related algorithms on a large amount of computational checks. We describe identified advantages of the proposed algorithm over others. The possibilities of algorithm optimization for reducing the complexity of factorization are also shown here. Regards 
20190401, 18:25  #2 
Apr 2019
2^{5} Posts 
Sorry. Its annotation is here: https://arxiv.org/abs/1903.12449

20190402, 08:06  #3 
Mar 2018
201_{8} Posts 
Interesting. Didn't read it thoroughly, just skimmed it for now. Not sure if phrasing "big natural numbers" is warranted – the included tests are just up to 16 decimal digits. But anyway...
Last fiddled with by DukeBG on 20190402 at 08:07 
20190402, 12:08  #4 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT)
5675_{10} Posts 
Translating from Russian is a bit of an issue for most here.
Am I correct in understanding that you believe you have found an improvement to Lehman's method that should find more factors and runs in slightly less time(basically the same)? 
20190402, 13:29  #5  
Apr 2019
2^{5} Posts 
Quote:
Hart showed an improvement in Fermat's algorithm. His way is heuristic. We also have tried to improve Fermat's algorithm. Our way seems mathematically formal to us. According to the test results for the selected comparison metric, the MMFFNNRM algorithm is faster than Lehman more than twice and partly faster than the MMFFNNSM algorithm (alaHart). Also, the MMFFNNRM algorithm reveals some theoretical limitations of the MMFFNNSM algorithm, which is useful to know when you'll use the latter. 

20190402, 15:11  #6 
Feb 2017
Nowhere
CC2_{16} Posts 
The algorithms are given in English; but, maddeningly (at least to me), they aren't in ordinary text...

20190402, 15:55  #7  
Mar 2018
3×43 Posts 
Quote:
https://funkyimg.com/i/2SRxA.png Quote:
Last fiddled with by DukeBG on 20190402 at 16:00 

20190402, 18:57  #8 
Apr 2019
2^{5} Posts 

20190402, 19:53  #9  
"Tilman Neumann"
Jan 2016
Germany
390_{10} Posts 
Quote:
this looks quite interesting. I have a question concerning the "simple multiplication" algorithm: Could you explain in english how 'm' is determined? I found that m=5040 works ok but is there something better than choosing a constant? Last fiddled with by Till on 20190402 at 19:55 Reason: specify which algorithm is meant 

20190402, 21:13  #10 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
1110000110_{2} Posts 
The SM method looks to be Hart's OLF (as alluded to in the text) using a multiplier. Translating the "Simple Multiplication algorithm" from pseudocode into C becomes exactly my existing code for HOLF. The recursive SM is where things look interesting for larger values.
For multipliers 5040, 720, and 480 work pretty well as constants but the issue often becomes what fits without overflow. Table 1 shows SM (e.g. Hart's OLF) beating Lehman in the chosen measure. There is some debate on what is faster in practice, and the recent improved Lehman would be very competitive. 
20190402, 22:26  #11  
Apr 2019
20_{16} Posts 
Quote:
In MMFFNN method (both in SM and RM) sought factor “k” most often has a number of prime divisors. So multiplier “m” sets some initial value of “k”. Besides “m > 1” is helpful for special hardfactoring numbers of MMFFNN method (see the examples of such numbers for RM algorithm in the article). In common case “m” is nonlinear from r (r is a decimal digits size of factoring number “n”). But there is an optimum of “m” as a compromise between negative (cost of multiplication and growth of N =m*n*k) and positive (growth of the number of prime divisors of “m”) factors. If apply equal (balanced) value “m” to SM and RM algorithms as m_sm = 4 * m_rm there is a critical number of decimal digits r* when the complexity q(r) of SM will be always some greater than of RM: r* = [6 * log10 (m_rm)], where the square brackets indicate of rounding up. 

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 