mersenneforum.org  

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

Reply
 
Thread Tools
Old 2019-11-27, 16:48   #12
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2019-11-29, 00:32   #13
nesio
 
Apr 2019

25 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
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 View Post
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.
nesio is offline   Reply With Quote
Old 2019-11-29, 14:35   #14
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

576610 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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).
Dr Sardonicus is offline   Reply With Quote
Old 2019-11-29, 14:49   #15
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2019-11-29, 16:52   #16
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×3×312 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.)
Dr Sardonicus is offline   Reply With Quote
Old 2019-11-29, 19:29   #17
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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.)
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.
R.D. Silverman is offline   Reply With Quote
Old 2019-11-30, 04:24   #18
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

24×13×31 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
... like trying to improve a square wheel.
I like this analogy. Concise and to the point.
retina is online now   Reply With Quote
Old 2019-11-30, 14:23   #19
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×3×312 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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?
Dr Sardonicus is offline   Reply With Quote
Old 2019-11-30, 14:41   #20
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

24×13×31 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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.
retina is online now   Reply With Quote
Old 2019-11-30, 15:07   #21
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

43028 Posts
Default

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
a1call is offline   Reply With Quote
Old 2019-12-01, 03:59   #22
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Quote:
Originally Posted by nesio View Post
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 View Post
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?
CRGreathouse 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:37.


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

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

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