mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-02-17, 11:42   #1
RMLabrador
 
RMLabrador's Avatar
 
"Roman V. Makarchuk"
Aug 2020
Ukraine

23×5 Posts
Minus 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<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))
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. 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
Code:
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

Last fiddled with by Dr Sardonicus on 2021-02-17 at 14:53 Reason: Added code tags and as indicated
RMLabrador is offline   Reply With Quote
Old 2021-02-17, 12:54   #2
axn
 
axn's Avatar
 
Jun 2003

32×5×109 Posts
Default

Quote:
Originally Posted by RMLabrador View Post
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
axn is online now   Reply With Quote
Old 2021-02-17, 13:02   #3
RMLabrador
 
RMLabrador's Avatar
 
"Roman V. Makarchuk"
Aug 2020
Ukraine

4010 Posts
Default

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
RMLabrador is offline   Reply With Quote
Old 2021-02-17, 14:09   #4
charybdis
 
Apr 2020

3428 Posts
Default

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.
charybdis is offline   Reply With Quote
Old 2021-02-17, 14:10   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

1064310 Posts
Default

Is this not just Dixon's algorithm?

Quadratic sieve is one of several optimizations to find small residues relatively quickly.
xilman is offline   Reply With Quote
Old 2021-02-17, 14:27   #6
RMLabrador
 
RMLabrador's Avatar
 
"Roman V. Makarchuk"
Aug 2020
Ukraine

2816 Posts
Default

) 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
RMLabrador is offline   Reply With Quote
Old 2021-02-17, 15:20   #7
charybdis
 
Apr 2020

2·113 Posts
Default

Quote:
Originally Posted by RMLabrador View Post
) 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 View Post
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.
charybdis is offline   Reply With Quote
Old 2021-02-17, 15:53   #8
RMLabrador
 
RMLabrador's Avatar
 
"Roman V. Makarchuk"
Aug 2020
Ukraine

23·5 Posts
Default

Quote:
Originally Posted by charybdis View Post
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??
RMLabrador is offline   Reply With Quote
Old 2021-02-17, 16:47   #9
charybdis
 
Apr 2020

2·113 Posts
Default

Quote:
Originally Posted by RMLabrador View Post
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.
charybdis is offline   Reply With Quote
Old 2021-02-17, 16:51   #10
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

10111111000112 Posts
Default

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.
retina is online now   Reply With Quote
Old 2021-02-17, 17:27   #11
RMLabrador
 
RMLabrador's Avatar
 
"Roman V. Makarchuk"
Aug 2020
Ukraine

23×5 Posts
Default

Quote:
Originally Posted by charybdis View Post
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
RMLabrador is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Riesel Primes k*2^n-1, k<300 [Part II] Kosmaj Riesel Prime Search 1024 2021-04-11 17:38
I'm sure this is an ID-10-T error on my part petrw1 PrimeNet 1 2017-09-25 23:12
Numbers in Tables : Part 2 wustvn Puzzles 9 2007-12-31 05:14
Two PC's looking for part-time work OmbooHankvald Software 8 2005-07-23 01:23
Circles part 2 mfgoode Puzzles 10 2004-12-27 15:17

All times are UTC. The time now is 11:07.

Wed Apr 14 11:07:50 UTC 2021 up 6 days, 5:48, 0 users, load averages: 1.71, 1.64, 1.62

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.