Factorising Mersenne composites

CuriousKit · 2015-10-14, 22:32

I have to ask... beyond a simple curiosity, is there any reason behind attempting to factorise a Mersenne number that has already been proven to be composite? I noticed that the user "westicles" successfully found a factor in 2^973,421 - 1 today (October 14^th, 2015), even though it's been triple-checked with the Lucas-Lehmer primality test. Of course, the factor found in this case is 88 bits long, so is definitely an impressive find, but is there a good reason for looking for the factors in such composites?

Prime95 · 2015-10-15, 03:00

Quote:

Originally Posted by CuriousKit

I have to ask... beyond a simple curiosity, is there any reason behind attempting to factorise a Mersenne number that has already been proven to be composite? I noticed that the user "westicles" successfully found a factor in 2^973,421 - 1 today (October 14^th, 2015), even though it's been triple-checked with the Lucas-Lehmer primality test. Of course, the factor found in this case is 88 bits long, so is definitely an impressive find, but is there a good reason for looking for the factors in such composites?

For the fun of it. Some people like to move Mersenne numbers from the double-checked to has-a-known-factor state. Others like the even tougher challenge of moving Mersenne numbers from the has-a-known-factor state to all-factors-known state.

retina · 2015-10-15, 03:31

To add to Prime95's post. The entire project is also for the fun of it. So it doesn't matter if someone wants to factor, or run an LL, or neither; the world will still turn as usual and wars will still be fought as usual.

CuriousKit · 2015-10-15, 04:04

For fun... heh, I can buy that! Although I'd hope we can stop the wars at least.

science_man_88 · 2015-10-15, 12:32

the main use I could find for it is in trying to eliminate factors for later exponents as they can't share factors unless the exponent itself is composite). Of course this probably would never work.

alpertron · 2015-10-15, 12:51

Well, in July I found the prime factor 782521855299947974696932851410613860657 of M1864739. I've been running the P-1 algorithm on Mersenne numbers with known factors for numbers less than M2000000. The idea is to try to find a "probably completely factored" Mersenne number, where that term means a product of primes and a probable prime.

I had several successes so far:

Code:

(2^1790743-1)/(146840927*158358984977*3835546416767873*20752172271489035681) = PRP539014
(2^750151-1)/(429934042631*7590093831289*397764574647511*8361437834787151*17383638888678527263)	= PRP225744
(2^675977-1)/(1686378749257*7171117283326998925471) = PRP203456
(2^576551-1)/4612409/64758208321/242584327930759 = PRP173528
(2^488441-1)/(61543567*30051203516986199) = PRP147012
(2^440399-1)/(16210820281161978209*31518475633*880799) = PRP132538
(2^270059-1)/540119/6481417/7124976157756725967 = PRP81265

The number at the right of "PRP" is the number of digits of that probable prime.

R.D. Silverman · 2015-10-15, 13:00

Quote:

Originally Posted by CuriousKit

I have to ask... beyond a simple curiosity, is there any reason behind attempting to factorise a Mersenne number that has already been proven to be composite? I noticed that the user "westicles" successfully found a factor in 2^973,421 - 1 today (October 14^th, 2015), even though it's been triple-checked with the Lucas-Lehmer primality test. Of course, the factor found in this case is 88 bits long, so is definitely an impressive find, but is there a good reason for looking for the factors in such composites?

Welcome to "Wagstaff's stamp collection"

xilman · 2015-10-15, 19:25

SSW isn't the only person with a stamp collection. I have one and so do you though, to be fair, I'm the one looking after your stamp albums for the moment.

Nothing wrong with stamp collection as long as it's clear at least to the collector that that is the activity being undertaken. For the avoidance of doubt, I'm pretty sure that you agree.

2015-10-14, 22:32	#1
CuriousKit "J. Gareth Moreton" Feb 2015 Nomadic 2·3²·5 Posts	Factorising Mersenne composites I have to ask... beyond a simple curiosity, is there any reason behind attempting to factorise a Mersenne number that has already been proven to be composite? I noticed that the user "westicles" successfully found a factor in 2^973,421 - 1 today (October 14^th, 2015), even though it's been triple-checked with the Lucas-Lehmer primality test. Of course, the factor found in this case is 88 bits long, so is definitely an impressive find, but is there a good reason for looking for the factors in such composites?

2015-10-15, 12:51	#6
alpertron Aug 2002 Buenos Aires, Argentina 2·11·61 Posts	Well, in July I found the prime factor 782521855299947974696932851410613860657 of M1864739. I've been running the P-1 algorithm on Mersenne numbers with known factors for numbers less than M2000000. The idea is to try to find a "probably completely factored" Mersenne number, where that term means a product of primes and a probable prime. I had several successes so far: Code: (2^1790743-1)/(146840927158358984977383554641676787320752172271489035681) = PRP539014 (2^750151-1)/(4299340426317590093831289397764574647511836143783478715117383638888678527263) = PRP225744 (2^675977-1)/(16863787492577171117283326998925471) = PRP203456 (2^576551-1)/4612409/64758208321/242584327930759 = PRP173528 (2^488441-1)/(6154356730051203516986199) = PRP147012 (2^440399-1)/(1621082028116197820931518475633*880799) = PRP132538 (2^270059-1)/540119/6481417/7124976157756725967 = PRP81265 The number at the right of "PRP" is the number of digits of that probable prime.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Can Mersenne composites share "shape"?	jnml	Miscellaneous Math	31	2018-01-01 01:55
Large runs of Mersenne composites	manasi	Prime Gap Searches	3	2017-06-29 13:05
false composites with LLR	Thomas11	Riesel Prime Search	32	2008-11-20 21:04
Primes and composites	mfgoode	Miscellaneous Math	12	2005-07-05 19:19
Mersenne composites (with prime exponent)	Dougy	Math	4	2005-03-11 12:14

2015-10-15, 03:31	#3
retina Undefined "The unspeakable one" Jun 2006 My evil lair 2·31·97 Posts	To add to Prime95's post. The entire project is also for the fun of it. So it doesn't matter if someone wants to factor, or run an LL, or neither; the world will still turn as usual and wars will still be fought as usual.

2015-10-15, 04:04	#4
CuriousKit "J. Gareth Moreton" Feb 2015 Nomadic 2×3²×5 Posts	For fun... heh, I can buy that! Although I'd hope we can stop the wars at least.

2015-10-15, 12:32	#5
science_man_88 "Forget I exist" Jul 2009 Dumbassville 20300₈ Posts	the main use I could find for it is in trying to eliminate factors for later exponents as they can't share factors unless the exponent itself is composite). Of course this probably would never work.

2015-10-15, 19:25	#8
xilman Bamboozled! "𒉺𒌌𒇷𒆷𒀭" May 2003 Down not across 10100100011011₂ Posts	SSW isn't the only person with a stamp collection. I have one and so do you though, to be fair, I'm the one looking after your stamp albums for the moment. Nothing wrong with stamp collection as long as it's clear at least to the collector that that is the activity being undertaken. For the avoidance of doubt, I'm pretty sure that you agree.