find_roots_of_unity.js

const crypto = require('crypto');
const BN = require('bn.js');

const p = new BN('30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001', 16);
const pRed = BN.red(p);

function randomGroupScalar = () => {
    return new BN(crypto.randomBytes(32), 16).umod(p);
}

function getRootOfUnity(min) {

    function getDivisors(n) {
        const divisors = [];
        const t = new BN(n);
        for (let i = 1; i < n - 1; ++i) {
            const acc = new BN(i);
            if (t.div(acc).mul(acc).eq(t)) {
                divisors.push(i);
            }
        }
        return divisors;
    }

    function isPrimitive(root, divisors) {
        let isPrimitive = true;
        for (let i = 0; i < divisors.length; ++i) {
            const t = root.redPow(new BN(divisors[i]));
            isPrimitive = isPrimitive && !t.fromRed().eq(new BN(1));
        }
        return isPrimitive;
    }

    let found = false;
    let i = min - 1;
    const pTest = p.sub(new BN(1));
    while (!found) {
        i = i + 1;
        const acc = new BN(i);
        if (pTest.div(acc).mul(acc).eq(pTest)) {
            found = true;
        }
    }

    const exponent = pTest.div(new BN(i));

    const divisors = getDivisors(i);
    let foundPrimitive = false;
    let root;
    while (!foundPrimitive) {
        const base = randomGroupScalar().toRed(pRed);
        root = base.redPow(exponent);
        foundPrimitive = isPrimitive(root, divisors);
    }
    return { order: i, root };
}