# NTT

## Overview

The Number Theoretic Transform (NTT) operation is used to convert an array of finite field elements representing a polynomial between coefficient and evaluation forms. The cuSnark library wraps Supranational's [sppark](https://github.com/supranational/sppark) NTT implementation.

## Performance

The following table outlines the performance improvements yielded with just the cuSnark NTT employed, showing the (CPU baseline) and accelerated results for the different proof stages in a set of proofs of various sizes. Times are in seconds, obtained on a AMD EPYC 7702 64-Core Processor with 4x NVIDIA GeForce RTX 3090 (24 GB) GPUs.

<table><thead><tr><th width="233">Proof Stage</th><th width="231">2^20 rows, 1135 columns</th><th>2^25 rows, 5 columns</th></tr></thead><tbody><tr><td>Initialization</td><td>(6.04) 6.16</td><td>(1.40) 1.41</td></tr><tr><td>Generate Instance</td><td>(0.05) 0.05</td><td>(1.05) 1.05</td></tr><tr><td>Generate Advice</td><td>(381.78) 379.87</td><td>(6.68) 4.07 </td></tr><tr><td>Generate Lookups</td><td>(57.99) 58.24 </td><td>(2.10) 1.86 </td></tr><tr><td>Commit Permutations</td><td>(146.59) 117.29</td><td>(23.72) 13.74 </td></tr><tr><td>Eval_h</td><td>(1069.09) 696.53</td><td>(66.55) 66.75 </td></tr><tr><td>Compute Evaluations</td><td>(9.81) 9.58</td><td>(35.75) 6.10 </td></tr><tr><td>Multiopen</td><td>(18.71) 18.76</td><td>(28.82) 11.61</td></tr><tr><td>Total</td><td>(1690.05) 1380.08</td><td>(166.10) 124.82</td></tr></tbody></table>