Join devRant
Do all the things like
++ or  rants, post your own rants, comment on others' rants and build your customized dev avatar
Sign Up
Pipeless API
From the creators of devRant, Pipeless lets you power realtime personalized recommendations and activity feeds using a simple API
Learn More
Search  "4096"

So I cracked prime factorization. For real.
I can factor a 1024 bit product in 11hours on an i3.
No GPU acceleration, no massive memory overhead. Probably a lot faster with parallel computation on a better cpu, or even on a gpu.
4096 bits in 9798 hours.
Verifiable. Not shitting you. My hearts beating out of my fucking chest. Maybe it was an act of god, I don't know, but it works.
What should I do with it?241 
POSTMORTEM
"4096 bit ~ 96 hours is what he said.
IDK why, but when he took the challenge, he posted that it'd take 36 hours"
As @cbsa wrote, and nitwhiz wrote "but the statement was that op's i3 did it in 11 hours. So there must be a result already, which can be verified?"
I added time because I was in the middle of a port involving ArbFloat so I could get arbitrary precision. I had a crude desmos graph doing projections on what I'd already factored in order to get an idea of how long it'd take to do larger
bit lengths
@p100sch speculated on the walked back time, and overstating the rig capabilities. Instead I spent a lot of time trying to get it 'justso'.
Worse, because I had to resort to "Decimal" in python (and am currently experimenting with the same in Julia), both of which are immutable types, the GC was taking > 25% of the cpu time.
Performancewise, the numbers I cited in the actual thread, as of this time:
largest product factored was 32bit, 1855526741 * 2163967087, took 1116.111s in python.
Julia build used a slightly different method, & managed to factor a 27 bit number, 103147223 * 88789957 in 20.9s,
but this wasn't typical.
What surprised me was the variability. One bit length could take 100s or a couple thousand seconds even, and a product that was 12 bits longer could return a result in under a minute, sometimes in seconds.
This started cropping up, ironically, right after I posted the thread, whats a man to do?
So I started trying a bunch of things, some of which worked. Shameless as I am, I accepted the challenge. Things weren't perfect but it was going well enough. At that point I hadn't slept in 30~ hours so when I thought I had it I let it run and went to bed. 5 AM comes, I check the program. Still calculating, and way overshot. Fuuuuuuccc...
So here we are now and it's say to safe the worlds not gonna burn if I explain it seeing as it doesn't work, or at least only some of the time.
Others people, much smarter than me, mentioned it may be a means of finding more secure pairs, and maybe so, I'm not familiar enough to know.
For everyone that followed, commented, those who contributed, even the doubters who kept a sanity check on this without whom this would have been an even bigger embarassement, and the people with their pins and tactical dots, thanks.
So here it is.
A few assumptions first.
Assuming p = the product,
a = some prime,
b = another prime,
and r = a/b (where a is smaller than b)
w = 1/sqrt(p)
(also experimented with w = 1/sqrt(p)*2 but I kept overshooting my a very small margin)
x = a/p
y = b/p
1. for every two numbers, there is a ratio (r) that you can search for among the decimals, starting at 1.0, counting down. You can use this to find the original factors e.x. p*r=n, p/n=m (assuming the product has only two factors), instead of having to do a sieve.
2. You don't need the first number you find to be the precise value of a factor (we're doing floating point math), a large subset of decimal values for the value of a or b will naturally 'fall' into the value of a (or b) + some fractional number, which is lost. Some of you will object, "But if thats wrong, your result will be wrong!" but hear me out.
3. You round for the first factor 'found', and from there, you take the result and do p/a to get b. If 'a' is actually a factor of p, then mod(b, 1) == 0, and then naturally, a*b SHOULD equal p.
If not, you throw out both numbers, rinse and repeat.
Now I knew this this could be faster. Realized the finer the representation, the less important the fractional digits further right in the number were, it was just a matter of how much precision I could AFFORD to lose and still get an accurate result for r*p=a.
Fast forward, lot of experimentation, was hitting a lot of worst case time complexities, where the most significant digits had a bunch of zeroes in front of them so starting at 1.0 was a no go in many situations. Started looking and realized
I didn't NEED the ratio of a/b, I just needed the ratio of a to p.
Intuitively it made sense, but starting at 1.0 was blowing up the calculation time, and this made it so much worse.
I realized if I could start at r=1/sqrt(p) instead, and that because of certain properties, the fractional result of this, r, would ALWAYS be 1. close to one of the factors fractional value of n/p, and 2. it looked like it was guaranteed that r=1/sqrt(p) would ALWAYS be less than at least one of the primes, putting a bound on worst case.
The final result in executable pseudo code (python lol) looks something like the above variables plus
while w >= 0.0:
if (p / round(w*p)) % 1 == 0:
x = round(w*p)
y = p / round(w*p)
if x*y == p:
print("factors found!")
print(x)
print(y)
break
w = w + i
Still working but if anyone sees obvious problems I'd LOVE to hear about it.38 
$ dd if=/dev/sda of=/dev/sdb bs=4096
^C ^C ^C ^C ^C ^C ^C ^C ^C ^C ^C ^C ^C ^C ^C ^C ^C ^C
Happens3 
techie 1 : hey, can you give me access to X?
techie 2 : the credentials should be in the password manager repository
t1 : oh, but I don't have access to the password manager
t2 : I see your key A1B2C3D4 listed in the recipients of the file
t1 : but I lost that key :(
t2 : okay, give me your new key then.
t1 : I have my personal key uploaded to my server
t1 : can you try fetching it?
t1 : it should work with web key directory ( WKD )
t2 : okay
t2 : no record according to https://keyserver.ubuntu.com
t1 : the keyserver is personaldomain.com
t1 : try this `gpg nodefaultkeyring keyring /tmp/gpg$$ autokeylocate clear,wkd locatekeys username@personaldomain.com`
t2 : that didn't work. apparently some problem with my dirmgr `Looking for drmgr ...` and it quit
t1 : do you have `dirmngr` installed?
t2 : I have it installed `dirmngr is already the newest version (2.2.272)`
t2 : `gpg: waiting for the dirmngr to come up ... (5)` . this is the problem. I guess
t1 : maybe your gpg agent is stuck between states.
t1 : I don't recall the command to restart the GPG agent, but restarting the agent should probably fix it.
t1 : `gpgconnectagent reloadagent /bye`
source : https://superuser.com/a/1183544
t1 : *uploads ASCIIarmored key file*
t1 : but please don't use this permanently; this is a temporary key
t2 : ok
t2 : *uploads signed password file*
t1 : thanks
t2 : cool
*5 minutes later*
t1 : hey, I have forgotten the password to the key I sent you :(
t2 : okay
...
t2 : fall back to SSH public key encryption?
t1 : is that even possible?
t2 : Stack Overflow says its possible
t1 : * does a web search too *
t1 : source?
t2 : https://superuser.com/questions/...
t2 : lets try it out
t1 : okay
t2 : is this your key? *sends link to gitlab.com/username.keys*
t1 : yes, please use the ED25519 key.
t1 : the second one is my old 4096bit RSA key...
t1 : which I lost
...
t1 : wait, you can't use the ED25519 key
t2 : why not?
t1 : apparently, ED25519 key is not supported
t1 : I was trying out the steps from the answer and I hit this error :
`do_convert_to_pkcs8: unsupported key type ED25519`
t2 : :facepalm: now what
t1 : :shrug:
...
t1 : *uploads ASCIIarmored key file*
t1 : I'm sure of the password for this key
t1 : I use it everyday
t2 : *uploads signed password file*
*1 minute later*
t1 : finally... I have decrypted the file and gotten the password.
t1 : now attempting to login
t1 : I'm in!
...
t2 : I think this should be in an XKCD joke
t2 : Two tech guys sharing password.
t1 : I know a better place for it  devRant.com
t1 : if you haven't been there before; don't go there now.
t1 : go on a Friday evening; by the time you get out of it, it'll be Monday.
t1 : and you'll thank me for a _weekend well spent_
t2 : hehe.. okay.8 
int totalHourSpentOnFixingBootflags = 5;
while (!isWorking) {
Clover.flags = "x v s f nv_disable=1 injectNvidia=false ncpi=0x2000 cpus=1 dart=0 nozp maxmem=4096" + Internet.getRandomBootFlags();
}1 
Over the weekend, I made the move to use a flash as a repository (don't need no wires to repo!). Felt that needing 12 MB to store less than 2 MB was a little bit high.
So I figured "simple fix, I'll just reformat the drive from 32Kb allocation to something less, like 4Kb".
After 30 seconds of a single copy/ paste, the transfer was complete. Checking the size... accidently clicked "4096 kilobytes" instead of "4096 bytes".