09-01-2015, 01:18 PM
function smallest_primitive_root(p) returns the smallest primitive root of an integer.
Examples:
smallest_primitive_root(7) returns: 3
smallest_primitive_root(8) returns: "no primitive roots exist"
Examples:
smallest_primitive_root(7) returns: 3
smallest_primitive_root(8) returns: "no primitive roots exist"
Code:
#pragma mode( separator(.,;) integer(h32))
EXPORT smallest_primitive_root(p)
BEGIN
local a,b,c,j,k;
a:=euler(p);
b:=ifactors(a);
c:=length(b);
for j from 2 to p−1 do
for k from 1 to c step 2 do
if powmod(j,a/b(k),p) == 1 then
break;
end;
if (k == c-1) and (gcd(j,p)==1) then
return j;
end;
end;
end;
return "no primitive roots exist";
END;