Primg – Generate prime numbers whose binary representation looks like any image | Hacker News Reader

Primg – Generate prime numbers whose binary representation looks like any image

geonnave.github.io

110 pointsgeonnave53 comments

Here is my Python implementation: https://github.com/shabda/experiments/tree/master/prime_dino...

I put up a show HN, but no one liked it :) https://news.ycombinator.com/item?id=16198861

You should have added "in python" to the title.

Possibly. But I think the immediate results from browser make this one easier for people to see what is happening.

Hi shabda. I've seen your version when I was searching if someone has done this before. And you are right, I did it in Javascript because I wanted to share it with the world more easily.

Haha, awesome! Glad if it helped in anyway.

Are you putting your code on github or such? (edit: disregard the question. Its obviously at: https://github.com/geonnave/primg/)

Yes it did, especially as a confirmation that such a thing could be done xD

So long and thanks for all the fish!

The example on https://github.com/geonnave/primg shows a binary number ending with zero; doesn't that mean it's even, and therefore divisible by 2?

Hmm, that screenshot is from first tests, it is clearly a bug -- but hopefully fixed now :)

If you decrease the binary number by 1, it becomes prime. Perhaps it's this bug:

https://github.com/geonnave/primg/commit/7ec6cfaa4b581902ea1...

It is indeed! Haven't noticed the binary was wrong too.

Not convinced I actually look like

  179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357110553379400815780032957688591226535854678434413850350192892043530395436831148532011789232552521569332295554081981793617293526812832242447096911185919439189235252915185597964786711096720343

tbh ;-)

I'm not 100% sure, but do you wear glasses?

I think I see how to view this. I can see a silhouette.

    17976931348623159077293
    05190789024733617976978
    94230657273430081157732
    67580550096313270847732
    24075360211201138798713
    93357110553379400815780
    03295768859122653585467
    84344138503501928920435
    30395436831148532011789
    23255252156933229555408
    19817936172935268128322
    42447096911185919439189
    23525291518559796478671
    1096720343

look at this and unfocus your eyes

It's the binary representation that looks like the image, not the decimal one.

I unfocused it wrong and now I can see it in hexadecimal. Awesome!

  puts number.to_s(2).split("").in_groups_of(32).map{|g| g.join("")}

Well... it looks like your face was illuminated from the right?

You could probably speed things up a lot using isProbablePrime(), at least to pre-filter candidate numbers. (Assuming you're using this library: https://www.npmjs.com/package/big-integer#isprobableprimeite...)

I used isProbablePrime() before, when I had a 50x50 canvas. But it was still really really really slow. After changing to a 32x32 canvas, the difference between isPrime() and isProbablePrime() seemed negligible.

Interesting. I guess in that case the only way to speed it up is with multithreading and/or asm.js.

That makes me think that their probable prime implementation isn't that great or else that they're losing a ton of efficiency to the Javascript interpreter.

  $ time python -c 'import gmpy; gmpy.next_prime(2**2500)'
  
  real	0m0.443s

Was it taking a lot longer than that for you?

Edit: I can see that there is an element of luck in terms of how many candidates you have to look at, but I'm still seeing everything in this size range take under 2 seconds. Maybe it's a question of what probability of error you're accepting from the test?

GMP is very well optimized and implemented in assembly. There's no way that a JavaScript implementation can get anywhere close to that performance since JavaScript doesn't even have support for 64 bit integers. WebAssembly might be faster, but is still lacking many instructions commonly used for big integer arithmetic.

You could color the 1s and 0s - so the image is more obvious and enhanced.

Relevant Numberphile on generating prime pictures: https://www.youtube.com/watch?v=fQQ8IiTWHhg

Perhaps it shouldn't even bother generating a binary number that ends in '0'

Is there a way to link to a number? Or enter a number to view the image?

That is very a good idea! For now it is stateless & frontend-only. But I was thinking on improving it, like a prettier UI and adding a "print" button, or maybe a "export to png". If I ever add a server side to it, it will feature a share & see option.

Afterthought: actually, I was thinking on using IPFS to store stuff, but I do not know if its model applies to this scenario. Feedback is appreciated.

You could link to a number by just adding a query or hash with the base64 encoding of the number in 171 characters. You'd lose the original image of course.

Edit: I bet a RLE would compress down really nicely except for the bottom row if you want to reduce URL sizes

Thanks guys, you can now access a prime dog right there: https://geonnave.github.io/primg/#17976931348623159077293051...

These are very neat, but all of these I've seen the last few weeks use the same trick of putting some garbage at the end to make it a prime. I wish people would vary their techniques a bit: like, make it base 10 and make an ascii-art image, and introduce imperceptible noise to make it a prime. Or, vary the number of rows and columns, and maybe scale of the image, to make it prime.

We need to disrupt the "images as primes" industry!

Haha! I may change that over the next weekend. Also, PRs are welcome :)

