alpt says they've been having problems mailing to the list, and asked me
to forward this.
-------- Original Message --------
>From [EMAIL PROTECTED] Tue Jan 3 07:57:33 2006
Date: Tue, 3 Jan 2006 07:57:33 +0100
From: Alpt <[EMAIL PROTECTED]>
To: [email protected]
Subject: Mrepfact: a simple way to factor a Mersenne number
I don't know if this can help you guys,
but maybe yes ^_^.
Here it is:
Mrepfact
=09
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 =3D 111111
1010101 * 11 =3D 11111111
1001001 * 111 =3D 111111111
1001001001 * 111 =3D 111111111111
=2E..
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.=20
We can generalize what we've seen.
---
Considering this example:
1001001001 * 111 =3D 111111111111
We call the `1001' part of the first factor the `generator', while `111' (t=
he
second factor) the `replicator'.
Let `b' be the number of bits of `x' and x =3D 2^b - 1;
`n' is the number of bits of the generator.
`generator/2' =3D int(generator/2); or using the bits operators:
`generator/2' =3D 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 =3D (2+k)(n-1) =3D
=3D 2n + (n-1)k - 2
With k >=3D 0 and n >=3D 2, we have:
A(k,n) * ( 2^(n-1) -1 ) =3D 2^(2n + (n-1)k -2) - 1
or using the binary operators:
A(k,n) * ( 1<<(n-1) - 1 ) =3D 1 << ( n<<1 + (n-1)k - 2) - 1
A(k,n) is defined in this way:
=20
{
{ A(0,n) =3D 2^(n-1) + 1
{
{ A(k,n) =3D 2^(n-1 + (n-1)k) + A(k-1, n)
{
or if we use the binary operators:
=20
{
{ A(0,n) =3D (1<<(n-1)) |1
{ A(k,n) =3D ( (1<<(n-1)) << ((n-1)k) ) | A(k-1,n) | 1
{
=20
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.
=20
The parameter `n' indicates how many zeros shall be in `A(k,n)', for examp=
le
using n=3D4 we get: 1`n-2 zeros'1 =3D=3D 1001.
`k' is the number of repetitions of A(0,n), f.e:
a(0,4) =3D 9 /* 0b1001 */
a(1,4) =3D 73 /* 0b1001001 */
a(2,4) =3D 585 /* 0b1001001001 */
--
=46rom what we've seen we can compute two factors of a non prime Mersenne
number, which is in the form:
x=3D2^b-1
We'll see later that when `b' is prime we cannot use this method.
The steps to follow are:
b =3D number_of_bits_of_x =3D ilog2(x+1)
(ilog2 =3D floor of logarithm to base 2. We use x+1 since x=3D2^b-1)
=20
n =3D (b + 2 + k)/(2+k)
It is necessary that `n' is an integer so we must choose a `k' that give:
=20
(b+2+k) mod (2+k) =3D 0
b mod (2+k) =3D 0
Therefore `k' has to be a factor of `b' minus 2.
At this point we've found the two factors of `x':
=20
x mod A(k,n) =3D 0
x mod (2^(n-1)-1) =3D 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/ )
=3D=3D=3D EOF =3D=3D=3D
Best regards
PS: I'm sending this mail once again, the previous one didn't arrive...
--=20
:wq!
"I don't know nothing" The One Who reached the Thinking Matter '.'
[ Alpt --- Freaknet Medialab ]
[ GPG Key ID 441CF0EE ]
[ Key fingerprint =3D 8B02 26E8 831A 7BB9 81A9 5277 BFF8 037E 441C F0EE ]
>From [EMAIL PROTECTED] Tue Jan 3 07:57:33 2006
Date: Tue, 3 Jan 2006 07:57:33 +0100
From: Alpt <[EMAIL PROTECTED]>
To: [email protected]
Subject: Mrepfact: a simple way to factor a Mersenne number
Message-ID: <[EMAIL PROTECTED]>
Mime-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha1;
protocol="application/pgp-signature"; boundary="zYM0uCDKw75PZbzx"
Content-Disposition: inline
User-Agent: Mutt/1.5.10i
Status: RO
Content-Length: 3639
Lines: 155
--zYM0uCDKw75PZbzx
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
I don't know if this can help you guys,
but maybe yes ^_^.
Here it is:
Mrepfact
=09
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 =3D 111111
1010101 * 11 =3D 11111111
1001001 * 111 =3D 111111111
1001001001 * 111 =3D 111111111111
=2E..
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.=20
We can generalize what we've seen.
---
Considering this example:
1001001001 * 111 =3D 111111111111
We call the `1001' part of the first factor the `generator', while `111' (t=
he
second factor) the `replicator'.
Let `b' be the number of bits of `x' and x =3D 2^b - 1;
`n' is the number of bits of the generator.
`generator/2' =3D int(generator/2); or using the bits operators:
`generator/2' =3D 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 =3D (2+k)(n-1) =3D
=3D 2n + (n-1)k - 2
With k >=3D 0 and n >=3D 2, we have:
A(k,n) * ( 2^(n-1) -1 ) =3D 2^(2n + (n-1)k -2) - 1
or using the binary operators:
A(k,n) * ( 1<<(n-1) - 1 ) =3D 1 << ( n<<1 + (n-1)k - 2) - 1
A(k,n) is defined in this way:
=20
{
{ A(0,n) =3D 2^(n-1) + 1
{
{ A(k,n) =3D 2^(n-1 + (n-1)k) + A(k-1, n)
{
or if we use the binary operators:
=20
{
{ A(0,n) =3D (1<<(n-1)) |1
{ A(k,n) =3D ( (1<<(n-1)) << ((n-1)k) ) | A(k-1,n) | 1
{
=20
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.
=20
The parameter `n' indicates how many zeros shall be in `A(k,n)', for examp=
le
using n=3D4 we get: 1`n-2 zeros'1 =3D=3D 1001.
`k' is the number of repetitions of A(0,n), f.e:
a(0,4) =3D 9 /* 0b1001 */
a(1,4) =3D 73 /* 0b1001001 */
a(2,4) =3D 585 /* 0b1001001001 */
--
=46rom what we've seen we can compute two factors of a non prime Mersenne
number, which is in the form:
x=3D2^b-1
We'll see later that when `b' is prime we cannot use this method.
The steps to follow are:
b =3D number_of_bits_of_x =3D ilog2(x+1)
(ilog2 =3D floor of logarithm to base 2. We use x+1 since x=3D2^b-1)
=20
n =3D (b + 2 + k)/(2+k)
It is necessary that `n' is an integer so we must choose a `k' that give:
=20
(b+2+k) mod (2+k) =3D 0
b mod (2+k) =3D 0
Therefore `k' has to be a factor of `b' minus 2.
At this point we've found the two factors of `x':
=20
x mod A(k,n) =3D 0
x mod (2^(n-1)-1) =3D 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/ )
=3D=3D=3D EOF =3D=3D=3D
Best regards
PS: I'm sending this mail once again, the previous one didn't arrive...
--=20
:wq!
"I don't know nothing" The One Who reached the Thinking Matter '.'
[ Alpt --- Freaknet Medialab ]
[ GPG Key ID 441CF0EE ]
[ Key fingerprint =3D 8B02 26E8 831A 7BB9 81A9 5277 BFF8 037E 441C F0EE ]
--zYM0uCDKw75PZbzx
Content-Type: application/pgp-signature
Content-Disposition: inline
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)
iD8DBQFDuiBdv/gDfkQc8O4RAppaAKCjLSh0/LvAM0qPDGRPloNVdlRVfQCdHTbO
M74Idw8I4ot4qZOc0EtO7Rs=
=Mzgd
-----END PGP SIGNATURE-----
--zYM0uCDKw75PZbzx--
_______________________________________________
Prime mailing list
[email protected]
http://hogranch.com/mailman/listinfo/prime
