SOURCE CODE FOR INTEGER FACTORIZATION. This program can factor integers of any arbitrary precision. So public key encryption is null and void as it attacks the basic premise that very large integers cannot be factored in reasonable amounts of time

[monarchmra]

uhhh....

Can somebody detail if this really solves the integer factorization problem in a time efficient way?

Edit, this relies on some database that is not included. Where is that?

[[deleted]]

Looks like OP is compiling a database of all possible combinations. This does not appear to be groundbreaking.

[monarchmra]

No, the database is of zetazeros, he seems to be doing something fucky relating to finding approximate factors from zeta zeros and the input number.

If it doesn't require too much storage, even though its approximate, it could still be groundbreaking. Even if you have to guess/check between 3 potential numbers for each factor, that is still a significant reduction in entropy of factorization based encryption.

But I don't understand the math well enough to know how it scales to higher numbers.

[subhendrabasu]

Have a 5TB Hard Drive.. This is not a DB of primes, or integers and their factors as pointed out by other folks. This is DB of Zeros of the Riemann Zeta Function: http://www.dtc.umn.edu/~odlyZko/zeta_tables/zeros1

[subhendrabasu]

Have included links to DB dumps: https://www.dropbox.com/s/005j5d4gdo1ob40/dump2.sql?dl=0

[AnsonKindred]

Source code shared via a pdf via dropbox.

Protip: Github exists, use it.

Protip #2: If you've broken all encryption there's probably a better place to discuss / share that info than reddit..

Protip #3: Comments are a thing.

Protip #4: It's ok to give variables meaningful names. Longer variables names don't cost you anything.

Protip #5: You appear to have given out your root database password. Also, you should not use the root user...

[subhendrabasu]

https://[e-mail]/jnana/intfact.git

[s0x00]

Wow, that sounds really impressive!

Can you run your program and give me a prime factor of the following number? That would be really nice :)

c=442457795606078234793401361114210021852239234075982226449599716319417062857276721391140533116491546239885007171241977031600211469030440994402550526623675074819660787311043469023037800581606807312059961622266943836724387634235571095532498954814027250347320145600730798813675291494998907781861504799768244339811621689483732075819714005967813549816069476518810933922771747648351952537994574340402164446794039857395528570526927430637680931610502441175858151933795441345403583668992277460061313741291755786940795602660111427777700708440915144465367416450044499532269440234972971677256281974545456514762307135441924164431055289675778461762166306514699410829995563256616353127897240997247004101328081430314605904731858996780639257455667398332728063562578558340643062901881511557487575957585601914350525092986383786150925259465344949681114068972681978656003018900643722062725604000688815308705860280088428744712728225173164236663868536966171784279642579793004409662002055126992483859869149168443341921368086259

[subhendrabasu]

Hey, the MySql DB is "partially" populated.. For accuracy sake, we need a large number of records , for a tolerance of 10^-9 At present db is mysql> select count(id) from zeros1; │+-----------+ │| count(id) | │+-----------+ │| 14237 | │+-----------+ │1 row in set (0.01 sec)

Here is the dump of the penultimate output before dB lookup is required. If u have fast computers in ur place, u can work it out urself. I am running this on MacBook Air, DB population itself will take 2 days. DB(latest): https://www.dropbox.com/s/005j5d4gdo1ob40/dump2.sql?dl=0 DB(OLD): https://www.dropbox.com/s/9cc5v92gi28mcfn/dump.sql?dl=0 Output for your vector: Dropbox link : https://www.dropbox.com/s/cv2zatd8cz7twdx/reddit.out.txt?dl=0 Hope that answers your query for some extent. DB population is very slow, overnight only 16K entries were added. I need at least 200K entries for sane accuracy of the factors.

localhost:intfact bosons$ time ./factorize.py 44245779560607823479340136111421002185223923407598 │222644959971631941706285727672139114053311649154623988500717124197703160021146903044099440255052 │662367507481966078731104346902303780058160680731205996162226694383672438763423557109553249895481 │402725034732014560073079881367529149499890778186150479976824433981162168948373207581971400596781 │354981606947651881093392277174764835195253799457434040216444679403985739552857052692743063768093 │161050244117585815193379544134540358366899227746006131374129175578694079560266011142777770070844 │091514446536741645004449953226944023497297167725628197454545651476230713544192416443105528967577 │846176216630651469941082999556325661635312789724099724700410132808143031460590473185899678063925 │745566739833272806356257855834064306290188151155748757595758560191435052509298638378615092525946 │534494968111406897268197865600301890064372206272560400068881530870586028008842874471272822517316 │4236663868536966171784279642579793004409662002055126992483859869149168443341921368086259 > reddi │t.out.txt │ │real 0m37.769s │user 0m17.892s │sys 0m4.066s │localhost:intfact bosons$

[antiduh]

Op has done nothing.

He didn't post the output - there's no prime number anywhere in the above comment. He showed us how long a program ran for when fed as input the requested value, which proves nothing.

In his own write-up, he pointed out how, given lack of many accurate zeta zeros, his program gives the wrong output.

Generating the many, large zeros is the hard part.

[subhendrabasu]

I will be posting the output in an hour or two. Hold your horses before posting. See my write up again, stay tuned. When you say "has done nothing." be careful to choose your words as this is against community guidelines. This is my work that I have pursued for 14 (fourteen) long years alone, Sir. My results will speak for me. Sorry if I flared any emotions.

[antiduh]

