ethsnarks icon indicating copy to clipboard operation
ethsnarks copied to clipboard

Add roots of unity to `FQ` class

Open HarryR opened this issue 4 years ago • 0 comments

So we can do something like FQ(...).primitive_root(5) which will return a primitive 5th root of unity in the field.

There are situations where there may not be a n-th root of unity, an exception should be thrown.

It may also be beneficial to do a deterministic search for the roots of unity, so that the results are consistent across runs.

Example code:

def find_root(p, n):
	x = randint(1, p-1)
	return pow(x, (p-1)//n, p)

def find_roots(p, n):
	# https://crypto.stackexchange.com/questions/63614/finding-the-n-th-root-of-unity-in-a-finite-field
	# In particular, if N is a power of 2 and ω^(N/2) = −1, then ω is a principal N-th root of unity.
	gs = set()
	while len(gs) != n:
		gs.add(find_root(p, n))
	return list(gs)

def is_primitive_root(g, p, n):
	return pow(g, n//2, p) != 1

def primitive_roots(p, n):
	return [_ for _ in find_roots(p, n) if is_primitive_root(_, p, n)]

def primitive_root(p, n):
	while True:
		g = find_root(p, n)
		if is_primitive_root(g, p, n):
			return g

HarryR avatar Aug 19 '19 14:08 HarryR