A New Largest-Known Prime Number | Hacker News Reader

A New Largest-Known Prime Number

npr.org

139 pointstshannon59 comments

We would write the number out for you, but it would fill up thousands of pages, give or take, and look like this gigantic zip file.

It's ironic to see that 11MB file being called "gigantic" in this day and age; many web pages are now unfortunately much larger, and the page of the article itself transfers at least 1MB of data.

Then it's probably in decimal form. The binary representation should compress much better :)

Explanation: A Mersenne prime is (2^n)-1 so in binary that's n 1s.

Any number N in base (N) is written as 1

no it's 10

Typical programmer. Off by zero as always.

Unironically this. NPR even has a subdomain for text only (text.npr.org), but only select articles are ported because reasons.

A thorough joke.

Read this and wondered, what estimates are there on the density of the Mersenne primes as n grows?

Google told me that, surprisingly, it's not even known that they are infinite!

I found this nice page on the Wagstaff Mersenne Conjecture:

https://primes.utm.edu/mersenne/heuristic.html

Possibly the only civilian use of quantum computing, an interesting decade is ahead.

Primality testing is actually much easier than integer factorization thanks to Fermat's "little" theorem. Methods based on this theorem, including the Lucas-Lehmer test for Mersenne primes, can identify prime numbers on classical computers in polynomial time. However, factorization is not possible with this method.

That's okay, hardly anyone needs to factor prime numbers :-)

I used to be into this stuff in college--we were obsessed with the idea of generating very large or else very large numbers of odd numbers, such as weird numbers or untouchable numbers. I was into HPC and writing programs that run on clusters, and this gave me some good practice.

We eventually realized that no one really cared about the numbers we felt confident we could find--now Mersenne primes, though, people really care about those, but they're extraordinarily difficult to find. Always a cool day to see a new one.

It's not clear to me that anyone really cares about Mersenne primes, either, which is not to detract from this cool result in any way.

Mersenne primes in binary are all 1's with length n.

PS: I remember scheduling Prime95 to run on lab computers at work (a nuclear engineering shop) after-hours, c. 1998.

The official press release from GIMPS: https://www.mersenne.org/primes/?press=M82589933

Anyone know what primality test they use? Miller-Rabin for testing then something deterministic for verification?

They use Lucas-Lehmer's[0] which is specifically for Mersenne primes[1]

https://www.mersenne.org/various/math.php#lucas-lehmer

https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality...

It would be nice if this were used as the PoW problem for a blockchain. Since the Mersenne Primes are rare, the PoW problem shouldn't be to find new Mersenne Primes directly, but something that could make indirect progress on that. Also the blockchain should solve an actual problem, such as torrent tracking or DNS.

It makes me think that there should be a list of viable uses of blockchain, and another list of interesting problems that could be moulded into PoWs, and they should be paired up into blockchains.

One problem is that a black hat could solve a lot of primes in secret, and then use those for a double spend attack.

Specifically,

a) Spend some coins to buy some other cryptocurrency

b) use all their secret primes creating a bunch of new blocks on a branch where they haven't spent their money. Since this is the longest branch now, all the other clients accept they haven't really spent it.

c) buy the other cryptocurrency again on this new branch.

Actually, the problem is that there is no way to control the difficulty. Finding new primes would be harder and harder, but you want the difficulty to adjust up or down to target a block time. Not sure how primecoin approached that problem?

Update: found some clues here, https://www.reddit.com/r/primecoin/comments/1i71ma/strange_b...

No. The PoW problem should be derived according to the current state of the blockchain. That makes "solving a lot of primes" in secret inapplicable. You read my post far too literally.

The idea is to combine the ideas behind Namecoin with Primecoin.

https://gridcoin.us/

How would you measure amount of work you want to reward with a coin? In both DNS and torrent examples one can influence a supply of work to be done rather easily

It's a broad idea to construct a secure PoW, with all that's required to make it secure, but to try and make it applicable to areas like number theory. See PrimeCoin for a successful example.

Also your concerns are unfounded: See Namecoin and Primecoin. I'm thinking these two ideas could be combined.

Two is prime.

According to German science magazine 2 is not prime

