 mersenneforum.org The end of RSA, Part 1
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read  2021-02-17, 18:20   #12
bsquared

"Ben"
Feb 2007

22·23·37 Posts Quote:
 Originally Posted by RMLabrador And, if number is small, the probability of beeing *smooth* much higher, isntly? If we can find x^2 mod p~10^6 for RSA-260,270 and so on, do You think, this is do not help us to find the factors?
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 RSA-260,270.   2021-02-17, 18:24   #13
charybdis

Apr 2020

3×7×11 Posts Quote:
 Originally Posted by RMLabrador Pari GP code \p10000 { p=2^8192+1; Srp=sqrt(p); for(m=1,1000, x=m*2^4096; B=lift(Mod(x^2,p)); localprec(5); print(B/Srp/1.); ); } (x^2 mod p)/Sqrt(p)~10^1233 I do something wrong here??? ... To Mr. charybdis. The Signum x^2 mod p/Sqrt(p) must be + (Positive))))))
Negative values are fine because we can include -1 in the factor base. In this case we get (m*2^4096)^2 = m^2*(2^8192+1) - m^2, so this reduces to -m^2.

Quote:
 And, if number is small, the probability of beeing *smooth* much higher, isntly? If we can find x^2 mod p~10^6 for RSA-260,270 and so on, do You think, this is do not help us to find the factors?
Indeed. But by "small", I meant "around the size of sqrt(N)"; as I alluded to above, even 10^-20*sqrt(N) is out of reach with current techniques as far as I know. For RSA-260, it'll be difficult to find many values of x^2 mod N that are below, say, 10^120.

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 2021-02-17 at 18:25   2021-02-17, 19:14   #14
bsquared

"Ben"
Feb 2007

22×23×37 Posts Quote:
 Originally Posted by charybdis 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)...
You are correct - I ran my QS poly generator in a loop and examined the smallest offsets near each root, gathering counts of values found that are smaller than sqrt(N). Here is example data for a 400 bit N (results are pretty consistent across a wide range of N sizes, dropping very slightly as N increases in size):

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
So at 17 bits (Q is a factor 131072 smaller than sqrt(N)) we find roughly 10^5 fewer cases.

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 2021-02-17 at 19:26 Reason: updated data set   2021-02-17, 19:52 #15 RMLabrador   "Roman V. Makarchuk" Aug 2020 Ukraine 23·5 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   2021-02-17, 21:38 #16 Batalov   "Serge" Mar 2008 Phi(4,2^7658614+1)/2 9,391 Posts This thread is still not in Misc.Math?    2021-02-18, 16:36   #17
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

23×32×5×17 Posts Quote:
 Originally Posted by retina To the OP. Please just show us the process used to factor an RSA number. As a starter I'll let you choose the number. But clearly show each step to arrive at p & q from n, without using knowledge of p & q as part of the process of course.
