Primitive 512th roots of unity mod q ≈ 2^16; SUPERSEDED BY <https://github.com/mkannwischer/dilithium-m3/blob/master/sage/find_moduli.sage>!

.gitignore

*.py

find_moduli.sage

#!/usr/bin/env sage

"""
Find moduli with 512th primitive roots of unity in the range 2^15 .. 2^16.
"""

NTH_ROOT_N = 512
SEARCH_RANGE = range(1, 2 ^ 16)

if __name__ == '__main__':
    print("{}th primitive roots in {}:".format(NTH_ROOT_N, SEARCH_RANGE))
    for q in SEARCH_RANGE:
        if not (q - 1) % NTH_ROOT_N == 0:
            # We know that there exists an n ∊ Zmod(q) with order 512 if and
            # only if the (multiplicative) order of the generator in Zmod(q)
            # is divisible by 512.
            # I.e. because q is prime, φ(q) == q-1 is divisible by 512.
            continue
        if not is_prime(q):
            # NTT does not work for this modulus
            continue

        zz = IntegerModRing(q)
        prou = None
        for n in zz:
            if n == 0:
                continue
            if n.multiplicative_order() == NTH_ROOT_N:
                prou = n
                break

        print("{}: {}".format(zz, prou))

output.txt

512th primitive roots in range(1, 65536):
Ring of integers modulo 7681: 62
Ring of integers modulo 10753: 10
Ring of integers modulo 11777: 24
Ring of integers modulo 12289: 3
Ring of integers modulo 13313: 15
Ring of integers modulo 15361: 98
Ring of integers modulo 17921: 325
Ring of integers modulo 18433: 6
Ring of integers modulo 19457: 25
Ring of integers modulo 23041: 52
Ring of integers modulo 25601: 114
Ring of integers modulo 26113: 135
Ring of integers modulo 32257: 330
Ring of integers modulo 36353: 53
Ring of integers modulo 37889: 21
Ring of integers modulo 39937: 55
Ring of integers modulo 40961: 248
Ring of integers modulo 45569: 365
Ring of integers modulo 50177: 66
Ring of integers modulo 51713: 304
Ring of integers modulo 58369: 125
Ring of integers modulo 59393: 41
Ring of integers modulo 61441: 60
Ring of integers modulo 64513: 426