mrepfact
			
A simple algorithm to factorize non prime Mersenne numbers which have an
non prime exponent.

You can find this text and the relative source code at:
http://freaknet.org/alpt/src/mrepfact/

---

Noticing that:

10101   * 11  = 111111
1010101 * 11  = 11111111
1001001 * 111 = 111111111
1001001001 * 111 = 111111111111
...

In base 2, a repunit with an even number of digits is always divisible by 3,
in fact, this kind of repunit can be written as 1010101... * 11.
11 is 3 in binary. 

We can generalize what we've seen.

---

Considering this example:

1001001001 * 111 = 111111111111

We call the `1001' part of the first factor the `generator', while `111' (the
second factor) the `replicator'.

Let `b' be the number of bits of `x' and  x = 2^b - 1;
`n' is the number of bits of the generator.

`generator/2' = int(generator/2); or using the bits operators:
`generator/2' = generator>>1

`k' is the number of repetition of `generator/2' in the first factor minus 1,
i.e. in this case it is 2, since we have "100"-"100"-"100"-"1".

Then `b' is:
	b = (2+k)(n-1) =
	  = 2n + (n-1)k - 2


With k >= 0 and n >= 2, we have:

 A(k,n) * ( 2^(n-1) -1 ) = 2^(2n + (n-1)k -2) - 1

or using the binary operators:

 A(k,n) * ( 1<<(n-1) - 1 ) = 1 << ( n<<1 + (n-1)k - 2) - 1

A(k,n) is defined in this way:
 
 {
 { A(0,n) = 2^(n-1) + 1
 {
 { A(k,n) = 2^(n-1 + (n-1)k) + A(k-1, n)
 {

 or if we use the binary operators:
 
 {
 { A(0,n) = (1<<(n-1)) |1
 { A(k,n) = ( (1<<(n-1)) << ((n-1)k) ) | A(k-1,n) | 1
 {
 
 A(k,n) gives the first factor by repeating `k+1' times the generator,
 shifting the result to the left by one and adding 1.
 
 The parameter `n' indicates how many zeros shall be in `A(k,n)', for example
 using n=4 we get: 1`n-2 zeros'1 == 1001.
 `k' is the number of repetitions of A(0,n), f.e:
 a(0,4) = 9   /* 0b1001 */
 a(1,4) = 73  /* 0b1001001 */
 a(2,4) = 585 /* 0b1001001001 */

--

From what we've seen we can compute two factors of a non prime Mersenne
number, which is in the form:
	x=2^b-1
We'll see later that when `b' is prime we cannot use this method.

The steps to follow are:

 b = number_of_bits_of_x = ilog2(x+1)
 (ilog2 = floor of logarithm to base 2. We use x+1 since x=2^b-1)
 
 n = (b + 2 + k)/(2+k)

It is necessary that `n' is an integer so we must choose a `k' that give:
 
 (b+2+k) mod (2+k) = 0
 b mod (2+k) = 0

Therefore `k' has to be a factor of `b' minus 2.
At this point we've found the two factors of `x':
 
 x mod A(k,n) = 0
 x mod (2^(n-1)-1) = 0

Mrepfact cannot be used for numbers in the form of 2^p-1, because `n' isn't an
integer.

--
Andrea Lo Pumo  aka  AlpT <alpt (@freaknet.org)>

A lot of thanks to:
Arfalas 	( http://mirkwood.mine.nu/ )