The end of RSA, Part 1

[RMLabrador]

Hi,

Let suppose we can find the values of x that x^2 mod p=a is less than the square root of p; and we can find many x, sqrt(p)< x<p for all of them x^2 mod p<Sqrt(p).
I find an ultra fast method to find such x.
For example, (one of RSA numbers))

p=233108530344407544527637656910680524145619812480305449042948611968495918245135782867888369318577116418213919268572658314913060672626911354027609793166341626693946596196427744273886601876896313468704059066746903123910748277606548649151920812699309766587514735456594993207

x,mod(x^2,p)/Sqrt(p)
2058686077730335973119191772849610782168405045509730859997324354659105999516762083568162982423079976943206854365767157315516369668063  0.014668356162430803200
465659067497421238677328743309425532948414157918754093707381666107398154777123979447812311531941689774171117730185960112937235923453  0.020903533758495456444
178506530939493217560703628068758041558822758826119595236870791706219502364542126714088093427241002753242504805175833751952413529673  0.024773825779890181770
4641967788565072861639467872680135512345751896450204457826578762033149163538308529904765857398517579832616621864977921442189554255818  0.013449472303315199821

and so on. This take a tini fraction of the second on the my very old pc.

If we find millions or billions of x^2 mod p =a<sqrt(p) (and keep in the mind, that value of a CAN be small, till to the 1), factoring them and find the smooth numbers and make a^2=b^2 mod p by the standart way..., even write this boring, must be a better way in the terms of the speed.

Now, I have an exponentially fast method of find x^2 mod p<sqrt(p) and just repeating, we can find x^2 mod p<<<sqrt(p). Moreover, we can, step by step, find out all of the sequence a0=1< a1<a2<a3 ... were a(n)=x(n)^2 mod p and take the full square directly from the small a)), they certainly exist, and they are rare.
So it's take a time for me to develop further solution, and its will be, i'm full of ideas))

The end of Part 1))).
P.S. You can give me any number and i give x for x^2 mod p<sqrt(p)
Amount of digits doesn't much matter

p=2^4096+1
x,(x^2 mod p)/sqrt(p)
3712941318503918005105030106698606420229383624881191830162165861886558\
7621096498935662708985340818440182303033428361071260472433079179299904\
5898956930863243903312449417053573024624956732844097342095100976245222\
8945444607125843617455321605370254188907059311308740355146299074772673\
8852185662490824156867498901807597567246290162526739899410091061271255\
7513622236226890779289018083259552975209723899635216121434385254832044\
4428801625211513067913178383256605162387940898020911006878770607989968\
5720682045701349502161359170383212098999340892390391908728652321508616\
6497101320641194353180333822491058332699915473487467860054, 0.551927

MODERATOR NOTE: Please use code tags [code] [/code] around program code and output

[axn]

Originally Posted by RMLabrador

For example, (one of RSA numbers))

p=233108530344407544527637656910680524145619812480305449042948611968495918245135782867888369318577116418213919268572658314913060672626911354027609793166341626693946596196427744273886601876896313468704059066746903123910748277606548649151920812699309766587514735456594993207

x,mod(x^2,p)/Sqrt(p)
2058686077730335973119191772849610782168405045509730859997324354659105999516762083568162982423079976943206854365767157315516369668063  0.014668356162430803200
465659067497421238677328743309425532948414157918754093707381666107398154777123979447812311531941689774171117730185960112937235923453  0.020903533758495456444
178506530939493217560703628068758041558822758826119595236870791706219502364542126714088093427241002753242504805175833751952413529673  0.024773825779890181770
4641967788565072861639467872680135512345751896450204457826578762033149163538308529904765857398517579832616621864977921442189554255818  0.013449472303315199821

and so on.

Can you double check your math on this one? I'm not getting the same results.

[RMLabrador]

Thank You!
its copy paste issue, i'm take p from wrong window)))
p must be another one (RSA too)

p=22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199

For 
p = 233108530344407544527637656910680524145619812480305449042948611968\
4959182451357828678883693185771164182139192685726583149130606726269113\
5402760979316634162669394659619642774427388660187689631346870405906674\
6903123910748277606548649151920812699309766587514735456594993207;

must be 
60156270039511115962524926339991761626930002124045078363906852618375471069499069517846923803563793649034201018868746724117680039728063728  0.011525820312644952861
30078135019755557981262463169995880813465001062022539181953426309187735534749534758923461901781896824517100509434373362058840019864031864  0.002881455078161238215
171804156903346119540741272009825446625305311264573842190606762378201248528539019757177995458173105109166645170180840926337803253037650057  0.022588388417496262820
81316397926552700985823695999486722656065596613130992916952631635266196647359422855140308702734512486889436591283194593320474521674372517  0.007428553157895737811
81316397926552700985823695999486722656065596613130992916952631635266196647359422855140308702734512486889436591283194593320474521674372517  0.007428553157895737811
172717586959853403019922623690582390212941301508469115711272491628955425690879646174237480762783658726969630321150895295203160409047411620  0.015557098233472417853

[charybdis]

Right, if N is the number we want to factor, we can find these very quickly by looking for values of k where sqrt(kN) is close to an integer.

But the problem isn't finding values of x where x^2 mod N is small: it's not hard to find lots of x for which it's around the size of sqrt(N). The difficulty comes from finding values where x^2 mod N is smooth. For this, you want numbers that are amenable to sieving, which is what QS does - and even then, it quickly becomes impractical for N above 100 digits as smooth numbers around sqrt(N) get rarer. For RSA-260 or 270, "millions and billions" of x would just be a drop in the ocean.

