Implementing Fermat Attack using Maple

154 views Asked by At

I am trying to implement Fermat Attack in maple but it is giving me an error stating that Error,(unexpected. Super beginner with Maple so if anyone who does have some experience could help, it would be much appreciated.

Also, I am trying to factor an integer that is 125 digits long. Does anyone know any efficient algorithm in Maple or any other program that can handle and factor such a large integers?

FermatAtttack:=proc(n::And(posint,odd), maxnumsteps::posint:=10^7,(numsteps::truefalse:=false))
local x, k, r, i, y:
x:=isqrt(n);
if x^2 < n then
  x:= x+1
end if;
k:=2*x+1;
r:=x^2-n;
for i to maxnumsteps while not issqr(r) do
  r:=r+k;
  k:=k+2
end do;
if issqr(r) then
  x:=(k-1)/2;
  y:=isqrt(r)
else
  error "%1 could not facot in %2 iteratioons", n, maxnumsteps
end if;
if not numsteps then
  x-y, x+y
else
  x-y, x+y, i
end if;
end proc:
3

There are 3 answers

0
DrC On

The error message is a simple syntax error. Your first line is probably supposed to be

FermatAtttack:=proc(n::And(posint,odd), maxnumsteps::posint:=10^7,{numsteps::truefalse:=false})

Maple uses the command "ifactor" to factor integers.

0
user448810 On

You will need to use the Number Field Sieve to factor your 125-digit integer. See this guide to get started.

0
acer On

In your parameter sequence of the definition of your procedure FermatAttack, you have a round-bracketed item within the bracketed parameter declaration, and your error message is due to that.

(numsteps::truefalse:=false)

Change that to either just,

numsteps::truefalse:=false

or to,

{numsteps::truefalse:=false}

according to how you intend on calling it. The second of those is termed a keyword parameter. Here's a short illustration of the difference.

FA := proc( ns::truefalse:=false )
    print(ns);
end proc:

FA();
                                 false

FA(true);
                                 true

FB := proc( {ns::truefalse:=false} )
    print(ns);                        
end proc:                           

FB(); # getting the default value
                                 false

FB( ns=false );
                                 false

FB( ns=true );
                                 true

FB( ns ); # a convenience of type truefalse keyword parameters
                                 true

If you use the keyword parameter approach then note that the passed argument true in the next example doesn't match the keyword (which thus gets its default value).

FB( true );
                                 false