root_of_unity!
A static primitive n-th root of unity, or its first powers and inverse powers. Integer and field arithmetic
root_of_unity! n [, count]
Returns a primitive n-th root of unity w = g^((p - 1) / n) for the field generator g. A root exists exactly when n divides p - 1; in the milli field p - 1 = 2^20 * 3^2 * 5 * 7 * 13, so power-of-two sizes up to 2^20 work. Used for number theoretic transforms.
With a second argument it returns a tuple of two static vectors instead: the powers [1, w, w^2, ...] and the inverse powers [1, w^-1, w^-2, ...], each count long. Bind them with a tuple assignment.
Arguments
n- Static scalar, the order of the root.
count- Optional static scalar, the number of powers to return.
Returns
A static scalar, or with count a tuple of two static vectors. Expression form only.
Constraints
None.
Example
A fourth root of unity squares to -1:
(let x) static w = root_of_unity! 4 x * w * w
Powers times inverse powers are all one:
(let x) (static w, static w_inv) = root_of_unity! 4, 4 x + w * w_inv
Notes
Errors: cycle length must be static and No root of unity with cycle length n when n does not divide p - 1. The root is fixed by the field's generator, so the same n always gives the same root in a field.