OP?

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.   2021-02-18, 16:39 #18 Dr Sardonicus   Feb 2017 Nowhere 22×1,117 Posts Suppose N = P*Q, the product of two (large) primes. The existence of small quadratic residues r (mod N) (that is, x2 == 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 p1, p2, p3, p4, and p5 are the smallest five primes which do not divide N, at least two of them, say pi, and pj, have the same quadratic characters (mod P) and (mod Q), so that r = pi*pj 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.   2021-02-18, 23:27 #19 Stargate38   "Daniel Jackson" May 2011 14285714285714285714 23×34 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 2021-02-18 at 23:30 Reason: smaller example   2021-02-19, 01:00   #20
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2·36 Posts Quote:
 Originally Posted by charybdis For p = 2^8192+1, yes: just set x = m*2^4096. But those trivial examples end up providing the trivial factorization. Here's a non-trivial example: Code: x = 803712330813026779984467996238884416214971565156928364938627476528725619263969815396609420647192767387047088537280168342583133370289681466664036601515256664532162868492066319219259007761040628727765538023351930944192148126167775008808304629533263425355385253143896320528105897093057289903813911261509744364221596754349092599941773536171331556106296046599280481554646712992461892614349798233477965259877475138994405369825177696679729437587826887692542458552640942273034046406623315798263145680891043686637391445032540395910325375468851229335375596465691932642620033840048042340560874167717227536778565093687084864153161837295278248064251713015349610408163810844931599580893498289130468322100545342214765576626305162155916461392536927172939542370552699794841546639696942494594881295110745600057366133524417482823881185678378432601423479050253273048637028860317987716898476943479237944963468932359660280494291852550606787892845073491675204759474666914399743527694155136496340145306286054418911968297458076935976668197695596679564065649545218457256747009337097533753616066105580844244678581870354460484805422460891163318275126567016218201111245008239842784312223897326256240493829297074010128721808496403649817028179402655922067452553735272112935118098361819146571967747051042335555925523097129065280695181367968739521347020479123535829218438990155045578042788217027786532541928880255659048461964830031081904398973070429000057734538932753168313024384238767541247394456519521058254015485928934810784366724254324179715676652889973536367069586419264634867275009262773583800103905515266430450939923456449494611090021711359342468052239822729109374194303746299345611328064149077421843876123990868643886890836434434739760257148038097816243546053087649691162971380180235559659909995406227405187678476435360101478277900910234390714923447334131495658146877984060452350213335133741350913893372372382750661473520560745144219025403767567466795828619770559384086516426383867438230420766577174816679626762160826485843734576247890525078588673773345671323828967305229371643946636126423808174801397883494238901936327801483179139525127964756982777998986620463231000851111119178933344251128592435756253320495730367630320796405088860883924469265007923549271763392823093339083508933874249313935417311348420618482970064864798810442199766735648403349360198497005505625756767517663136001810083403724859580183756649673884657258679172071876388173521731691492002229655726374237582150646660585229025 gives Code: (x^2 mod p)/sqrt(p) = -0.00001411401799303015 In general, 10^-4 or 10^-5 is easy using continued fractions. 10^-20 isn't. But unless you can find a way of making these numbers more likely to be smooth, none of this will help you find the factors.
Actually it is easy, using the OP's other favourite number: F12 Fermat number [which was unfactored yesterday]:

Code:
N=2^4096+1;
x=694785161528292923786070190544555127232240209017636661869870533750882763489045000867332467054810239781399921579969506436642297683669911703872080967388500816022277746167694857580457652166225682974530552047112203051070338401109908446260279847078970792145467049257338313237868081366759136762565251648862281714914995197952316755064524338400918179455572546482880077018987683158318505298442798783267438375857916262236433095094292316209710672835987139312183549242253415226918092785089300407580368162509986228628720758163796878263167474617853571423652021277601746521663261163233388784562738278204035477697005166148741791444671221013316389071199405955489346962764911029066060952806706468840007209003757098020635429100939439790001980019741636794934562528612894292850402306119554279977156597950763874443170242820415159604620459350895817305168757436309593792476838456236394332656462170141068969911112855268986127446289522931510124437002265723783571727844109653361571149379210536707047831786919502836080940586269636140465448963287720825372805929802060293541140251875634166289176827612801578044851329006633310819343967394026364504199674632920414220663751847157995328508699229052114436701607271539306507184406826769097643090735334545700591255234078;

((x^2)%N)/sqrt(N)
%3 = 9.0460488930260020189274458788248289311 E-50

x/N*1.0
%4 = 0.66525522618374281552550148589689295545
?
Do you see, reached for the squared residue < 10^(-49)*sqrt(N), beating you all.
Where is my genious cheat?   2021-02-19, 01:31   #21
charybdis

Apr 2020

3·7·11 Posts Quote:
 Originally Posted by R. Gerbicz Actually it is easy, using the OP's other favourite number: F12 Fermat number [which was unfactored yesterday]: ... Do you see, reached for the squared residue < 10^(-49)*sqrt(N), beating you all. Where is my genious cheat?
Well yes, it does help that we already know 6 factors of F12    2021-02-19, 01:53 #22 LaurV Romulan Interpreter   Jun 2011 Thailand 222428 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 2021-02-27 at 04:42   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Kosmaj Riesel Prime Search 1024 2021-04-11 17:38 petrw1 PrimeNet 1 2017-09-25 23:12 wustvn Puzzles 9 2007-12-31 05:14 OmbooHankvald Software 8 2005-07-23 01:23 mfgoode Puzzles 10 2004-12-27 15:17

All times are UTC. The time now is 15:28.

Sun Apr 18 15:28:10 UTC 2021 up 10 days, 10:09, 1 user, load averages: 1.37, 1.38, 1.44

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.