20210217, 18:20  #12 
"Ben"
Feb 2007
2^{2}×853 Posts 
Yes, much smaller numbers would have a larger probability of being smooth. But so far we have not seen this from you, only ratios of 10^1 to 10^3 that are trivial to generate. So, show us a bunch of ratios of 10^20, or those lists of x^2 mod p~10^6 for RSA260,270.

20210217, 18:24  #13  
Apr 2020
241 Posts 
Quote:
Quote:
In practice, looking for the smallest possible values of x^2 mod N is not the most efficient way to proceed: it's about 10^5 times harder (I think!) to find such values around 10^5*sqrt(N) than it is around sqrt(N), and they aren't 10^5 times more likely to be smooth, so there's no point in searching them out specifically. The best known factoring algorithm of this type is QS, which finds lots of values of x^2 mod N around sqrt(N) (or a little larger) in such a way that they can easily be sieved, allowing the smooth residues to be found quickly. Last fiddled with by charybdis on 20210217 at 18:25 

20210217, 19:14  #14  
"Ben"
Feb 2007
D54_{16} Posts 
Quote:
Code:
sqrtN = 8566463691637185710323259019755230896737522212231811895870570 found 80732629 small Q's (91.65 percent) with Q >= 1 bits below sqrtN found 3701469 small Q's (4.20 percent) with Q >= 2 bits below sqrtN found 1846974 small Q's (2.10 percent) with Q >= 3 bits below sqrtN found 908506 small Q's (1.03 percent) with Q >= 4 bits below sqrtN found 450578 small Q's (0.51 percent) with Q >= 5 bits below sqrtN found 223450 small Q's (0.25 percent) with Q >= 6 bits below sqrtN found 111367 small Q's (0.13 percent) with Q >= 7 bits below sqrtN found 56011 small Q's (0.06 percent) with Q >= 8 bits below sqrtN found 27932 small Q's (0.03 percent) with Q >= 9 bits below sqrtN found 13859 small Q's (0.02 percent) with Q >= 10 bits below sqrtN found 7074 small Q's (0.01 percent) with Q >= 11 bits below sqrtN found 3436 small Q's (0.00 percent) with Q >= 12 bits below sqrtN found 1792 small Q's (0.00 percent) with Q >= 13 bits below sqrtN found 861 small Q's (0.00 percent) with Q >= 14 bits below sqrtN found 402 small Q's (0.00 percent) with Q >= 15 bits below sqrtN found 214 small Q's (0.00 percent) with Q >= 16 bits below sqrtN found 102 small Q's (0.00 percent) with Q >= 17 bits below sqrtN found 56 small Q's (0.00 percent) with Q >= 18 bits below sqrtN found 20 small Q's (0.00 percent) with Q >= 19 bits below sqrtN found 16 small Q's (0.00 percent) with Q >= 20 bits below sqrtN found 11 small Q's (0.00 percent) with Q >= 21 bits below sqrtN found 5 small Q's (0.00 percent) with Q >= 22 bits below sqrtN found 4 small Q's (0.00 percent) with Q >= 23 bits below sqrtN found 0 small Q's (0.00 percent) with Q >= 24 bits below sqrtN The data set only takes a few seconds to run, so it is pretty easy to find Q's a factor 1000 smaller. But as you said, these are far from 1000x more likely to be smooth. Last fiddled with by bsquared on 20210217 at 19:26 Reason: updated data set 

20210217, 19:52  #15 
"Roman V. Makarchuk"
Aug 2020
Ukraine
40_{10} Posts 
Whatever, I finding the sub sqrt values by iterations, and at least on the paper, there no difference between N^(1/2) or N^(1/3) or N^(1/4) or N^(1/u)=x^2 mod N. In real life, u=2 have solid convergence.u= 3,4 work nasty(mostly, do not work), time to time, and strongly depend on the initial guess values

20210217, 21:38  #16 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{3}·5^{2}·47 Posts 
This thread is still not in Misc.Math?

20210218, 16:36  #17  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
6128_{10} Posts 
Quote:
Do you have no example for us? Does that mean you can't actually end RSA? You could start with a really easy 20 digit number of your own construction. I left it wide open for you. If you can do that then we could see how it scales for larger, more practically sized, inputs. 