In addition, trying x = nearest integer to sqrt(kN) does initially find some values of x^2 mod N that are a bit smaller than sqrt(N). But as k gets larger, so do the values of x^2 mod N, so they become less and less likely to be smooth.

[xilman]

Is this not just Dixon's algorithm?

Quadratic sieve is one of several optimizations to find small residues relatively quickly.

[RMLabrador]

) No. Thats not modification of something, that alredy known.
Here, almost not exist dependence on the size of p
2^8192+1

x, (x^2 mod p)/Sqrt(p)

5720353491575715365573207647060110130930311845941594489709162339669173\
3126677002055391174158840058106144909186570744855851093731306217508995\
9904893948756275321967474142053334772728638507288543280281286290756461\
5837609477906353263812704698792858816149688772025752422991311907352876\
3308371380947492638856570549154410494535273090517737372504750670651385\
1402045808003165989729105311696878561696904595476798191526269221901297\
2415199363664663542904520069011535324223012917082110304849056309392164\
3112296309372232260926345770271256291117734247883955572564143748950201\
2184443345201434502884665779349015969722245352945784071585263882023867\
4701702966890829829675500055788514197297514679915703971620448840307557\
3044360782389514086046002012478147094087424792073565714375772067001558\
9433577219670428998448397398960749460674073247323215216367712893144571\
0358060949647927283528173599525786312849998317267529730989937814140040\
3644194938140926143797422658447268306638854123378709962459979951948091\
0907930266415417199103959789921686018969493005859797753629923068710385\
8094392178848444117376048506865352746573209529159661508854229736867428\
5538648706817872530124690134814789263156546700612819905564080225133758\
79498470008940968142224307210692421637483474, 0.196535

still less than second on the pc that was born anno 2010

[charybdis]

Originally Posted by RMLabrador

) No. Thats not modification of something, that alredy known.
Here, almost not exist dependence on the size of p
2^8192+1

x, (x^2 mod p)/Sqrt(p)

[big number = floor(sqrt(30p))], 0.196535

still less than second on the pc that was born anno 2010

As I said:

Originally Posted by charybdis

Right, if N is the number we want to factor, we can find these very quickly by looking for values of k where sqrt(kN) is close to an integer.

But the problem isn't finding values of x where x^2 mod N is small: it's not hard to find lots of x for which it's around the size of sqrt(N). The difficulty comes from finding values where x^2 mod N is smooth.

Finding x such that x^2 mod N is small is NOT the bit that becomes difficult for very large numbers. So unless you demonstrate an efficient way of finding x for which x^2 mod N is *smooth*, no-one is going to believe you have found an improvement on existing methods.

[RMLabrador]

Originally Posted by charybdis

As I said:



Finding x such that x^2 mod N is small is NOT the bit that becomes difficult for very large numbers. So unless you demonstrate an efficient way of finding x for which x^2 mod N is *smooth*, no-one is going to believe you have found an improvement on existing methods.

Are You shure? For the large p, can You find x^2 mod p~.0001*sqrt(p)? Or 10^-5*sqrt(p)? 10^-20??

[charybdis]

Originally Posted by RMLabrador

Are You shure? For the large p, can You find x^2 mod p~.0001*sqrt(p)? Or 10^-5*sqrt(p)? 10^-20??

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:

x = 803712330813026779984467996238884416214971565156928364938627476528725619263969815396609420647192767387047088537280168342583133370289681466664036601515256664532162868492066319219259007761040628727765538023351930944192148126167775008808304629533263425355385253143896320528105897093057289903813911261509744364221596754349092599941773536171331556106296046599280481554646712992461892614349798233477965259877475138994405369825177696679729437587826887692542458552640942273034046406623315798263145680891043686637391445032540395910325375468851229335375596465691932642620033840048042340560874167717227536778565093687084864153161837295278248064251713015349610408163810844931599580893498289130468322100545342214765576626305162155916461392536927172939542370552699794841546639696942494594881295110745600057366133524417482823881185678378432601423479050253273048637028860317987716898476943479237944963468932359660280494291852550606787892845073491675204759474666914399743527694155136496340145306286054418911968297458076935976668197695596679564065649545218457256747009337097533753616066105580844244678581870354460484805422460891163318275126567016218201111245008239842784312223897326256240493829297074010128721808496403649817028179402655922067452553735272112935118098361819146571967747051042335555925523097129065280695181367968739521347020479123535829218438990155045578042788217027786532541928880255659048461964830031081904398973070429000057734538932753168313024384238767541247394456519521058254015485928934810784366724254324179715676652889973536367069586419264634867275009262773583800103905515266430450939923456449494611090021711359342468052239822729109374194303746299345611328064149077421843876123990868643886890836434434739760257148038097816243546053087649691162971380180235559659909995406227405187678476435360101478277900910234390714923447334131495658146877984060452350213335133741350913893372372382750661473520560745144219025403767567466795828619770559384086516426383867438230420766577174816679626762160826485843734576247890525078588673773345671323828967305229371643946636126423808174801397883494238901936327801483179139525127964756982777998986620463231000851111119178933344251128592435756253320495730367630320796405088860883924469265007923549271763392823093339083508933874249313935417311348420618482970064864798810442199766735648403349360198497005505625756767517663136001810083403724859580183756649673884657258679172071876388173521731691492002229655726374237582150646660585229025

gives

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

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

[RMLabrador]

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.

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???
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?
To Mr. charybdis. The Signum x^2 mod p/Sqrt(p) must be + (Positive))))))