How the FFT helps speed up schemes like PLONK.

In 1985, René Schoof published an efficient algorithm for computing the number of points on elliptic curves over finite fields.

The computation of xy modulo p is much slower than usual multiplication, since it requires a division to know how many times p has to be subtracted from the product.

How do we compute a square root of an element in a finite field of characteristics of some prime p?

The finite field fast Fourier transform is incredibly useful in cryptography, in particular in modern ZKP schemes like PLONK.

Last time I wrote about the purpose of lookups and specifically about the Halo2 lookups. However, the first scheme for checking that the values of a committed polynomial are contained in some table was introduced in the paper "plookup: A simplified polynomial protocol for lookup tables".

Lookups allow us to check whether a particular witness value is an element of some set. Such a check can be done using too but it’s much more expensive.

There’s one very important idea in PLONK that I didn’t mention last time – the permutation argument.

PLONK stands for Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge. But do not mind the incomprehensible words – PLONK is an incredibly useful cryptographic protocol.

Commitment schemes are used heavily in cryptography. In a nutshell, committing to some value means you cannot change this value later and this value is hidden to others. A Kate-Zaverucha-Goldberg commitment or simply Kate commitment allows commitment to a polynomial. And polynomial commitments are one of the building blocks of zk-rollups.

The prominent British mathematician G. H. Hardy (1877-1947) said he had never done anything useful in his life. But don’t judge him. He did many wonderful things but is somehow, unfortunately, most famous for his discovery of Srinivasa Ramanujan (1887–1920).