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 => a sequence, default value (10000,30000), of integers (a,b)
Outputs:
- p, an integer, a prime in the specified range. The default range is $(10^4,3*10^4)$
- r, an integer, a primitive n-th root of unity mod p

We compute the prime p as a larger prime factor of $r1^n-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