What, if anything, can be said about the factors of 2^n - 1 when n is composite? - Page 4

JeppeSN · 2018-04-12, 15:31

Quote:

Originally Posted by CRGreathouse

In general this is very hard.

As hard as factoring other numbers of similar size? /JeppeSN

VBCurtis · 2018-04-12, 17:16

Quote:

Originally Posted by JeppeSN

As hard as factoring other numbers of similar size? /JeppeSN

If by "similar size" you mean the equivalent size after removing algebraic factors, I believe so. It may be slightly easier to find small factors, but once trial division is exhausted you're left with the usual ECM and NFS factoring tools and no benefit from the number's form.

henryzz · 2018-04-13, 06:40

You can use snfs rather than gnfs. That doesn't help much once you get to numbers that are too big for either though.

CRGreathouse · 2018-04-13, 14:31

Quote:

Originally Posted by henryzz

You can use snfs rather than gnfs. That doesn't help much once you get to numbers that are too big for either though.

Right, or if you find too many factors (from trial division or ECM) so GNFS is better than SNFS again.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Composite P-1 factors not showing up under recently cleared exponents?	ixfd64	PrimeNet	2	2018-02-28 07:54
PrimeNet has composite factors recorded	James Heinrich	PrimeNet	4	2011-09-16 14:40
is M21934219 composite ?	S485122	Data	50	2011-01-10 10:28
Missing factors at the 'Known Factors' page	MatWur-S530113	PrimeNet	11	2009-01-21 19:08
F10,21=10^(2^21)+1 is composite	Shaopu Lin	Factoring	2	2004-10-31 13:48

2018-04-13, 06:40	#36
henryzz Just call me Henry "David" Sep 2007 Cambridge (GMT/BST) 5880₁₀ Posts	You can use snfs rather than gnfs. That doesn't help much once you get to numbers that are too big for either though.