Hidden numerical sieve with adjustable sieving ability within Fermat's factorization method

[R.D. Silverman]

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.

[nesio]

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?

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.

[Dr Sardonicus]

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.

Sometimes people do stupid things. As danaj related in this post:

How about:

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

[R.D. Silverman]

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.

[Dr Sardonicus]

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

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)

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

[R.D. Silverman]

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

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)

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

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.

[retina]

Originally Posted by R.D. Silverman

... like trying to improve a square wheel.

I like this analogy. Concise and to the point.

[Dr Sardonicus]

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.

If you reread danaj's post linked to above, you'll see that

(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?

[retina]

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.

[a1call]

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.

[CRGreathouse]

Originally Posted by R.D. Silverman

Other methods are faster.

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?