mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2019-10-24, 16:07   #1
nesio
 
Apr 2019

25 Posts
Default 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.
nesio is offline   Reply With Quote
Old 2019-11-25, 10:00   #2
nesio
 
Apr 2019

25 Posts
Default

If it will be convenient for someone, then this article can be viewed here:
https://www.researchgate.net/publica...orizacii_Ferma
nesio is offline   Reply With Quote
Old 2019-11-25, 13:51   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by nesio View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2019-11-25, 17:31   #4
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

112·79 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Pointless.
Because?
Uncwilly is offline   Reply With Quote
Old 2019-11-25, 17:49   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by Uncwilly View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2019-11-25, 19:15   #6
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

112·79 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
Uncwilly is offline   Reply With Quote
Old 2019-11-26, 11:28   #7
nesio
 
Apr 2019

25 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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 ;-)
nesio is offline   Reply With Quote
Old 2019-11-26, 13:31   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by nesio View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2019-11-27, 11:07   #9
nesio
 
Apr 2019

25 Posts
Default

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.
nesio is offline   Reply With Quote
Old 2019-11-27, 15:44   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by nesio View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2019-11-27, 16:38   #11
chris2be8
 
chris2be8's Avatar
 
Sep 2009

23×3×5×17 Posts
Default

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
chris2be8 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
improving factorization method bhelmes Computer Science & Computational Number Theory 7 2017-06-26 02:20
New factorization method henryzz Miscellaneous Math 4 2017-04-13 12:41
Fast factorization method or crankery? 10metreh Factoring 6 2010-04-08 11:51
Modification of Fermat's method 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

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