{{omit from|GUISS}}

A Mersenne number is a number in the form of 2<sup>P</sup>-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 2<sup>P</sup>-1 (or equivalently, if 2<sup>P</sup> 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 2<sup>23</sup> mod 47.
Convert the exponent 23 to binary, you get 10111. Starting with <tt>square</tt> = 1, repeatedly square it.
Remove the top bit of the exponent, and if it's 1 multiply <tt>square</tt> by the base of the exponentiation (2), then compute <tt>square</tt> modulo 47.
Use the result of the modulo from the last step as the initial value of <tt>square</tt> 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 2<sup>23</sup> mod 47 = 1, 47 is a factor of 2<sup>P</sup>-1.
(To see this, subtract 1 from both sides: 2<sup>23</sup>-1 = 0 mod 47.)
Since we've shown that 47 is a factor, 2<sup>23</sup>-1 is not prime.
Further properties of Mersenne numbers allow us to refine the process even more.
Any factor q of 2<sup>P</sup>-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 [[Primality by Trial Division|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, M<sub>4</sub>=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  2<sup>929</sup>-1 (aka M929)


;Related tasks:
* &nbsp; [[count in factors]]
* &nbsp; [[prime decomposition]]
* &nbsp; [[factors of an integer]]
* &nbsp; [[Sieve of Eratosthenes]]
* &nbsp; [[primality by trial division]]
* &nbsp; [[trial factoring of a Mersenne number]]
* &nbsp; [[partition an integer X into N primes]]
* &nbsp; [[sequence of primes by Trial Division]]


;See also:
* &nbsp; [https://www.youtube.com/watch?v=SNwvJ7psoow Computers in 1948: 2¹²⁷-1]
<br><br>
