Why is my modulus messing up?

Here is my code, it is my own take on creating Pollard's method using Matlab. For most numbers it works great, but if you use a number such as 1234567, it returns that it is divisible by 1234567, but due to the modulus, the number itself should never even show up. (By the way, 1234567 is not prime (127) is a divisor).

function Pollards_div(k)
    z = @(x) x.^2 - 7;
    y(1) = 2;
    m = 1;
    for i = 2:21
        y(i) = z(y(i-1));
    end
    while m < 11
    q = mod(y(m)-y(2*m), k);
    G = gcd(q,k);
            if G > 1
                disp([num2str(k) ' is divisible by ' num2str(G)]);
                m = m + 10;
            else
                m = m+1;
            end
    end
    end

Please help

Answer 1

[John D'Errico]

Almost always one of the iterations here will have ended up exceeding 2^53-1. That is the limit for a floating point double to be an integer. In that case, you should expect INTEGER arithmetic to fail.

A check of your code suggests the above is not the solution however. So then I took a look at Pollards method for factorization. A quick read ( here or here ) suggests that it will not always succeed for all integers.

[Tony]

Here is the same code with a few adjustments. I made sure every y(i) is less than k by the way since they are now getting modded (you pointed out its getting too large). I removed the semi colon in a test on my while loop from q and noticed y(m) - y(2*m) = 0 sometimes. If I run a GCD on a number k against 0, will the result always be the number k?

 function Pollards_div(k)
  z = @(x) x.^2 - 7;
  y(1) = 2;
  m = 1;
  for i = 2:21
      y(i) = mod(z(y(i-1)),k);
  end
  while m < 11
  q = mod(y(m)-y(2*m), k);
  G = gcd(q,k);
          if G > 1 && G < k
              disp([num2str(k) ' is divisible by ' num2str(G)]);
              m = m + 10;
          else
              m = m+1;
          end
  end
  end

[John D'Errico]

gcd(0,k) or gcd(k,0) will always return abs(k). This is strongly implied by the help, although not explicitly stated as such, and it is the only logical result. (Ok, I would have stated that fact, IF I had written the help.)

The help does state that all other GCDs besides gcd(0,0) will return a positive integer, and that gcd(0,0) returns 0.