A Mersenne number is a number in the form of 2P-1.

If P is prime, the Mersenne number may be a Mersenne prime
(if P is not prime, the Mersenne number is also not prime).

In the search for Mersenne prime numbers it is advantageous to eliminate exponents by finding a small factor before starting a, potentially lengthy, Lucas-Lehmer test.

There are very efficient algorithms for determining if a number divides 2P-1 (or equivalently, if 2P mod (the number) = 1).
Some languages already have built-in implementations of this exponent-and-mod operation (called modPow or similar).

The following is how to implement this modPow yourself:

For example, let's compute 223 mod 47.
Convert the exponent 23 to binary, you get 10111. Starting with square = 1, repeatedly square it.
Remove the top bit of the exponent, and if it's 1 multiply square by the base of the exponentiation (2), then compute square modulo 47.
Use the result of the modulo from the last step as the initial value of square in the next step:

                  remove       optional   
      square      top bit   multiply by 2   mod 47
   ────────────   ───────   ─────────────   ────── 
   1*1 = 1        1  0111   1*2 = 2            2
   2*2 = 4        0   111      no              4
   4*4 = 16       1    11   16*2 = 32         32
   32*32 = 1024   1     1   1024*2 = 2048     27
   27*27 = 729    1         729*2 = 1458       1

Since 223 mod 47 = 1, 47 is a factor of 2P-1.
(To see this, subtract 1 from both sides: 223-1 = 0 mod 47.)
Since we've shown that 47 is a factor, 223-1 is not prime.
Further properties of Mersenne numbers allow us to refine the process even more.
Any factor q of 2P-1 must be of the form 2kP+1, k being a positive integer or zero. Furthermore, q must be 1 or 7 mod 8.
Finally any potential factor q must be prime.
As in other trial division algorithms, the algorithm stops when 2kP+1 > sqrt(N).

These primality tests only work on Mersenne numbers where P is prime. For example, M4=15 yields no factors using these techniques, but factors into 3 and 5, neither of which fit 2kP+1.



Task

Using the above method find a factor of 2929-1 (aka M929)



Related tasks

   count in factors
   prime decomposition
   factors of an integer
   Sieve of Eratosthenes
   primality by trial division
   trial factoring of a Mersenne number
   partition an integer X into N primes
   sequence of primes by Trial Division


See also

   Computers in 1948: 2127 - 1 
       (Note:   This video is no longer available because the YouTube account associated with this video has been terminated.)


with Ada.Text_IO;
--  reuse Is_Prime from [[Primality by Trial Division]]
with Is_Prime;
 
procedure Mersenne is
   function Is_Set (Number : Natural; Bit : Positive) return Boolean is
   begin
      return Number / 2 ** (Bit - 1) mod 2 = 1;
   end Is_Set;
 
   function Get_Max_Bit (Number : Natural) return Natural is
      Test : Natural := 0;
   begin
      while 2 ** Test <= Number loop
         Test := Test + 1;
      end loop;
      return Test;
   end Get_Max_Bit;
 
   function Modular_Power (Base, Exponent, Modulus : Positive) return Natural is
      Maximum_Bit : constant Natural := Get_Max_Bit (Exponent);
      Square      : Natural := 1;
   begin
      for Bit in reverse 1 .. Maximum_Bit loop
         Square := Square ** 2;
         if Is_Set (Exponent, Bit) then
            Square := Square * Base;
         end if;
         Square := Square mod Modulus;
      end loop;
      return Square;
   end Modular_Power;
 
   Not_A_Prime_Exponent : exception;
 
   function Get_Factor (Exponent : Positive) return Natural is
      Factor : Positive;
   begin
      if not Is_Prime (Exponent) then
         raise Not_A_Prime_Exponent;
      end if;
      for K in 1 .. 16384 / Exponent loop
         Factor := 2 * K * Exponent + 1;
         if Factor mod 8 = 1 or else Factor mod 8 = 7 then
            if Is_Prime (Factor) and then Modular_Power (2, Exponent, Factor) = 1 then
               return Factor;
            end if;
         end if;
      end loop;
      return 0;
   end Get_Factor;
 
   To_Test : constant Positive := 929;
   Factor  : Natural;
begin
   Ada.Text_IO.Put ("2 **" & Integer'Image (To_Test) & " - 1 ");
   begin
      Factor := Get_Factor (To_Test);
      if Factor = 0 then
         Ada.Text_IO.Put_Line ("is prime.");
      else
         Ada.Text_IO.Put_Line ("has factor" & Integer'Image (Factor));
      end if;
   exception
      when Not_A_Prime_Exponent =>
         Ada.Text_IO.Put_Line ("is not a Mersenne number");
   end;
end Mersenne;