Development of Algorithmic Constructions

Helmes p+1 Factorization in the adjoined field

Implementation in Mupad

• powermod_A:=proc (aa, bb, exp, modul, adj)
  begin
     bit:=exp mod 2;
     aq:=aa;
     bq:=bb;
     if bit = 1 then
        a:=aa;
        b:=bb;
     else
        a:=1;
        b:=0;
     end_if;
     exp:=(exp-bit)/2;
  
     while TRUE do   
        bit:=exp mod 2;
        c:=aq*aq+adj*bq*bq mod p;
        d:=2*aq*bq mod p;     
        aq:=c;
        bq:=d;
        if bit = 1 then
             e:=a*aq+adj*bq*b mod p;
             f:=a*bq+b*aq mod p;
             a:=e;
             b:=f;
        end_if;
        exp:=(exp-bit)/2; 
        if exp=0 then  
           return (0);
        end_if;
     end_while;
  end;
  
  e:=2;
  a:=1;
  b:=2;
  adj:=2;
  f:=nextprime (100000);
  g:=nextprime (200000);
  p:=f*g;
  
  while TRUE do
     a2:=a;
     b2:=b;
     ee:=e;
     for i from 1 to 1000 do
        powermod_A (a, b, e, p, adj);
        e:=e+1;
     end_for;
  
     if b=0 then
        // Repetition
        for i from 1 to 1000 do
           a:=a2;
           b:=b2;
           powermod_A (a, b, ee, p, adj);
           f:=gcd (b, p);
           if f > 1 then
              print (p,"=", f, "*", p/f);
              return (0);  
           end_if; 
           ee:=ee+1;
        end_for;
     else
        f:=gcd (b, p);
        if f > 1 then
           print (p,"=", f, "*", p/f);
           return (0);
        end_if;
     end_if;
  end_while;