prime number factorization

[dilver]

I have a problem . I want to factorize this number into two primes numbers but I am unable to find a program to do it

2107223609161105668976918317066561183910066035018968816252689949383528072901
7620910006683962065747474746709582322870618924665901484145427690586656845288
5184216817156736191122897117017204303913460454982456911293788381172179723704
4148971768379805180467794140878622058164489327264965270826072588392667925176
1833970410399147125916239687836131680486047711823435095777510281209932021075
8552707199048382382442649785375300332462260192629013022593323262011189565838
1739364984572332984356941312726357025505146283362673660738098896234205957499
7647316022718247287419422282235170644994619557795227339530396253222625063056
5358132772107223609161105668976918317066561183910066035018968816252689949383
7620910006683962065747474746709582322870618924665901484145427690586656845288
5184216817156736191122897

does anyone knows a good program that I ignore which can do the operation or direct me to a good method?

thanks

[giblit]

Why exactly are you trying to factorize that? Trying to break an encryption?

Also you do realize that the sqrt is ~14516279169129759020642150971546188931972946507286
33472133464713586028681112152214747021452764197861
76604206503372287193332632880150700736239389789270
45343410780057965783568718649430196066010357635694
37876858163720635712135893292883264568992560885554
99844180499985772327403822704034695750213861333891
42124000943875993646069558927059267497262456499028
0901644355418629470932386674762817843692359

There are going to be a crap load of primes <= to that.

Check out http://en.wikipedia.org/wiki/Integer_factorization there isn't even going to be a very effective method other than using a super computer :P

You're trying to factorize a number that is 785 digits long which means it is between 2600 and 2610 bits.

[ResidentBiscuit]

http://www.dwavesys.com/

[giblit]

I doubt Dilver has 10 million dollars :P

[dilver]

neither I am trying to win money nor am I trying to crack that key of 2600 bits . I do not care about these people putting money on challenges. I want only to know what is the efficient method or program that can factorize such a huge number . I eager to know it . it is impossible to solve that problem using a pencil and a paper . So what can I do ? I cannot even find a program that factorize that huge number. I am stuck . Any help ?

[TwilightSpectre]

I think you'll find its impossible with a computer too. Read that wikipedia article @giblit linked - you can learn how to do it there (its not all that hard). Remember, though, it took hundreds of computers 2 years to do that to a number many orders of magnitude smaller - it could be hundreds or thousands of years for your home computer to be able to factorise a number that large.

[MiiNiPaa]

And not to mention, that person which will fing a quick method of integer factorisation will kill most popular cryptography methods used today.

[ResidentBiscuit]

I cannot even find a program that factorize that huge number. I am stuck. Any help?

We've told you, it's impossible (in any reasonable amount of time). The link I posted was for a company that's basically leading the quantum computing research. This is the technology that will allow for quick prime factorization of large numbers. Until then, it's just not going to happen.

[tition]

that will allow for quick prime factorization

I would use the more cautious:

... that may eventually allow algorithms leading to quick prime factorization.

[dilver]

Thank you very much guys

:)

now I know that , in the present moment it is impossible to factorize that huge number .

but talking about finding this same number or lets say half of it divisors . The divisors

lets say of this number 2107223609161105668976918317066561183910066035018968816252689949383528072901
7620910006683962065747474746709582322870618924665901484145427690586656845288
5184216817156736191122897117017204303913460454982456911293788381172179723704
4148971768379805180467794140878622058164489327264965270826072588392667925176
1833970410399147125916239687836131680486047711823435095777510281209932021075
8552707199048382382442649785375300332462260192629013022593323262011189565838
17393649845723329843569413127263570255051

is it possible ? if yes ? is there any program in the internet that can do it ? because , my own searching , I did not find one .

[ModShop]

Make one then. It's not that hard programmatically, it just takes a while for your computer to actually run the program. There will be a limit though, there's no way your computer could factorize that number in a decent amount of time. I'm too lazy to tell how long it would actually take though.

[chrisname]

Try Shor's algorithm.

[giblit]

I think the part you are not understanding is that these are not realistic numbers to factorize. Think about how long it would take for say 100 quadrillion iterations (comparing 100 quadrillion prime numbers) on your computer? Now multiply that by a very large number and that is how long it will probably take you to solve that problem (worst case). Though if you are lucky the prime factors will be less than 1 billion and only take a matter of minutes or solve.

By the way the largest RSA number factored was only 232 digits. You are trying to factorize more than double that.


http://en.wikipedia.org/wiki/RSA_numbers

[chrisname]

giblit wrote:

Think about how long it would take for say 100 quadrillion iterations

If anyone's interested, my 3.8 GHz Phenom II x4 can do about 10⁸ iterations* per second when running one thread per core with maximum priority. 100 quadrillion is 10¹⁷, so it would take 10¹⁷-10⁸=10⁹ seconds ≈ 32 years to do 100 quadrillion iterations.

* where one iteration involved incrementing a variable and checking a different one

[giblit]

Haha so about 32 years for factoring a 35 digit number :P (Worst case) though coming up with the list of primes and modulus operator may make it take even longer.

[18hRX9L8]

http://www.quora.com/Which-is-the-fastest-prime-factorization-algorithm-to-date
http://en.wikipedia.org/wiki/General_number_field_sieve

[dilver]

thank you very much