09-01-2015, 01:35 PM
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}
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;