Hacker News Reader

Comment by reificator | Hacker News Reader

I think the more interesting way to do this would be to create a border that's roughly circular to frame the giraffe, and fill that border with noise. Then do the incrementing thing, and your 12 or so bits of noise at the end will blend in better, making it harder for the average person to reverse engineer.

I'm imaging something like this, but with a giraffe instead: https://6d4be195623157e28848-7697ece4918e0a73861de0eb37d0896...

(Sorry for unreadable CDN link)

View on HN

I had the same sort of idea, and just implemented it in Python using gmpy2 for the primality check. Here's a prime smiley face:

  111010101111001000110101111111001001000010000
  000000000000000000000000000000000000000000001
  000000000000000001110111111100000000000000001
  100000000000011110000000000011010000000000001
  000000000011100000000000000000011100000000000
  100000000100000000000000000000000011000000001
  100000011000000000000000000000000000100000001
  100000110000000001000000001000000000011000001
  100000100000000001000000001000000000001100000
  000001000000000001000000001000000000000100001
  100010000000000001000000001000000000000010000
  000010000000000001000000001000000000000010001
  000010000000000001000000001000000000000010000
  000010000000000000000000000000000000000010000
  100010000001100000000000000000001100000010001
  000001000000110000000000000000011000000100000
  000000100000011000000000000000110000001100001
  100000110000001111000000000111100000011000000
  000000011000000001111111111100000000100000000
  100000000100000000000000000000000011000000001
  000000000011100000000000000000011100000000000
  100000000000011110000000000011010000000000000
  100000000000000001110111111100000000000000000
  100000000000000000000000000000000000000000001
  111011110010001011101100010110111111110011001

As a number, it's

  418286130038247526051590581692998429049634527936177232676862400134230223310124567196900044669909574838414882468188159808593146618824409867113710174334769625185535031892647808338085451521099179358299885075661065903947563499117521951858387121272237585876050870984471996640946451287415573046990997289875221396633775785411121263373993999302553.

This took 487 random border attempts to find, which seems pretty small!

Note that efficient primality tests are probabilistic, so there's a small chance this isn't actually prime. I expect it's the same with the giraffe one in the link.

Edit: Here's the code (improved a bit over what made the picture above): https://gitlab.com/snippets/1694391

It is provably prime; I got Mathematica to generate a certificate for it in about five minutes using `PrimeQCertificate`.

Sometimes its a good idea to use a faster probable prime test when searching, and then use a slower test to verify the result. As has been done here.

Lenstra and Pomerace's variant of the AKS test is O(log(n)^6), and deterministic. So polynomial, and not a huge exponent. Still not as fast as the probabilistic algorithms, but not as slow as pre-AKS methods.

"not as slow as pre-AKS methods." only in terms of provable asymptotic bounds. It's much slower than APR-CL and ECPP, both of which existed before AKS, and are the methods used daily.

Playing with the wrap width (in this case 94), you'll see a small herd of giraffes instead. (This is the prime from the reddit article, rather than your smiley face. Easier to see white on black.)

    100000000000000000000000000000000000000000000000000000000000000110000000000000000000000000000000
    000000000000000000000000000000111000000000000000000000000000000000000000000000000000000000000111
    110000000000000000000000000000000000000000000000000000000000111111000000000000000000000000000000
    000000000000000000000000000011111110000000000000000000000000000000000000000000000000000000011111
    111000000000000000000000000000000000000000000000000000000001000011110000000000000000000000000000
    000000000000000000000000000000000111000000000000000000000000000000000000000000000000000000000000
    011110000000000000000000000000000000000000000000000000000000000000111100000000000000000000000000
    000000000000000000000000000000000011110000000000000000000000000000000000000000000000000000000000
    000111100000000000000000000000000000000000000000000000000000000000011111000000000000000000000000
    000000000000000000000000000000000000111110000000000000000000000000000000000000000000000000000000
    000011111100000000000000000000000000000000000000000000000000000000000111111100000000000000000000
    000000000000000000000000000000000000011111111100000000000000000000000000000000000000000000000000
    000000111111111100000000000000000000000000000000000000000000000000000011111111111000000000000000
    000000000000000000000000000000000000000111111111111000000000000000000000000000000000000000000000
    000000001111111111111100000000000000000000000000000000000000000000000000111111111111111100000000
    000000000000000000000000000000000000000011111111111111111000000000000000000000000000000000000000
    000000001111111111111111110000000000000000000000000000000000000000000000111111111111111111000000
    000000000000000000000000000000000000000011111111111111111110000000000000000000000000000000000000
    000000001111111111111111111000000000000000000000000000000000000000000000011111111111111111100000
    000000000000000000000000000000000000000001111111111111111110000000000000000000000000000000000000
    000000000111100001111111110000000000000000000000000000000000000000000000011110000011111111000000
    000000000000000000000000000000000000000001111000000111111100000000000000000000000000000000000000
    000000001111100000011111110000000000000000000000000000000000000000000000110110000000110111000000
    000000000000000000000000000000000000000011011000000011101110000000000000000000000000000000000000
    000000011001100000001110111000000000000000000000000000000000000000000001100110000000111001110000
    000000000000000000000000000000000000000110011000000011100110000000000000000000000000000000000000
    000000011001100000001100011000000000000000000000000000000000000000000000110010000000100001100000
    000000000000000000000000000000000000000001001000000110000110000000000000000000000000000000000000
    000000000011100000010000011000000000000000000000000000000000000000000000001110000011000001100000
    000000000000000000000000000000000000000000011000011000000110000000000000000000000000000000000000
    000000000001100001100000011000000000000000000000000000000000000000000000000111001100000001100000
    000000000000000000000000000000000000000000011100110000000110000000000000000000000000000000000000
    000000000001010011000000010000000000000000000000000000000000000000000000001100000000000011000000
    000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    000000000000000000000000000000000000000000000000000000000000001000101101001

Nice results at 192 (also three giraffes) and at 256 (four giraffes).

Pari/GP's APR-CL took 4 seconds to prove it. Perl's ntheory module took 2.6 seconds to prove with ECPP (including generating and verifying a certificate). That's over 1000x slower than BPSW but still not bad.

Reply on news.ycombinator.com