20210218, 16:39  #18 
Feb 2017
Nowhere
1000110001001_{2} Posts 
Suppose N = P*Q, the product of two (large) primes. The existence of small quadratic residues r (mod N) (that is, x^{2} == r (mod N) is solvable) isn't hard to prove.
If p is a prime not dividing N, there are 4 possibilities for the quadratic character values ((p/P), (p/Q)), namely (+1, +1), (+1, 1), (1, +1), and (1, 1). If p_{1}, p_{2}, p_{3}, p_{4}, and p_{5} are the smallest five primes which do not divide N, at least two of them, say p_{i}, and p_{j}, have the same quadratic characters (mod P) and (mod Q), so that r = p_{i}*p_{j} is a quadratic residue (mod P) and (mod Q). Unfortunately, I don't see any easy way of figuring out which pair, or pairs, fill the bill. 
20210218, 23:27  #19 
"Daniel Jackson"
May 2011
14285714285714285714
2^{3}×3^{4} Posts 
@RMLabrador: Try factoring http://www.factordb.com/index.php?id...00002495591425 with your algorithm. I have the factors, but I won't submit them unless your algorithm is proven wrong/too slow.
Also, try 144122485282468744921 if the above is too hard. Last fiddled with by Stargate38 on 20210218 at 23:30 Reason: smaller example 
20210219, 01:00  #20  
"Robert Gerbicz"
Oct 2005
Hungary
2^{2}·5·73 Posts 
Quote:
Code:
N=2^4096+1; x=694785161528292923786070190544555127232240209017636661869870533750882763489045000867332467054810239781399921579969506436642297683669911703872080967388500816022277746167694857580457652166225682974530552047112203051070338401109908446260279847078970792145467049257338313237868081366759136762565251648862281714914995197952316755064524338400918179455572546482880077018987683158318505298442798783267438375857916262236433095094292316209710672835987139312183549242253415226918092785089300407580368162509986228628720758163796878263167474617853571423652021277601746521663261163233388784562738278204035477697005166148741791444671221013316389071199405955489346962764911029066060952806706468840007209003757098020635429100939439790001980019741636794934562528612894292850402306119554279977156597950763874443170242820415159604620459350895817305168757436309593792476838456236394332656462170141068969911112855268986127446289522931510124437002265723783571727844109653361571149379210536707047831786919502836080940586269636140465448963287720825372805929802060293541140251875634166289176827612801578044851329006633310819343967394026364504199674632920414220663751847157995328508699229052114436701607271539306507184406826769097643090735334545700591255234078; ((x^2)%N)/sqrt(N) %3 = 9.0460488930260020189274458788248289311 E50 x/N*1.0 %4 = 0.66525522618374281552550148589689295545 ? Where is my genious cheat? 

20210219, 01:31  #21 
Apr 2020
241 Posts 
Well yes, it does help that we already know 6 factors of F12

20210219, 01:53  #22 
Romulan Interpreter
Jun 2011
Thailand
2×3×5×313 Posts 
The small numbers not only have a higher probability to be smooth (like someone already pointed out), but they also have a higher probability to be squares (or powers, in general). If it is so easy to generate x^2 (mod p) to be as small as we want it, then make it to be two digits. There are 90 numbers below 100 which are not squares, so you only need to find 91 relations** to factor every N by difference of squares. No (quadratic) sieve needed, and no linear algebra. Piece of cake. Show us a factorization of RSA1024.
Edit: also, if making the values small is difficult, then please make the values be as close as possible to sqrt(N), in that case a method like Pollard rho will also find the factors reasonable fast.  **in fact you need much less, as they also contain cubes and other odd powers (2^3, 3^3, 2^5) and you can easily combine them to eliminate multiples of 2, 3, primes, etc., and also, not all the numbers under 100 are quadratic residues. This works like the birthday paradox, except the birthdays are taken from 100, not from 365. So, maybe around 10 relations will always be enough (probabilistic) to find two with the same birthday? (no calculation done, wild ass guess). Then apply difference of squares, to factor any number, of any size. Last fiddled with by LaurV on 20210227 at 04:42 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Riesel Primes k*2^n1, k<300 [Part II]  Kosmaj  Riesel Prime Search  1027  20210420 08:23 
I'm sure this is an ID10T error on my part  petrw1  PrimeNet  1  20170925 23:12 
Numbers in Tables : Part 2  wustvn  Puzzles  9  20071231 05:14 
Two PC's looking for parttime work  OmbooHankvald  Software  8  20050723 01:23 
Circles part 2  mfgoode  Puzzles  10  20041227 15:17 