Compute the smallest primitive root of unity of BLS-12-381

validate_bls_12_381_primitive_root.py

# Python3 program to find primitive root
# of a given number n
from math import sqrt
from gmpy2 import is_prime
import primefac


# Function to find smallest primitive
# root of n
def findPrimitive(n):

    if is_prime(n) == False:
        return -1

    phi = n - 1

    # Find prime factors of phi and store in a set
    s = set(primefac.primefac(phi))
    print(s)

    # Check for every number from 2 to phi
    for r in range(2, phi + 1):

        # Iterate through all prime factors of phi.
        # and check if we found a power with value 1
        flag = False
        for it in s:

            # Check if r^((phi)/primefactors)
            # mod n is 1 or not
            if pow(r, phi // it, n) == 1:

                flag = True
                break

        # If there was no power with value 1.
        if flag == False:
            return r

    # If no primitive root found
    return -1


# Driver Code
n = 0x73EDA753299D7D483339D80809A1D80553BDA402FFFE5BFEFFFFFFFF00000001
print("Smallest primitive root of", n, "is", findPrimitive(n))

from @dankrad