

Thread Tools 
20191024, 16:07  #1 
Apr 2019
2^{5} Posts 
Hidden numerical sieve with adjustable sieving ability within Fermat's factorization method
Hi! If someone is interested in the subject and knows the Russian language then you can see a new publication here: https://www.linkedin.com/posts/igor...847498754yGwA
ABSTRACT This paper proposes an algorithm for applying a hidden numerical sieve with an adjustable sieving ability in the Fermat’s factorization method. The sieve allows you to repeatedly – 2^α times – reduce the complexity of factorization, calculated by the metric described in the work, where the parameter α = {1,2,3, ...} is a regulator that determines the structure of the sieve and its sieving ability. The paper gives an exact rationale and a formal description of the algorithm, presents computational experiments confirming the effectiveness of this sieve. 
20191125, 10:00  #2 
Apr 2019
2^{5} Posts 
If it will be convenient for someone, then this article can be viewed here:
https://www.researchgate.net/publica...orizacii_Ferma 
20191125, 13:51  #3  
Nov 2003
2^{2}×5×373 Posts 
Quote:


20191125, 17:31  #4 
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
11^{2}·79 Posts 

20191125, 17:49  #5 
Nov 2003
16444_{8} Posts 
It should be obvious. Trying to improve Fermat's method is like trying to
improve a square wheel. The method is totally obsolete. To factor N it is O(N^(1/2)). Lehman's improved variation of Fermat's method is already O(N^(1/3)). ECM, QS, squfof are faster yet in both theory and practice. Trying to factoring anything beyond 2025 digits is hopeless. Despite this, people here in this forum and externally are repeatedly prattling about proposed "improvements". Trying to improve an O(N^(1/2)) method is pointless when there are existing methods that are faster. 
20191125, 19:15  #6 
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
11^{2}·79 Posts 

20191126, 11:28  #7  
Apr 2019
2^{5} Posts 
Running time of Fermat's method is O(N).
Quote:
Quote:
Quote:


20191126, 13:31  #8  
Nov 2003
2^{2}×5×373 Posts 
Wrong. If N = pq it is (p+q)/2  sqrt(N).
Quote:
Quote:
Quote:


20191127, 11:07  #9 
Apr 2019
2^{5} Posts 
Posted by R.D. Silverman: To factor N it is O(N^(1/2)).
Posted by nesio: Running time of Fermat's method is O(N). Posted by R.D. Silverman: Wrong. If N = pq it is (p+q)/2  sqrt(N). =================================================================== nesio: Let p > 1 then q > N, hence p + q > N or (p+q)/2 > N/2, and now it takes O(N) steps. 
20191127, 15:44  #10  
Nov 2003
2^{2}×5×373 Posts 
Quote:
"Fermat's method is good to fast test whether factors x and y are near at sqrt(N)." One always rules out small factors by trial division first. One only runs Fermat when it is known that no small factors exist, e.g. to split cofactors that arise in QS or NFS. However, even used in this setting other methods are faster. If p = 1, then Fermat's method becomes a totally hopeless primality test. 

20191127, 16:38  #11 
Sep 2009
2^{3}×3×5×17 Posts 
Would it be useful if you know the factors are *very* close to sqrt(N)? Eg a RSA key generated by a doctored rsakeygen that ensures the factors are close enough to find that way if you know what to check for?
Chris 
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 
improving factorization method  bhelmes  Computer Science & Computational Number Theory  7  20170626 02:20 
New factorization method  henryzz  Miscellaneous Math  4  20170413 12:41 
Fast factorization method or crankery?  10metreh  Factoring  6  20100408 11:51 
Modification of Fermat's method  rdotson  Miscellaneous Math  0  20070727 10:32 