This is the coding interview for the Rust Engineer role at Phantom Zone (see Linkedin).
Implement and benchmark a rust routine that performs the forward and backward Number Theoretic Transform (NTT) over
We will judge the submission by i) performance ii) code readability and iii) documentation. We highly suggest adding unit test to ensure the solution performs correctly.
Implement NTT for prime
As a reference, we've provided a 61 bit prime 0x1fffffffffe00001 and its 2^17-th root of unity 0x15eb043c7aa2b01f, required for NTT, for
To calculate a 2N-th root of unity for an NTT friendly prime, refer to the following link.
Provide a second implementation that leverages CPU specific instructions (e.g. Intel CPUs with AVX2 or AVX512 extensions). It's acceptable to limit bit-width of primes (for ex, to
This implementation is expected to be faster than the base case.
Provide a third implementation optimized for the Goldilocks prime 0xffffffff00000001 = 0xabd0a6e8aa3d8a0e). Check this link for additional information.
This implementation is expected to be faster than one accepting a generic prime (either w.r.t. the base case or the vectorized implementation).
A solution will only be valid if:
- It performs correctly (the code correctly evaluates the NTT and INTT).
- It does so efficiently, even for the base case (e.g. by using specialized finite field arithmetic).
- It was written solely by the candidate and can be fully explained by the later.
- It is licensed under Apache 2.0.
Bonuses 1 and 2 are not needed for a submission to be valid, but are a necessary condition to be eligible for the compensation (see job post).