Factorization of a c347

default user · 2011-08-05, 15:48

The big question is how to do this?

n = 27522884532451833659149776917746638986174657900066\
198752380003170448119748075384445592779385894249597396\
094191677880219560888196851455725449439483803186859620\
146949440063016674500917668352090332377156968507248761\
790464807676623818073184400365051431209611045478502369\
831284768038953758975809687928142691906577069733299672\
994073736207656693522871409

R.D. Silverman · 2011-08-05, 17:29

Quote:

Originally Posted by default user

The big question is how to do this?

n = 27522884532451833659149776917746638986174657900066\
198752380003170448119748075384445592779385894249597396\
094191677880219560888196851455725449439483803186859620\
146949440063016674500917668352090332377156968507248761\
790464807676623818073184400365051431209611045478502369\
831284768038953758975809687928142691906577069733299672\
994073736207656693522871409

ECM, if it can be done at all. If possible, whittle it down to (say) C200, then
run GNFS.

wblipp · 2011-08-05, 19:21

Where did the number come from? Sometimes there are algebraic factors that will help (things like a^3n-1 is divisible by a^n-1). Otherwise it will require some luck. With ECM you can find factors up to 45 digits without too much trouble, 60 digits if you are willing to devote enough resources. Then you need the remainder to be prime or to be less than about 150 digits - up to 200 if you willing to apply enough resources.

default user · 2011-08-05, 20:43

Quote:

Originally Posted by wblipp

Where did the number come from?

It is a weak choice for rsa number. Primefactors from known factortables from Internet. But I don't know which tables used.

Mini-Geek · 2011-08-05, 21:39

As of when I went there, the FactorDB already had a (recently-created) entry for this number: http://factordb.com/index.php?id=1100000000442028653 Note that a 20-digit factor is known.
With your hint that the factors came from the Internet, I googled for the known factor: http://www.google.com/search?q=35135274085230907447
It is also a factor of the L part of the Aurifeuillean Factorization of 12^579+1.
Hopefully, that's a good starting point for you.

2011-08-05, 15:48	#1
default user Aug 2011 5 Posts	Factorization of a c347 The big question is how to do this? n = 27522884532451833659149776917746638986174657900066\ 198752380003170448119748075384445592779385894249597396\ 094191677880219560888196851455725449439483803186859620\ 146949440063016674500917668352090332377156968507248761\ 790464807676623818073184400365051431209611045478502369\ 831284768038953758975809687928142691906577069733299672\ 994073736207656693522871409

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Factorization of RSA-180	Robert Holmes	Factoring	19	2010-11-08 18:46
Factorization on 2^p +1	kurtulmehtap	Math	25	2010-09-12 14:13
Factorization of 7,254+	dleclair	NFSNET Discussion	1	2006-03-21 05:11
Factorization of 11,212+	Wacky	NFSNET Discussion	1	2006-03-20 23:43
Factorization of 5,307-	Jeff Gilchrist	NFSNET Discussion	7	2005-02-23 19:46

2011-08-05, 19:21	#3
wblipp "William" May 2003 New Haven 2×7×13² Posts	Where did the number come from? Sometimes there are algebraic factors that will help (things like a^3n-1 is divisible by a^n-1). Otherwise it will require some luck. With ECM you can find factors up to 45 digits without too much trouble, 60 digits if you are willing to devote enough resources. Then you need the remainder to be prime or to be less than about 150 digits - up to 200 if you willing to apply enough resources.

2011-08-05, 21:39	#5
Mini-Geek Account Deleted "Tim Sorbera" Aug 2006 San Antonio, TX USA 17·251 Posts	As of when I went there, the FactorDB already had a (recently-created) entry for this number: http://factordb.com/index.php?id=1100000000442028653 Note that a 20-digit factor is known. With your hint that the factors came from the Internet, I googled for the known factor: http://www.google.com/search?q=35135274085230907447 It is also a factor of the L part of the Aurifeuillean Factorization of 12^579+1. Hopefully, that's a good starting point for you.