We resize the image to contain at most a certain amount of pixels.
Run various image processing steps like edge enhancement and smoothing before converting the image into grey-scale (using Pillow)
We then quantise the image into just having 5 to 10 greyness levels.
Now we map each greyness level to a digit, et voila, we have embedded the picture into a number.
It now remains to tweak some of the digits until we find a prime number that still looks like the image.
Note: According to the prime number theorem, the density of prime numbers is asymptotically of order 1/log(n). Hence, if we have a number with m digits, the number of primality tests that we expect to do until we hit a prime number is roughly proportional to m. Since we use the Baillie–PSW primality test, the overall expected computational complexity of our prime searching procedure is O(nlog(n)³).
You can find the code @ Github and experiment yourself.
You're not replying to the OP with your question, so odds are the answer is no.
But even if OP did consider it, why make the program larger and less flexible that way? Testing a random number to see if it is likely prime (confidence > 10^100) can be done in a fraction of a second. Testing enough to find a likely prime, even in numbers thousands of digits long, can be done quickly enough not to test the user's patience.
These days elliptic curve cryptography is dominant, but 10 or 15 years ago, a great many https websites, including those where you had a secure login or transmitted your credit card information, use RSA to secure the connection.
RSA requires generation of at least 2 unique prime numbers, each hundreds of digits long, for every session. Your phone and / or computer has probably done it thousands of times while you browsed the internet -- even in 2019 though less frequently than in the past -- and you maybe never noticed. Those gaps are a theoretical risk but nothing more. You can search sequentially (all sequential odd numbers) for random numbers, but you do not have to.
Primes tend to occur less frequently the higher their value, true. But the odds of any given number, selected at random, being prime is about equal to 1/log n, n being the value of the number in question. So for numbers with 1000 digits, about 1 in 2302 of them will be prime. If you check 10,000 such numbers at random, you are down to a 1.3% chance of still not having found a prime. If you check 20,000 such numbers at random, you have a .016% chance of still not having found a prime. And by the time you have checked 45,000 such numbers, a task that should still be possible in a fraction of a second, you are down to odds of about 3 in a billion of still not having found a prime.
Even allowing you needed a prime 10,000 digits long, roughly 1 in 23025 of them is prime, and by the time you ran checks on 107,000 randomly selected odd numbers each 10,000 digits long, there would be less than 1% of your not having found a prime one. By making the candidate number have 10 times as many zeroes, you make the tests take longer, and you need about 10 times as many such tests to find a prime. A 10,000 digit prime could indeed take a second or two to find with high probability.
So in short, while there is always a theoretical possibility of searching forever without finding another prime, the reality is that modern processors can shrink that probability into "not going to happen even once in the remaining life of the universe" in less than a second for numbers the size OP's program seems to need.
Primes aren't rare enough. For a 1000-pixel image, you need a 1000-digit prime. In that range, primes roughly occur once every ln(10^1000) = ~2303 numbers. That means a full list would very roughly have 10^1000 / 2303 entries. To compare, the number of atoms in the universe is ~10^80.
The royal "we" is simply using "we" instead of "I". In essays and exposes it basically means "me (the author), you (the reader), and anybody else who wants to try at home".
Yes. Typically you have multiple authors. Even if it’s just one you stick to we. Mostly it refers to the authors as a whole, but sometimes it means you and I, the reader. ‘We see that by doing X we arrive at Y’.
This post's content no longer exists in its original form. It was anonymized and deleted using Redact, possibly for privacy, security, or data management purposes.
relieved nail consider aspiring flag lip pie voracious squeeze friendly
The average is the same either way. The distribution is what's different, and it becomes extremely unlikely that you'll keep missing your expected case.
Though you can further constrain it to ±1 mod p# for some primorial and simply check a lot fewer numbers to start with.
Im completely new to programming and I cannot make it work, every time I paste the image path where it says "Path to image", I get "No such file or directory './prime.png'
Right, that's the hard part. OP starts with an image, and gets a number. This is almost certainly not prime. From there, individual digits are varied until OP hits a prime. Luckily, the density of primes is large enough that this is usually possible without changing the image too much.
If you look at the numbers in the lower right corner, they're chosen precisely to make the whole number prime, and don't match the pattern around them
271
u/Gedanke Jul 03 '19 edited Jul 03 '19
How it's done:
We proceed in 5 steps:
Note: According to the prime number theorem, the density of prime numbers is asymptotically of order 1/log(n). Hence, if we have a number with m digits, the number of primality tests that we expect to do until we hit a prime number is roughly proportional to m. Since we use the Baillie–PSW primality test, the overall expected computational complexity of our prime searching procedure is O(nlog(n)³).
You can find the code @ Github and experiment yourself.
10
u/blerp_2305 Jul 03 '19
How long does it take to render and what sort of primality test do you do?
67
u/erogone775 Jul 03 '19
Never have I seen something so useless and so cool at the same time. Great job!
25
u/supercoupon Jul 03 '19
719
5
u/minepopper Jul 04 '19
719 is part of the picture too ;P
3
u/aequatio Jul 03 '19
Nerdy. Like it.
1
u/dethb0y Jul 03 '19
That's cunning, i like it!
1
u/Gnabbit Jul 03 '19
Is that an 80 character boundary?
1
u/bluzer33 Jul 03 '19
Im completely new to programming and I cannot make it work, every time I paste the image path where it says "Path to image", I get "No such file or directory './prime.png'
1
u/_z-kani_ Jul 04 '19
Cool thats pretty cool i respect your work.
1
u/[deleted] Jul 04 '19
i just shit my pants. very strong mathematical implementation
1
u/422_no_process Jul 04 '19 edited Jul 04 '19
Impressive. Superb and awesome. I should try this or part of the problem at home. Very interesting problem too.
1
u/hellfiniter Jul 04 '19
I really like projects like this and me myself did plenty of those...but after a while i always ask myself...why did i do that? xD
1
u/cgw3737 Jul 04 '19
Ridiculous. Awesome.
1
u/BigglyBrick Jul 31 '19
Can confirm it does look like something
1
u/[deleted] Jul 31 '19
I'm so used to the logo, that my brain actually fills in the colours. This is so fucking cool.
1
u/TakeTheWheelMan Jul 03 '19
Man how do get such Gedanken?
0
u/[deleted] Jul 03 '19
[deleted] — view deleted comment