HarryR / ethsnarks

A toolkit for viable zk-SNARKS on Ethereum, Web, Mobile and Desktop
GNU Lesser General Public License v3.0
241 stars 57 forks source link

Add roots of unity to `FQ` class #156

Open HarryR opened 5 years ago

HarryR commented 5 years ago

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