I'm very very new to Magma and I'm having some troubles with division between different types. My task is to implement the Pollard p-1 method (factorization method) in Magma in order to find all the prime factors of a given integer.

Basically what I want to do is to find the first prime factor, divide my given integer n by the prime number I just found and repeat the cycle until I found all the prime factors. The problem is that n (my integer) is RngIntElt while t (the prime factor) is RngIntResElt and the division "n div t" always gives me 0 (which is wrong), blocking the next cycle.

This is my code:

- Code: Select all
`E := 1; B:=17;`

for j in [2..B] do

E:=LCM(E,j);

end for;

pollard:= function(n)

R:= quo<Integers()|n>;

a := 2;

if (IsPrime(n) eq false) then

for j in [1..100] do

a := NextPrime(a);

if (n mod a) eq 0 then

return a;

else

b := (R!a)^E;

g := GCD(n,b-1);

if not (g eq 1) and not (g eq n) then

t := g;

return g;

end if;

end if;

end for;

else

return n;

end if;

end function;

n := 2*3^40+1;

repeat

t := pollard(n);

Type(t);

Type(n);

t;

n := n div t;

until (n eq 1);

This is the actual output I get:

RngIntResElt

RngIntElt

379

pollard(

n: 0

)

>> R:= quo<Integers()|n>;

^

Runtime error in quo< ... >: Illegal empty quotient

Is there some kind of conversion I can make so that the division is performed correctly? I think mine is a noob problem, but I just can't find a working solution. Let me know if you need any more info or if I did some mistakes in posting the discussion.