primitive root

[roadrunner]

function primitive_root(p) returns a list of all primitive roots of an integer.

Examples:

primitive_root(13) returns {2,6,7,11}
primitive_root(8) returns {}
primitive_root(14) returns {3,5}

Code:

#pragma mode( separator(.,;) integer(h32))

EXPORT primitive_root(p)
BEGIN
 local a,b,c,d,e,j,k;
 a:=euler(p);
 b:=ifactors(a);
 c:=length(b);
 d:={};
 for j from 2 to p-1 do
  print();
  print("checking " + j);
  for k from 1 to c step 2 do
   if powmod(j,a/b(k),p) == 1 then
    break;
   end;
   if k == c-1 then
    d(0):=j;
   end;
  end;
 end;
 if isprime(p) then
  return d;
 else
  e:={};
  for j from 1 to size(d) do
   if gcd(d(j),p)==1 then e(0):=d(j);end; 
  end;
  return e;
 end;
END;