Index Mathematics Conjectures nbv lettuce Widgets

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.

Used in the standard library

polynomial/intt_negacyclic, polynomial/ntt_negacyclic