mersenneforum.org Hidden numerical sieve with adjustable sieving ability within Fermat's factorization method
 Register FAQ Search Today's Posts Mark Forums Read

 2019-10-24, 16:07 #1 nesio   Apr 2019 25 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-...847498754-yGwA 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.
 2019-11-25, 10:00 #2 nesio   Apr 2019 25 Posts If it will be convenient for someone, then this article can be viewed here: https://www.researchgate.net/publica...orizacii_Ferma
2019-11-25, 13:51   #3
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by nesio 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-...847498754-yGwA 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.
Pointless.

2019-11-25, 17:31   #4
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

112·79 Posts

Quote:
 Originally Posted by R.D. Silverman Pointless.
Because?

2019-11-25, 17:49   #5
R.D. Silverman

Nov 2003

164448 Posts

Quote:
 Originally Posted by Uncwilly Because?
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 20-25 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.

2019-11-25, 19:15   #6
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

112·79 Posts

Quote:
 Originally Posted by R.D. Silverman Trying to improve an O(N^(1/2)) method is pointless when there are existing methods that are faster.
Thanks, the OP will benefit more from that than a one word response.

2019-11-26, 11:28   #7
nesio

Apr 2019

25 Posts

Quote:
 Originally Posted by R.D. Silverman To factor N it is O(N^(1/2))
Running time of Fermat's method is O(N).

Quote:
 The method is totally obsolete.
Fermat's method is good to fast test whether factors x and y are near at sqrt(N).

Quote:
 Lehman's improved variation of Fermat's method is already O(N^(1/3))
Here is another my and co-author paper where improved Fermat's method takes O(N^1/3) steps: https://www.researchgate.net/publica...atural_numbers

Quote:
 Despite this, people here in this forum and externally are repeatedly prattling about proposed "improvements".
People! If you have any workable improvements then publish it (here or outside) for the readers which will see additional paths in the forest of knowledge. It is quite normal ;-)

2019-11-26, 13:31   #8
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by nesio Running time of Fermat's method is O(N).
Wrong. If N = pq it is (p+q)/2 - sqrt(N).

Quote:
 Fermat's method is good to fast test whether factors x and y are near at sqrt(N).
Other methods are faster.

Quote:
 Here is another my and co-author paper where improved Fermat's method takes O(N^1/3) steps: https://www.researchgate.net/publica...atural_numbers
Lehman's method. Published back in the 80's.

Quote:
 People! If you have any workable improvements then publish it (here or outside) for the readers which will see additional paths in the forest of knowledge. It is quite normal ;-)
Improving a square wheel has very little utility.

 2019-11-27, 11:07 #9 nesio   Apr 2019 25 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.
2019-11-27, 15:44   #10
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by nesio 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.
Allow me to quote you:

"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.

 2019-11-27, 16:38 #11 chris2be8     Sep 2009 23×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 rsa-keygen that ensures the factors are close enough to find that way if you know what to check for? Chris

 Similar Threads Thread Thread Starter Forum Replies Last Post datblubat Computer Science & Computational Number Theory 6 2018-12-25 17:29 bhelmes Computer Science & Computational Number Theory 7 2017-06-26 02:20 henryzz Miscellaneous Math 4 2017-04-13 12:41 10metreh Factoring 6 2010-04-08 11:51 rdotson Miscellaneous Math 0 2007-07-27 10:32

All times are UTC. The time now is 07:32.

Sun May 9 07:32:35 UTC 2021 up 31 days, 2:13, 0 users, load averages: 3.31, 3.03, 2.81