getPrimeWithRootOfUnity -- find a prime p with a primitive n-th root of unity r in ZZ/p

Synopsis

Usage:
(p,r)=getPrimeWithRootOfUnity(n,r1)
Inputs:
- n, an integer, the exponent of the root of unity
- r1, an integer, tentative root of unity
Optional inputs:
- Range => ... (missing documentation),
Outputs:
- p, an integer, a prime in the specified range. The default range is (10⁴,3*10⁴)
- r, an integer, a primitive n-th root of unity mod p

We compute the prime p as a larger prime factor of r1ⁿ-1. If the largest p in the desired range does not work, we pass to r1+1 and repeat.

i1 : n=12

o1 = 12

i2 : (p,r)=getPrimeWithRootOfUnity(n,5)

o2 = (20593, 12)

o2 : Sequence

i3 : factor(r^n-1)

o3 = 5*7*11*13*19*29*157*20593

o3 : Expression of class Product

i4 : r^12%p==1,r^6%p==1,r^4%p==1

o4 = (true, false, false)

o4 : Sequence

i5 : (p,r)=getPrimeWithRootOfUnity(12,11,Range=>(100,200))

o5 = (157, 22)

o5 : Sequence

i6 : factor(r^n-1)

      2      2
o6 = 3 5*7*13 23*97*157*463*1489

o6 : Expression of class Product

i7 : r^12%p==1,r^6%p==1,r^4%p==1

o7 = (true, false, false)

o7 : Sequence