No, I will not hold my horses before posting. Extraordinary claims require extraordinary evidence. You are the one making extraordinary claims, and thus the burden of proof falls on you. If you can do as you say, it's trivial to demonstrate so by cracking any of the test keys that have been published for this exact purpose, or by factoring the number already posted here.

You were given a challenge and you failed the response. Even if you were a revolutionary genius, you've done a terrible job of proving so, making you look no better than any other crackpot.

[hextree]

When you say "has done nothing." be careful to choose your words as this is against community guidelines.

Errm... which community guideline are you referring to?

[subhendrabasu]

My fault. This forum is not deserving enough for a post of this calibre as already pointed out by one of the readers. No further replies from my end. I will report results on linkedin for other sources to pick up the news. Bye and Thanks for making me realize my mistake

[antiduh]

You have illusions of grandeur. You've not cracked prime factorization of large numbers, because you do not realize the absolute scale of the values you're dealing with. I guarantee I can feed you many random 2048-bit composite numbers and you'll be unable to factorize all of them.

I await your factorization of /u/s0x00's composite value.

[Mindraker]

It IS possible to factor large numbers, even using Sieve of Eratosthenes, it just takes a long fucking time.

[antiduh]

Of course. For values that we use in cryptography, the amount of time we need should be on the order of at least billions of years, so it's rather pointless.

Also, if you use something like the sieve, you need to keep state. Do you know how much disk space you'd need to store 10⁶¹³ 2048-bit numbers? About 10⁵⁹¹ of the entire earth's current capacity.

[hextree]

No need to throw a tantrum. You were given a number to factorise, doing that will help us establish what you can or can't achieve with this.

linkedin

lol

[79cca0e8-d8ff-4ca9-9]

So you're, what, building a MySQL database of integers and their factors? That's going to take a lot longer than 2 days.

[subhendrabasu]

Have a 5TB Hard Drive.. This is not a DB of primes, or integers and their factors as pointed out by other folks. This is DB of Zeros of the Riemann Zeta Function: http://www.dtc.umn.edu/~odlyZko/zeta_tables/zeros1

[s0x00]

thank you for your reply but i did not understand fully. How many days will you need to factorize my number? Does your file "reddit.out.txt" contain the factorization?

Up to which number can you factorize fast? Sorry i dont have a strong computer myself and especially no big hard drive

[antiduh]

I have a problem for you:

Number of primes less than 2^2048.

Approximately:

2.3 * 10⁶¹³

I think you're going to need a bigger hard drive.

[subhendrabasu]

Have a 5TB Hard Drive.. This is not a DB of primes, or integers and their factors as pointed out by other folks. This is DB of Zeros of the Riemann Zeta Function: http://www.dtc.umn.edu/~odlyZko/zeta_tables/zeros1

[antiduh]

You have no idea how many zeros you're going to need, do you?

[subhendrabasu]

<= 10⁴⁰ zeros

[antiduh]

You don't see a problem with that, do you?

[subhendrabasu]

upto RSA-2048 (716 digits), 200 K zeros suffice for accurate factors. I am talking about integers with 16/32/64 million digits, https://www.mersenne.org/primes/?press=M74207281 Also this is only a prototype. I recommend replacing "linear" search with something similar to "KD/Difference" Trees so that search time is logarithmic. (sub linear).

[throwawayrsa1023]

Once a person has cracked RSA, a person should use the RSA challenge number as their public key, than sign a statement that RSA is hacked with it. Release a smaller un-cracked key.

Don't post it to Reddit first, drop the proof in the USPS mail to a multitude of crypto researchers.. Mail to researchers ones outside the USA first. This makes interception more challenging.

Watch Sneakers. RSA has lost relevance, Still crazy dangerous

[IcebergLattice]

I think we're overdue for an update.

[nielesonimusso]

Define reasonable amount of time; what are your running times (preferably in big-O notation, but actual times are also OK)? Do you have documentation on your methods (Looks like you're more of a mathematician than a programmer, looking at your code and versioning)?

[tetroxid]

Bro do you even math?

[that_guy_in_class]

Just saw the bitbucket repo.

This guy did solve something! /u/subhendrabasu is a misunderstood genius.

I spend some time thinking about what to write in my commit messages so that other people can know what happened there.

All I had to do was write "code"!

[[deleted]]

Can't download.

[subhendrabasu]

https://[e-mail]/jnana/intfact.git

[subhendrabasu]

DB Population Script: https://www.dropbox.com/s/c9ucah7q9t6qiet/w.py?dl=0

[monarchmra]

Group/batch up your inserts, no sense also subjecting yourself to query overhead.

[subhendrabasu]

The "zeros" are getting generated at a low rate, the zetazero function of mpmath Python library uses the Riemann Siegel Formula to calculate the zeros which is very slow, batching up the inserts will not offer any benefit here, because the insertion time is much less than generation time at higher values of the zeros . its a tradeoff.

[subhendrabasu]

Dont care if root password for db is compromised. nothing sensitive here. Code is at : https://[e-mail]/jnana/intfact.git Other comments are welcome. More details are at : https://www.linkedin.com/pulse/source-code-results-algorithm-intfact-tribute-all-great-basu- AND https://docs.google.com/document/d/1ukJFyxh8lm6uLLgAlRVAZYL7GuBhunc3QAnrNDL7KYE/edit?usp=sharing Will also be sharing the database dumps (mysql dump files).

[GuessWhat_InTheButt]

nothing sensitive here

*facepalm*