Looking for a Primitive Roots program

[roadrunner]

(08-31-2015 03:29 PM)Joe Horn Wrote:  Wouldn't the built-in powmod function be much faster?

There's a powmod function??? Go figure.

Thanks for your help Joe. I made that change and it seems to have ended the issues I was having with large values of p.

Below is revision A; it seems to be working correctly with large values of p as long as the emulator doesn't run out of memory at p=20000 or so.

Code:

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

EXPORT smallest_p_root(p)
BEGIN
 local a,b,c,j,k;
 a:=euler(p);
 b:=ifactors(a);
 c:=length(b);
 for j from 2 to a 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 then return j;end;
  end;
 end;
END;

EXPORT p_root(p)
BEGIN
 local a,b,c,d,j,k;
 a:=euler(p);
 b:=ifactors(a);
 c:=length(b);
 d:={};
 for j from 2 to a 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;
 return d;
END;

Thanks again!!

road