How to Factor this C617

[al3ndaleeb]

Hi every one
I'm beginner in factorization
Could you help me in finding factors for number with 617 digits ?

this is my number

n =  28741083415630005255690480469107835369873791289364759588877477113146655226408918780112108295505804265014862848090865758420967993262797507950752653394882896967058604227201938597414368021195635449901810849911802939807819832338426217337987490746972599063968389045031654317669294667421342545397794432984368071311904924503743117362870668786829851809518501264300271055176829061194957753569702442207324461076377974889883998518352517982108273204221414611035306237366963775105833187994371057041920880941694821056039794643080574098576209881884616583671909936762821762650875908410320571378646248422469114912933579526946987609971

Is it possible or impossible ?

Thanks

[wblipp]

I moved your post from the GCW thread because that thread is for numbers of particular form, and it sounds unlikely that your number is of that form. Please tell us where your number comes from - some numbers come from a form that have easy factorizations. If there isn't anything special, it's too big to guarantee factorization. If it has sufficiently small factors, ECM can find them. You can try running ECM on your computer.

[henryzz]

A 2048 bit RSA key?

[R.D. Silverman]

Originally Posted by henryzz

A 2048 bit RSA key?

Probably.

[VBCurtis]

If it is an RSA key, it's almost surely possible. We should develop the tools to factor it in the next 20 or so years, and by 2040 it should take no more than a few years to factor. So, not only possible, but likely to be possible within the lifetime of a current school student.
Good luck!

[legendarymudkip]

Originally Posted by VBCurtis

If it is an RSA key, it's almost surely possible.

It's composite, so it's possible whether it's an RSA key or not, given the same time.

[VBCurtis]

Originally Posted by legendarymudkip

It's composite, so it's possible whether it's an RSA key or not, given the same time.

Agreed- my post should have begun "Even if it's an RSA key".

[al3ndaleeb]

Yes

It's RSA-2048 Public Key
and I just asking if the factorization can find the values of p & q and how long time to find it.

I used yafu tool to find the SQRT of my number
the result was

x = 169531953966295112880473438810738322165572077137608075620764766417971464535727701374051840816960729001810152102696508985685256417515370876371407395952786706436725406063631606346305384666429555180742647777876003809615650439801539233635298112359726439626866196865255272159494408714045517641548616522957189424665

It is not p value or q value but it's intermediate value between p & q
q < x < p

According to this result can we get the p or q values from this arguments ?

[retina]

Originally Posted by al3ndaleeb

I used yafu tool to find the SQRT of my number
the result was

x = 169531953966295112880473438810738322165572077137608075620764766417971464535727701374051840816960729001810152102696508985685256417515370876371407395952786706436725406063631606346305384666429555180742647777876003809615650439801539233635298112359726439626866196865255272159494408714045517641548616522957189424665

It is not p value or q value but it's intermediate value between p & q
q < x < p

According to this result can we get the p or q values from this arguments ?

Yes you can. Using the difference of squares method you could find p & q. It is relatively easy to do although you would likely need some all surpassing patience while waiting for your computer to find the result.

[Dubslow]

Originally Posted by retina

Yes you can. Using the difference of squares method you could find p & q. It is relatively easy to do although you would likely need some all surpassing patience while waiting for your computer to find the result.

"easy" in the sense of "simple to understand and implement"

Not in the sense of "I will have the result in my lifetime" though.


OP, factoring any well constructed 2048-bit RSA key is simply not possible within our lifetime with current hardware in methods. (There are possibly ways to try and see if your particular key wasn't well constructed; try collecting a bunch of other 2048 bit keys and taking the gcd of this key with all the others, for example.)

[al3ndaleeb]

Originally Posted by retina

Yes you can. Using the difference of squares method you could find p & q. It is relatively easy to do although you would likely need some all surpassing patience while waiting for your computer to find the result.

I tried to play with x value and I reached to these p & q values

p : 177132000962462750861823938095685532179675835927959587957363973518728378426087663320351561462057029060642294952689809527050347419518452276365923551958107025129027421026251346908150714661293927150625505825244109010015603836267104149363297209196111524846988712162730533642148622734330221437074857931622752219662

q : 162257995503143015120983197956574851759757721569786719181315269975455391839368542984326324979101265594648322976567527689049637750276594547174128562256239384332021910010102098060631303032021674700800574873371239616159292875998936323390971199282712145698598985201681153564859485624991216715416739051576087793093

when calculate p * q

the result :

28741083415630005255690480469107835369873791289364759588877477113146655226408918780112108295505804265014862848090865758420967993262797507950752653394882896967058604227201938597414368021195635449901810849911802939807819832338426217337987490746972599063968389045031654317669294667421342545397794432984368071311900421573405800149421633748717324708668093396127863111371969668669212247253616122413111352145054058891596528190532273313792035984202199978668120692875640410462908366310014970075642197746727089027626038906280841851230039264366391863615445748965665841123756872139125667592555239083068575625143443213848742394566

the amazing thing, the new result matched at first half part C309 of my number

matched part :
287410834156300052556904804691078353698737912893647595888774771131466552264089187801121082955058042650148628480908657584209679932627975079507526533948828969670586042272019385974143680211956354499018108499118029398078198323384262173379874907469725990639683890450316543176692946674213425453977944329843680713119

I think I'm near from finding the real p & q of my number but I don't know how to reach it at this moment.

I appreciate any suggestions.

Thanks