The Corpus Christi Prime

Here is one script [0] that was posted on Github yesterday, I believe a few others have been popping up ever since this video [1] by Numberphile on Thursday.

[0] https://github.com/jorants/PrimeImage

[1] https://www.youtube.com/watch?v=fQQ8IiTWHhg

wglb• 9 years ago

Shades of Carl Sagan's Contact!

sarreph• 9 years ago

A more challenging 'edition' is to find a number that spells out one of its prime factors.

But then, that long number wouldn't be a prime, so it's more like prime-ception. :)

martinmj2• 9 years ago

Something like this - https://youtu.be/3IMAUm2WY70 ?

madez• 9 years ago

That isn't very difficult. Choose a prime, say 2. Now pick a sufficiently large number of digits to get a high enough resolution. Pick a number that graphically spells out 2. Replace the least significant bit of the number with a zero. You are done.

In general, "fixing" a number such that it is divisible by a given prime is easy.

eadmund• 9 years ago

I was curious about this:

Finally, I generated random fluctuations in the number and tested each with the Miller-Rabin primality test. This produced a shortlist of numbers which were very very likely to be prime. I used Dario Alpern’s fantastic tool to determine whether any of them actually were prime.

I thought that in crypto one normally just repeats Miller-Rabin enough times that it's infinitesimally improbable that the candidate isn't a prime, and that the reason for doing this is that it's too expensive to actually prove it. This indicates that it's now feasible to just prove that a number is actually prime; should crypto libraries now switch to a different method of ensuring primality?

krastanov• 9 years ago

From an engineering point of view it really does not matter. The chance that the probabilistic algorithm fails is so insignificantly small, that cosmic rays hitting your CPU registers is probably a bigger problem.

From a mathematical/CS point of view, indeed it was a fairly recent, and fairly pleasant discovery that the primality testing algorithm can be derandomized while still retaining its low complexity (it was suspected for a long time, but proving it was awesome).

Rapzid• 9 years ago

What's going on in the upper left there? :)

clemParis• 9 years ago

The first paragraph of the articles says "The top left corner encodes my initials, JRH, in ASCII. The bottom right corner is my date of birth."

The Corpus Christi Prime

Related Stories