mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2019-04-01, 16:59   #1
nesio
 
Apr 2019

25 Posts
Default 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 run-time 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
nesio is offline   Reply With Quote
Old 2019-04-01, 18:25   #2
nesio
 
Apr 2019

25 Posts
Default

Sorry. Its annotation is here: https://arxiv.org/abs/1903.12449
nesio is offline   Reply With Quote
Old 2019-04-02, 08:06   #3
DukeBG
 
Mar 2018

2018 Posts
Default

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 2019-04-02 at 08:07
DukeBG is offline   Reply With Quote
Old 2019-04-02, 12:08   #4
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

567510 Posts
Default

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)?
henryzz is online now   Reply With Quote
Old 2019-04-02, 13:29   #5
nesio
 
Apr 2019

25 Posts
Default

Quote:
Originally Posted by DukeBG View Post
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...
Lehman improved Fermat's algorithm. His way is mathematically formal.
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 MMFFNN-RM algorithm is faster than Lehman more than twice and partly faster than the MMFFNN-SM algorithm (a-la-Hart).
Also, the MMFFNN-RM algorithm reveals some theoretical limitations of the MMFFNN-SM algorithm, which is useful to know when you'll use the latter.
nesio is offline   Reply With Quote
Old 2019-04-02, 15:11   #6
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

CC216 Posts
Default

The algorithms are given in English; but, maddeningly (at least to me), they aren't in ordinary text...
Dr Sardonicus is offline   Reply With Quote
Old 2019-04-02, 15:55   #7
DukeBG
 
Mar 2018

3×43 Posts
Default

Quote:
Originally Posted by henryzz View Post
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)?
The relevant part of the paper to answer your question is this table. r is the decimal digit size. The numbers are the average (over 20000 tests of composite numbers) of total square root attempts when factoring an r-size number. Used as a metric for work amount.
https://funkyimg.com/i/2SRxA.png

Quote:
The algorithms are given in English; but, maddeningly (at least to me), they aren't in ordinary text...
They're given in pseudo-code and relevant parts described "in language" in Russian. Giving that in English I think should be by just translating the whole paper into English properly...

Last fiddled with by DukeBG on 2019-04-02 at 16:00
DukeBG is offline   Reply With Quote
Old 2019-04-02, 18:57   #8
nesio
 
Apr 2019

25 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
The algorithms are given in English; but, maddeningly (at least to me), they aren't in ordinary text...
If you have any general or specific questions about the pseudo-code of algorithms, please send to us. We will try to answer them.
nesio is offline   Reply With Quote
Old 2019-04-02, 19:53   #9
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

39010 Posts
Default

Quote:
Originally Posted by nesio View Post
If you have any general or specific questions about the pseudo-code of algorithms, please send to us. We will try to answer them.
Hi Nesio,
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 2019-04-02 at 19:55 Reason: specify which algorithm is meant
Till is offline   Reply With Quote
Old 2019-04-02, 21:13   #10
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

11100001102 Posts
Default

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.
danaj is offline   Reply With Quote
Old 2019-04-02, 22:26   #11
nesio
 
Apr 2019

2016 Posts
Default

Quote:
Originally Posted by Till View Post
Hi Nesio,
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?
Till!
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 hard-factoring numbers of MMFFNN method (see the examples of such numbers for RM algorithm in the article).
In common case “m” is non-linear 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.
nesio 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 08:31.

Sun Jul 5 08:31:02 UTC 2020 up 102 days, 6:04, 1 user, load averages: 1.37, 1.27, 1.20

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.