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  "primes"

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?250 
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.39 
Made a program to list primes until stopped. I got to about 2 billion when it took 8 GB of RAM and I more or less had to stopped it.
Only took 10% of CPU though.14 
MySQL has the absolute worst error messages.
"You have an error in your SQL syntax; check the manual that corresponds blah blah near '(some random code line)'".
How vague can you be? It doesn't help that I always find the error in a completely different place to where the message says it is.5 
CONTEST  Win big $$$ straight from Wisecrack!
For all those who participated in my original "cracking prime factorization" thread (and several I decided to add just because), I'm offering a whopping $5 to anyone who posts a 64 bit *product* of two primes, which I cant factor. Partly this is a thank you for putting up with me.
FIVE WHOLE DOLLARS! In 1909 money thats $124 dollars! Imagine how many horse and buggy rides you could buy with that back then! Or blowjobs!
Probably not a lot!
But still.
So the contest rules are simple:
Go to
https://asecuritysite.com/encryptio...
Enter 32 for the number of bits per prime, and generate a 64 bit product.
Post it here to enter the contest.
Products must be 64 bits, and the result of just *two* prime numbers. Smaller or larger bit lengths for products won't be accepted at this time.
I'm expecting a few entries on this. Entries will generally be processed in the order of submission, but I reserve the right to wave this rule.
After an entry is accepted, I'll post "challenge accepted. Factoring now."
And from that point on I have no more than 5 hours to factor the number, (but results usually arrive in 3060 minutes).
If I fail to factor your product in the specified time (from the moment I indicate I've begun factoring), congratulations, you just won $5.
Payment will be made via venmo or other method at my discretion.
One entry per user. Participants from the original thread only, as well as those explicitly mentioned.
Limitations: Factoring shall be be done
1. without *any* table lookup of primes or equivalent measures, 2. using anything greater than an i3, 3. without the aid of a gpu, 4. without multithreading. 5. without the use of more than one machine.
FINALLY:
To claim your prize, post the original factors of your product here, after the deadline has passed.
And then I'll arrange payment of the prize.
You MUST post the factors of your product after the deadline, to confirm your product and claim your prize.99 
After a year of college give everyone 2 hours to solve a programming problem in the language of their choice. Like implement a doubly linked list, or count the number of primes between two integers or something straightforward. Anyone who can’t do it gets kicked out of the major.
I’m sick of dealing with people who are 3 or 4 years into a CS degree, and can’t do 30line programming assignments in two weeks. I might have to work with one of these clowns someday and I hope to God that my university doesn’t send them into the workforce with a degree.3 
!rant
So I was experimenting with distributing load on separate processes in node.js. I wrote the simplest isPrime function for performance testing, and I calculated a lot of primes. To be able to see the result, I generated a 1920x1080 image where each white pixel represents a prime.
New wallpaper?5 
{ !rant, devlog }
I finished an exercise on Deletable Primes at http://catcoder.codingcontest.org just as part of my training for when I'm going to attend hackathons.
I could've done better than 08m 44s, by 3 minutes, if I hadn't made my initial IsPrime() method so damn inefficient that a large number wouldn't stop calculating, making me quickly debug and find the issue...
I used C#, because that's the language I currently just write most of my stuff in (and thus, I'm the fastest in out of all langs I know)
Gist: https://gist.github.com/filthycodin...2 
I got pranked. I got pranked good.
My prof at my uni had given us an asigment to do in java for a class.
Easy peasy for me, it was only a formality...
First task was normal but...
The second one included making a random number csv gen with the lenght of at least 10 digits, a class for checking which numbers are a prime or not and a class that will check numbers from that cvs and create a new cvs with only primes in it. I have created the code and only when my fans have taken off like a jet i realised... I fucked up...
In that moment i realised that prime checking might... take a while..
There was a third task but i didnt do it for obvious reasons. He wanted us to download a test set of few text files and make a csv with freq of every word in that test set. The problem was... The test set was a set of 200 literature books...17 
ok, fuck people. i mean the people who talk about things that are a big deal. you don't need to take a course in html/css to build a website, you need documentation.
people act like programming languages are a whole separate literacy. they're not. it is not a big deal, nor an accomplishment of any significance, to learn any language to a basic extent. variables, control flow, functions and scope should not be considered challenging topics, and people should stop bragging about them. i'm pretty sure this is because programming is new. as people, i think when something is new we tend to think of it as more complex and harder to understand. basic programming is not that.
ok that was a tangent from my real point. college is a scam. anyone can learn anything from books and the internet. any time you want to learn about something, go to google, and search "${my topic} site:*.github.io" and you'll have a page about that topic written by someone who is knowledgeable and passionate of the topic. colleges don't teach people how to think like these books/websites do. and i'm fucking sick of people who'd rather see a degree then a portfolio. fuck them shits bro. i can distinct my smart friends because my smart friends speak logically and enjoy becoming smarter. i would take the kid who watches aerodynamics videos on youtube and then built a plane over a kid who studied and got a five on his ap physics exam. watching then doing is better learning than watching and repeating. after all, creativity is not at all measured in our grades, and i'd like to argue that sometimes intelligence isn't even measured. i mean, people can say they're good at math, but the kids who talk about fibinnoci numbers and why there can never be two primes more than 7 (i if i remember properly) integers apart or the ones who prove cryptographic algorithms. i guess what i'm trying to say is the dumb kids aren't dumb and the smart kids aren't smart (well not that) but kids who are passionate and just do something instead of waiting for their degree to do the same thing are the best and brightest. i forgot what i was talking about. sorry it is almost 2 am and i am intoxicated , and i don't believe i got my point across very well either.9 
Today was a rather funny day in school. School starts for me at 13:40 because our timetable planners are so qualified for this job.
First 2hrs: Physics, fine its good
Second 2hrs: Discrete Maths (however you want to call it)
Goal is to write a text (30 pages, 10, etc all those standard settings). Teacher prefers Latex over word, but we can do it in word if we want. We could choose a topic, I took primes because it looked the best. I decided to use latex because I'm a fetishist and it simply looks better in the end. A classmate was arguing with our teacher about ides: texmaker vs kile. And I'm like "I use vim". So my teacher is like kk
Later that class, when we actually started doing stuff I started the ssh session to my server because I don't know any good c++ compilers for win and I'm too lazy to get a portable version of cygwin (or whatever its called). So in my server I open vim and start coding my tool for Fermat Primes (Fermatsche Primzahlen, too lazy to actually translate). And this teacher seriously is the best teacher I ever met in my life. Usually teachers are like " dude r u hakin' the school server?" and I'm like bruh its just vim and I'm doing it this way because I cannot code on your PC coz I can't install a compiler. And this teacher is like "oh hey you actually use vi, all cool kids used it in 2000. I first though u were kidding and stuff..." And we continued talking about more of stuff like that and I have to say that this is the first teacher that actually understands me. Phew
Now I'm going to continue writing my 30 pages piece of trash latex doc and hope it'll end good1 
Following on from my previous SQL script to find prime numbers
https://devrant.com/rants/2218452/...
I wondered whether there was a way to improve it by only checking for prime factors. It feels really dirty to use a WHILE loop in SQL, but I couldn't think of another way to incrementally use the already found prime numbers when checking for prime factors.
It's fast though, 2 mins 15 seconds for primes under 1,000,000  previous query took over an hour and a half.5 
Cracked my first weak RSA implementation challenge today. Feels pretty awesome.
Involved primes that were very close, which means you can factorize the modulus quickly to get the private key. Normally, you would never use close primes as prime factorization's difficulty relies a certain amount on some distance between the two values.
The reason you can brute force close primes has to do with them being close in value to the square root of the function, meaning that you can search far quicker than if you were to try every combination of primes.2 
Another GeeksForGeeks rant
Wisecrack got me a bit interested in primes (just a passing interest). I looked up their python implementation of "Sieve of Atkin". Wow, is it bad.
First of all, they use PascalCase instead of underscore_natation so that's points off right there.
Their function takes a limit as a parameter (pretty obviously).
Their program breaks if you pass a prime number as a limit. That's right, if you give it a 2, it breaks. Pretty pathetic.
Reading the comments, their Java implementation is wrong too.
For fucks sake guys, if you're going to have an algorithm blog at least write good algorithms.6 
Math question time!
Okay so I had this idea and I'm looking for anyone who has a better grasp of math than me.
What if instead of searching for prime factors we searched for a number above p?
One with a certain special property. BEAR WITH ME. I know I make these posts a lot and I'm a bit of a shitposter, but I'm being genuine here.
Take this cherry picked number, 697 for example.
It's factors are 17, and 41. It's trivial but just for demonstration.
If we represented it's factors as a bit string, where each bit represents the index that factor occurs at in a list of primes, it looks like this
1000001000000
When converted back to an integer that number becomes 4160, which we will call f.
And if we do 4160/(2**n) until the result returns
a fractional component, then N in this case will be 7.
And 7 is the index of our lowest factor 17 (lets call it A, and our highest factor we'll call B) in our primes list.
So the problem is changed from finding a factorization of p, to finding an algorithm that allows you to convert p into f. Once you have f it's a matter of converting it to binary, looking up the indexes of all bits set to 1, and finding the values of those indexes in the list of primes.
I'm working on doing that and if anyone has any insights I'm all ears.9 
Finally.... Spent over an hour trying to optimize ~5 lines of code... Guess it was a review on how to use primes for hasig but....
Root cause was I just needed a slightly faster hashing function...
1 test failed from timeout of like maybe 1sec. Test shows passed, then in details shows Timeout...
https://hackerrank.com/challenges/... 
I find it very interesting how many types of primes there are.
This kind of prime number, I think very nice!
What types of primes do you like?
https://sololearn.com/learn/12365/...6 
Is there any exact way to get the product of all primes under n multiplied together, without explicitly knowing what those primes are?
Lets call this number V.
Because hypothethetically, if we calculate from the *base* of V, then we can derive easy divisibility rules for V1 and V+1, as laid out
here:
https://notaboutapples.wordpress.com/...
And then, unless I've misunderstood something, the problem of factorization has been changed from division into an addition and subtraction problem.9 
!rant
Just posted some swift code to a server, in a few hours I should have all the prime numbers from 1 to a billion!4 
Let some number P be the product of two factors, A and B
Let the iterations of A*1..2..3..N up to B+1 be a directed graph.
Would this graph be eularian?
If so then it should be possible to use the BEST algorithm to count the number of eularian circuits, yielding B, no?
Edit: this is supported by the following text:
An arborescence can equivalently be defined as a rooted digraph in which the path from the root to any other vertex is unique.
* * *
Where the product of any two primes is unique, the path to it across our graph here, is also unique.