That's not a primary source and wrong. A prime is most simply: it has no factors other than itself and 1. "Not being even" is a corollary, and would be redundant if included in the definition of primality.

Another way to see this is to observe that the Fundamental Theorem of Arithmetic would be wrong (or more difficult to state succinctly) if 2 were not considered prime or if 1 were considered prime.

For example, if 2 were not prime, it would be impossible to represent the number 256 (or the number 123456) as a product of primes.

Alternatively: "even" means "multiple of 2". Saying "no primes are even" is isomorphic to saying "no primes are multiples of 3 [or any other p you choose]". A claim "n can't be prime if none of the other primes are multiples of n", implies that cannot exist at all.

This is an excellent rebuttal, nice.

It's not, though. It's one group of mathematicians appropriating prime numbers and jack-booting them into their favourite theorem. There are valid reasons to treat 1 as a prime number, just as there are for defining 0^0 as 1 in some cases. Also for a fun pastime try asking an arithmetician to apply the fundamental theorem to 1 and watch them squirm.

Presumably the arithmetician will answer that its factorization is the empty set. That's what sympy says, for example.

  >>> sympy.factorint(6)
  {2: 1, 3: 1}
  >>> sympy.factorint(1)
  {}

This definition is also sensible because it also preserves uniqueness in both directions. The empty set is the only prime factorization of 1, and 1 is the only natural number whose prime factorization is the empty set. (Wikipedia has a footnote that "Using the empty product rule one need not exclude the number 1 [from the fundamental theorem of arithmetic], and the theorem can be stated as: every positive integer has unique prime factorization.")

The fundamental theorem doesn't have to state that the prime factorization is nonempty.

It's true that some mathematicians have defined 1 as a prime number and there's nothing logically inconsistent about doing so, but it makes most theorems and formulas in number theory more complex and so this definition has fallen out of favor.

Edit: I think the Wikipedia article on the empty product gives some quite nice examples of the benefits of a closely related concept. https://en.wikipedia.org/wiki/Empty_product

> Presumably the arithmetician will answer that its factorization is the empty set.

Arithmetician (Ph.D. in number theory) here. This answer is completely correct.

As another reason why the factorization of 1 should be the empty set: suppose you have two positive integers m and n. Write S(m) and S(n) for their sets of prime divisors, counted with multiplicity.

Then S(mn) is the union of S(m) and S(n). We need S(1) to be the empty set to make this rule consistent.

Analogous to how log(1) is equal to 0.

It also is analogous to the fact that the sum of zero integers equals zero (a claim that, I guess, more laymen will find reasonable)

The analogy is a good one, as zero is the additive identity (https://en.wikipedia.org/wiki/Additive_identity) of the integers, and one is the multiplicative one (https://en.m.wikipedia.org/wiki/1#Mathematics)

See? Squirming. Somehow multiplying 0 factors is supposed to result in 1.

I'm not saying it's incorrect, but you have to explain that edge case away. At the same time allowing 1 to be prime would remove that problem given that e.g. 6 = 2^1 * 3 ^1 and 6 = 1^81 * 2^1 * 3^1 are the same unique factorisation because, well, monoids.

Edit: `s/fields/monoids`

How many prime factors does the product of two numbers have? Not the sum of the number of prime factors of the individual numbers.

Now you are the one squirming.

Cleanly accounting for edge cases isn't squirming, it's logical thinking.

Why would anyone "squirm"? You have an issue with multiplying 0 factors to obtain 1, but you don't have a problem with multiplying a number by itself 0 times to obtain 1?

What the sibling response to my own is correct. It's just the empty set.

>That's not a primary source

Heh.

Number Theory is beautiful, but impractical for daily usage or programming. Who cares ?

"Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something."

https://news.ycombinator.com/newsguidelines.html

That may be true now, but perhaps not in the future.

Heck, mathematicians in general thought number theory was “useless” up until only around 40 years ago. Now we know that our world could not have developed this way without the creation of modern cryptography.

I think number theory serves as a great example for why basic research is so important to humanity.

Impractical for daily usage? Surely you use TLS daily, in some fashion, do you not?

Reply on news.ycombinator.com