[dgacmu]

Related, there are a few cryptocurrencies that used things related to finding large primes as part of their proof of work functions. It turns out that ~8 years ago, a really fast primality test implementation could make you a lot of money. (For some period of time I was the author and maintainer of mining software for riecoin. Why, I have no idea, except that I like prime numbers.)

This article omits the number one optimization for fast primality testing: Montgomery multiplication

https://en.m.wikipedia.org/wiki/Montgomery_modular_multiplic...

It forms the basis of fast practical modular exponentiation implementations.

Niall Emmart, then in academia and now I believe at Nvidia, released a really, spectacularly fast GPU bigint library, CGBN: https://github.com/NVlabs/CGBN

It's still the fastest batch modexp implentation that I'm aware of. It's breathtaking, if I can gush in geek for a moment.

(Someday I should write up the story of how that helped me dominate production of a small cryptocurrency for about 5 years. Thanks, Niall - owe you a beer if we ever cross paths!)

Also worth noting that python includes an entirely fine modexp in the three-argument form of pow(x, y, m) --> compute x^y % m

With that, you can very easily implement a fermat or miller-rabin primality test if you want to roll your own, which is quite fun. If you don't, the gmp library provides a very nice mpz_probab_prime() function. Gmp is obviously faster, but it's hard to beat the fun of a two liner fermat test for playing with big primes.

[kwantam]

Great stuff dga :)

Turns out, Niall was also involved in one of the winning ZPrize submissions for fast multi-scalar multiplication (closely related to batch modexp, although over an elliptic curve rather than mod a prime); I assume it inherits from his work on CGBN.

He give a very nice talk about it last year at a Stanford crypto lunch, and it turns out the slides and recording are online!

https://cbr.stanford.edu/seminarTalks/slides_20230526_niall_...

https://www.youtube.com/watch?v=KAWlySN7Hm8

[dgacmu]

Howdy, neighbor! Thanks for this - I'm glad to hear he's still doing cool stuff. I'm off to watch that now, in fact... :-)

[mxwsn]

I'd love to read that story. Please do write it up!

[codeflo]

Do you know why said cryptocurrency would use such a bespoke proof-of-work function? I.e., was it just someone ignorant who had only a vague idea that cryptography somehow uses prime numbers and didn’t know when or why, or was there a deeper reason?

[dgacmu]

There was a really popular trend among cryptocurrencies at some point of creating a new proof of work function as a way to differentiate your coin from the sea of Bitcoin clones. Coin creators would then make unsupported claims about why their new pow was better than Bitcoin (claims such as GPU, resistance, asic resistance, or some kind of social good were common). In the case of the prime number coins (primecoin, riecoin, nexus, probably some others), it was marketing that doing the pow would, in some hand wavy way help "science". Bullshit, mostly, but...

All pow functions are just about proving that you wasted work, so there's nothing really inherently wrong with using something prime number based. The problem is that you don't really want to have mathematically and implementation intricate proof-of-work functions, because then some jerk like me comes along and is able to create a much more optimized miner, keep it private, and make money at the cost of having the other miners feel like the game is unfair. New coins in particular depend on those miners acting as marketers to shill the coin, so if they are grumpy, you lose part of your marketing team.

[cratermoon]

> New coins in particular depend on those miners acting as marketers to shill the coin

Isn't that the definition of a pyramid scheme?

[adgjlsfhk1]

welcome to cryptocurrency.

[Perepiska]

pow(x,e,mod) was the reason I switched from Perl to Python :)

[archgoon]

Even better, they implement negative exponents as well, so you don't have to find a library or cobble together an extended gcd function, since you get in inverses for free.