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

2019-11-27, 16:48   #12
R.D. Silverman

Nov 2003

1D2416 Posts

Quote:
 Originally Posted by chris2be8 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
Please tell. How does one know this? Someone would have to tell you that they
deliberately constructed the composite in such a manner.

2019-11-29, 00:32   #13
nesio

Apr 2019

25 Posts

Quote:
 Originally Posted by chris2be8 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?
Quote:
 Originally Posted by R.D. Silverman Please tell. How does one know this? Someone would have to tell you that they deliberately constructed the composite in such a manner.
For instance one can find some examples of cases regarding Fermat, factorization, analysis, improvement and so on here:

http://www.enseignement.polytechniqu...ts/Weger02.pdf
https://blog.trailofbits.com/2019/07/08/fuck-rsa/
https://www.researchgate.net/publica...ring_Algorithm
... ... ...

BTW. It is so happened that you can come to R.D. Silverman from the inside of the first link - where the talk is right about Fermat.
P.S. Since I'm not the author of the information in the links, I can not answer for them.

2019-11-29, 14:35   #14
Dr Sardonicus

Feb 2017
Nowhere

576610 Posts

Quote:
Originally Posted by R.D. Silverman
Quote:
 Originally Posted by chris2be8 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
Please tell. How does one know this? Someone would have to tell you that they
deliberately constructed the composite in such a manner.
Sometimes people do stupid things. As danaj related in this post:
Quote:
 How about: Code: 185486767418172501041516225455805768237366368964328490571098416064672288855543059138404131637447372942151236559829709849969346650897776687202384767704706338162219624578777915220190863619885201763980069247978050169295918863 which was not a number I created, but was supplied by someone as what they considered to be a hard to factor number. It's the product of two large "random" primes, after all. Turns out it's ridiculously easy for Hart's OLF, which is a Fermat variant. Of course this is not going to be the case for properly formed keys, but there are reasons not to be quite so dismissive of their having a place in the toolbox. I do agree that once we've gotten past some special inputs and out of the 64-bit range (which for this forum would be considered tiny numbers), Fermat, HOLF, Lehman, SQUFOF, etc. have little use other than optimizing factoring tiny inputs (e.g. small co-factors or to support other algorithms that need factoring of these tiny sizes).

2019-11-29, 14:49   #15
R.D. Silverman

Nov 2003

11101001001002 Posts

Quote:
 Originally Posted by Dr Sardonicus Sometimes people do stupid things. As danaj related in this post: I do agree that once we've gotten past some special inputs and out of the 64-bit range (which for this forum would be considered tiny numbers), Fermat, HOLF, Lehman, SQUFOF, etc. have little use other than optimizing factoring tiny inputs (e.g. small co-factors or to support other algorithms that need factoring of these tiny sizes).
Even then, ECM and a 'tiny' SIQS are faster.

2019-11-29, 16:52   #16
Dr Sardonicus

Feb 2017
Nowhere

2×3×312 Posts

Quote:
 Originally Posted by R.D. Silverman Even then, ECM and a 'tiny' SIQS are faster.
I assume you mean ECM and SIQS are faster for tiny inputs or inputs with small factors. That leaves people doing stupid things.

For the numerical example that danaj gave (222 decimal digits), quoted above, even on my sluggish system the Pari-GP user-defined function

Code:
OLF(x)={i=1;while(i<x,if(issquare(ceil(sqrt(i*x))^2%x),return(gcd(x,floor(ceil(sqrt(i*x))-sqrt((ceil(sqrt(i*x))^2)%x)))));i++)}
found the smaller factor (111 decimal digits)

Code:
192606732705880508138303165129171270891951231683030125996296974238495711578947569589234612013165893468683239489
in "0 ms" which I interpret as less than half a millisecond. I leave it as an exercise for the reader to refine this estimate.

(If realprecision isn't high enough for OLF() to work, Pari-GP will issue an error message. Adjust as necessary.)

2019-11-29, 19:29   #17
R.D. Silverman

Nov 2003

746010 Posts

Quote:
 Originally Posted by Dr Sardonicus I assume you mean ECM and SIQS are faster for tiny inputs or inputs with small factors. That leaves people doing stupid things. For the numerical example that danaj gave (222 decimal digits), quoted above, even on my sluggish system the Pari-GP user-defined function Code: `OLF(x)={i=1;while(i
So? A number was specially constructed to be susceptible. Big whoopee.

If such a number has been constructed we don't need improvements to the
algorithm.

2019-11-30, 04:24   #18
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

24×13×31 Posts

Quote:
 Originally Posted by R.D. Silverman ... like trying to improve a square wheel.
I like this analogy. Concise and to the point.

2019-11-30, 14:23   #19
Dr Sardonicus

Feb 2017
Nowhere

2×3×312 Posts

Quote:
 Originally Posted by R.D. Silverman So? A number was specially constructed to be susceptible. Big whoopee. If such a number has been constructed we don't need improvements to the algorithm.

(1) the number was constructed by another person who thought it would be hard to factor, and

(2) danaj was merely arguing that one shouldn't dismiss having the method from one's toolkit.

And that's all I'm saying. No argument that Fermat's method is useless as a general factoring method. No argument about improving a useless method being a waste of time.

Just out of curiosity, though: What general method would factor the example C222 in a reasonable length of time?

2019-11-30, 14:41   #20
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

24×13×31 Posts

Quote:
 Originally Posted by Dr Sardonicus No argument about improving a useless method being a waste of time.
I don't like this conclusion. Sometimes improving a square wheel with some new and novel device can also be applied to other systems that are less useless.

M: Hey look, we improved method A with device X. Yay us, we are the greatest.
N: Yeah, okay. But method A is pointless and useless, so you are wasting your time. Methods B, C and D already outperform A.
M: Oh, yeah, you are correct. ... But, wow look, device X can also be applied to method C.
N: OMG, that is so cool. No one else saw that previously. You guys are the greatest.

Ya never know. It could happen.

 2019-11-30, 15:07 #21 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 43028 Posts Which one would track better in snow? A round or square wheel? Which one would be an improvement over square-wheels for an on-snow-driven vehicle? Round or triangular wheels? For the literally detailed version, let's assume that the vehicle is equipped with adjustable-elevation-maintenance skis on the side, to avoid digging in the snow. Last fiddled with by a1call on 2019-11-30 at 15:34
2019-12-01, 03:59   #22
CRGreathouse

Aug 2006

3×1,993 Posts

Quote:
Originally Posted by R.D. Silverman
Quote:
 Originally Posted by nesio Fermat's method is good to fast test whether factors x and y are near at sqrt(N).
Other methods are faster.
Quote:
 Originally Posted by nesio Just out of curiosity, though: What general method would factor the example C222 in a reasonable length of time?
I'm curious here too: suppose I'm interested in testing numbers believed to have factors near their square roots (but inaccessible to trial factorization/ECM), what improvements are available over Fermat? I know OLF can be used but can I do better?

 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:37.

Wed May 18 07:37:51 UTC 2022 up 34 days, 5:39, 0 users, load averages: 1.69, 1.31, 1.22