mersenneforum.org The end of RSA, Part 1
 Register FAQ Search Today's Posts Mark Forums Read

 2021-02-17, 11:42 #1 RMLabrador     "Roman V. Makarchuk" Aug 2020 Ukraine 2816 Posts The end of RSA, Part 1 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
2021-02-17, 12:54   #2
axn

Jun 2003

490510 Posts

Quote:
 Originally Posted by RMLabrador For example, (one of RSA numbers)) Code: 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.

Last fiddled with by Dr Sardonicus on 2021-02-17 at 14:49 Reason: Added code tags to quote from OP

 2021-02-17, 13:02 #3 RMLabrador     "Roman V. Makarchuk" Aug 2020 Ukraine 23×5 Posts Thank You! its copy paste issue, i'm take p from wrong window))) p must be another one (RSA too) Code: 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 Last fiddled with by Dr Sardonicus on 2021-02-17 at 14:49 Reason: Added code tags
 2021-02-17, 14:09 #4 charybdis   Apr 2020 E216 Posts 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.
 2021-02-17, 14:10 #5 xilman Bamboozled!     "𒉺𒌌𒇷𒆷𒀭" May 2003 Down not across 29·367 Posts Is this not just Dixon's algorithm? Quadratic sieve is one of several optimizations to find small residues relatively quickly.
 2021-02-17, 14:27 #6 RMLabrador     "Roman V. Makarchuk" Aug 2020 Ukraine 23×5 Posts ) 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) Code: 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 Last fiddled with by RMLabrador on 2021-02-17 at 15:15
2021-02-17, 15:20   #7
charybdis

Apr 2020

2·113 Posts

Quote:
 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) Code: [big number = floor(sqrt(30p))], 0.196535 still less than second on the pc that was born anno 2010
As I said:

Quote:
 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.

2021-02-17, 15:53   #8

"Roman V. Makarchuk"
Aug 2020
Ukraine

1010002 Posts

Quote:
 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??

2021-02-17, 16:47   #9
charybdis

Apr 2020

2×113 Posts

Quote:
 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:
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.

 2021-02-17, 16:51 #10 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 10111111000112 Posts 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.
2021-02-17, 17:27   #11

"Roman V. Makarchuk"
Aug 2020
Ukraine

23×5 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.
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))))))

Last fiddled with by RMLabrador on 2021-02-17 at 18:22

 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 04:54.

Wed Apr 14 04:54:24 UTC 2021 up 5 days, 23:35, 0 users, load averages: 5.24, 3.60, 2.96