Last time this kind of thing was on the front page I suggested a frame of noise around the image, which would work to hide the bottom corner.

Can you use this for encryption? Make the decryption key the prime number generated by this, and you unlock it by pointing the camera at the right thing?

I suppose if you have a very good camera, and are super-humanly precise at aiming the camera, and you have perfectly consistent lighting, then maybe.

No, not really: if you take a picture of something, it won't have the exact same pixel values every time you take it. A QR code would be way easier.

It's scaled to 32x32 black and white. The pixel values don't have to be that similar, only reasonable close.

But then I'm guessing it fudges pixels/bits until it ends up with a prime number. Is that fudging deterministic, or just random?

It tests primality of numbers greater than the number corresponding to the input image by incrementing. So it's deterministic.

Incrementing… So pixels at the bottom right of the image are the most likely to be flipped from the source image. Interesting. (Edit: Assuming big-endianness and left-to-right, top-to-bottom printing of the pixels/bits)

Nonetheless, yes, using this to create security keys would probably be a good way to lose your bitcoin. :D

Clearly the current implementation is not enough, but I wonder if there is a way to do this properly with actual security, and yet be reproducible for a normal human (we can assume the same camera and lighting).

Maybe some kind of marker in the image that is used for cropping and scaling?

Being able to see a particular image, and at a particular time of day (or indoors I guess), would definitely be an interesting security key.

(Hollywood: feel free to take this idea and do it badly :)

Actually it's decrementing: https://github.com/geonnave/primg/blob/master/index.html#L82

I guess it could change the whole image if the last pixels are "000...000", which happens when the top-left corner has an opposite color to the bottom-right one.

This image can't be "primed" correctly, for example: https://i.imgur.com/ms3sXtF.png

But that's only 1024 bits, assuming values of each pixel is independant from its neighbors. Which it isn't, so you are well under 1024 bits.

Huh? Why do you want the decryption key to be prime?

That's how RSA encryption works.

> numberBigInt = numberBigInt.minus(1)

https://github.com/geonnave/primg/blob/master/index.html#L82

Could go double as fast subtracting 2 instead of 1 (why try the even numbers).

I assume the BigInteger library, which offers isPrime() and isProbablyPrime() functions, already does that kind of optimization.

Is this in response to https://mathwithbaddrawings.files.wordpress.com/2017/10/2017... ?

https://github.com/geonnave/primg links to https://www.reddit.com/r/math/comments/7qpfls/does_there_exi... .

Previous discussion: https://news.ycombinator.com/item?id=16192608

The Python version I wrote and linked to back then (which is a bit less general): https://gitlab.com/snippets/1694391

This takes a very, very, very long time.

20 minutes in, it is up to 13388 in Firefox.

Funny enough, I ran the same image through Chrome, it said it was finish at iteration 458. I'm guessing it is not completely deterministic?

So. In some cases, which I couldn't isolate, it finds the prime but won't stop the program. On average, it should only need from 400 to 600 iterations.

I've found the problem that made this happen and it is now corrected.

Source: https://github.com/geonnave/primg

Ah, but can you generate a prime number that encompasses the full list of true statements, please? :)

Would it not be preferrable to change as little bits as possible? Instead of counting up from your number you should first try to change single bits (one bit, two, three ...)

Changing a single out of 3232 bits gives you 1024 variations. Changing two already gives you 10241023/2 = 523776 variations.

Reply on news.ycombinator.com