Post Reply 
smallest primitive root
09-01-2015, 01:18 PM
Post: #1
smallest primitive root
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"

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;
Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: 1 Guest(s)