 # Development ofAlgorithmic Constructions ### Helmes p+1 Factorization in the adjoined field

This is a factorization algorithm similar to Williams p+1 factorization,
but it is faster, because there is no use of a gcd in every loop.
The algorithm has the same limits as the Williams p+1 algorithm.

You can combine it with the Helmes p-1 algorithm in the complex 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;
20000900009, "=", 100003, "*", 200003