Finding factors of cunningham-like numbers - Page 9

Zeta-Flux · 2006-09-14, 15:20

Dear xilman,

I'm about to start making that list. Do you want the decimal expansions of these numbers, or would you prefer them in the form a^b -1?

Thanks,
Pace

R. Gerbicz · 2006-09-14, 15:38

Zeta-Flux, I think that Lemma 9.'s proof is wrong in your book. Why you suppose that p<10^13 ? Because you haven't proved that
it cann't be that p>10^13 and all prime divisors of q^o(p,q)-1 is smaller than 10^13.

Zeta-Flux · 2006-09-14, 16:38

Dear R. Gerbicz,

If p>10^13 then clearly q^o_q(p)-1 has a prime factor larger than 10^13, namely p.

If p<10^13, then the Keller-Richstein result tells us there are only finitely many cases to consider.

Does this clarify the lemma for you?

R. Gerbicz · 2006-09-14, 16:57

Quote:

Originally Posted by Zeta-Flux

Does this clarify the lemma for you?

Ok, that's correct. But it would be better for the reader if you could add that one line proof.

xilman · 2006-09-14, 17:46

Quote:

Originally Posted by Zeta-Flux

Dear xilman,

I'm about to start making that list. Do you want the decimal expansions of these numbers, or would you prefer them in the form a^b -1?

Thanks,
Pace

Either is fine.

Decimal expansions are in some sense easier for me (but make sure you compress the file if it looks like it's too big); A list of (a,b) pairs should be much smaller but then I'd also like a list non-algebraic factors too, so that I don't have to rediscover them.

Guidance on how much ECM/P-1/P+1 has already been done will also be very useful, so that I can set the B1 values appropriately.

Paul

Zeta-Flux · 2006-09-14, 19:57

Dear Paul,

Here are the pairs, (a,b), for which we have not found any factor of a^b-1 larger than 10^11 (so any new factor will do). Note: If I put +- after the number, that means the form a^b +1 is also one for which factors would be helpful. Also, each of the exponents is prime, so you don't have to worry about algebraic factors. I do not know how much p-1 or ECM work has been done on these. You might as well assume none. (But set B1 high enough to capture factors >10^11.) Thanks again. If this list doesn't meet your specification let me know what I can do to change it.

(a,b)=
41, 128159 +-
151, 2351 +-
157, 1973 +-
179, 5843
197, 1559443 +-
199, 14869 +-
227, 10069 +-
251, 14487
271, 42157 +-
281, 191281
397, 4657
409, 17291
433, 16187 +-
433, 122201 +-
491, 165440983
499, 4517
607, 1439401 +-
613, 509 +-
809, 2213
809, 20249
823, 577
853, 562703
881, 11192861
929, 31099802339 +-
937, 11171 +-

xilman · 2006-09-14, 20:58

Quote:

Originally Posted by Zeta-Flux

Dear Paul,

Here are the pairs, (a,b), for which we have not found any factor of a^b-1 larger than 10^11 (so any new factor will do). Note: If I put +- after the number, that means the form a^b +1 is also one for which factors would be helpful. Also, each of the exponents is prime, so you don't have to worry about algebraic factors. I do not know how much p-1 or ECM work has been done on these. You might as well assume none. (But set B1 high enough to capture factors >10^11.) Thanks again. If this list doesn't meet your specification let me know what I can do to change it.

(a,b)=
41, 128159 +-
151, 2351 +-
157, 1973 +-
179, 5843
197, 1559443 +-
199, 14869 +-
227, 10069 +-
251, 14487
271, 42157 +-
281, 191281
397, 4657
409, 17291
433, 16187 +-
433, 122201 +-
491, 165440983
499, 4517
607, 1439401 +-
613, 509 +-
809, 2213
809, 20249
823, 577
853, 562703
881, 11192861
929, 31099802339 +-
937, 11171 +-

Ok, thansk.

I've snaffled the numbers but it will take me a day or two to find enough time to set up my ECMnet servers. I hope to start this weekend.

Paul

xilman · 2006-09-14, 21:09

Quote:

Originally Posted by Zeta-Flux

Dear Paul,

Here are the pairs, (a,b), for which we have not found any factor of a^b-1 larger than 10^11 (so any new factor will do). Note: If I put +- after the number, that means the form a^b +1 is also one for which factors would be helpful. Also, each of the exponents is prime, so you don't have to worry about algebraic factors. I do not know how much p-1 or ECM work has been done on these. You might as well assume none. (But set B1 high enough to capture factors >10^11.) Thanks again. If this list doesn't meet your specification let me know what I can do to change it.

(a,b)=
41, 128159 +-
151, 2351 +-
157, 1973 +-
179, 5843
197, 1559443 +-
199, 14869 +-
227, 10069 +-
251, 14487
271, 42157 +-
281, 191281
397, 4657
409, 17291
433, 16187 +-
433, 122201 +-
491, 165440983
499, 4517
607, 1439401 +-
613, 509 +-
809, 2213
809, 20249
823, 577
853, 562703
881, 11192861
929, 31099802339 +-
937, 11171 +-

Note that the ones with very large exponents, with more than 5 digits, say, are not feasible candidates for anything other than trial division. The numbers are just too large otherwise.

I don't yet have a good program to perform TD on those numbers. I may yet write one, but no promises. Even then, finding factors >10^10 will be very hard and quite probably infeasible. For instance, I see no plausible way of factoring the penultimate number on your list. The exponent is just too big.

I'll start on the ones with exponent < 10000.

Paul

alpertron · 2006-09-14, 21:43

For the exponents in the range 5 to 7 digits, it is better to perform p-1 factoring, since the prime factors of a^b +/- 1 (where a and b are primes as in this case) have the form 2kb + 1.

So you have to include the exponent b in your p-1 factoring.

Of course you will need a powerful big number library to perform fast modular multiplications with too many digits.

frmky · 2006-09-14, 22:46

Quote:

Originally Posted by xilman

I don't yet have a good program to perform TD on those numbers. I may yet write one, but no promises. Even then, finding factors >10^10 will be very hard and quite probably infeasible. For instance, I see no plausible way of factoring the penultimate number on your list. The exponent is just too big.

All of the factors that I have submitted were found by trial division. Remember that large factors of a^n-1 are of the form kn+1 for some k. For example,
567696479734193399 | 587^634331767 - 1
567696479734193399 = 894951994 * 634331767 + 1

The program I created is quite simple. It just uses a powermod function to find a^n % (kn+1) for each odd kn+1. Using it, I searched each of the remaining numbers to k = 3.4 billion.

Greg

axn · 2006-09-14, 23:14

One question. From oddperfect.org:

Quote:

In proving this, he found it helpful to prove that there are at least two factors greater than 10^11 for some numbers of the form q^(p-1)-1 where the number is divisible by p^2.

Does that mean it is sufficient to show that any remaining factors must be > 10^11 (via exhaustive trial factoring)?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
New phi for homogeneous Cunningham numbers	wpolly	Factoring	26	2016-07-29 04:34
newbie question - finding small factors of very large numbers	NeoGen	Math	7	2007-03-13 00:04
Don't know how to work on Cunningham numbers.	jasong	GMP-ECM	6	2006-06-30 08:51
Doing Cunningham numbers but messed up.	jasong	Factoring	1	2006-04-03 17:18
Need help factoring Cunningham numbers	jasong	Factoring	27	2006-03-21 02:47

2006-09-14, 15:20	#89
Zeta-Flux May 2003 7·13·17 Posts	Dear xilman, I'm about to start making that list. Do you want the decimal expansions of these numbers, or would you prefer them in the form a^b -1? Thanks, Pace

2006-09-14, 15:38	#90
R. Gerbicz "Robert Gerbicz" Oct 2005 Hungary 2·743 Posts	Zeta-Flux, I think that Lemma 9.'s proof is wrong in your book. Why you suppose that p<10^13 ? Because you haven't proved that it cann't be that p>10^13 and all prime divisors of q^o(p,q)-1 is smaller than 10^13.

2006-09-14, 16:38	#91
Zeta-Flux May 2003 7·13·17 Posts	Dear R. Gerbicz, If p>10^13 then clearly q^o_q(p)-1 has a prime factor larger than 10^13, namely p. If p<10^13, then the Keller-Richstein result tells us there are only finitely many cases to consider. Does this clarify the lemma for you?

2006-09-14, 19:57	#94
Zeta-Flux May 2003 7·13·17 Posts	Dear Paul, Here are the pairs, (a,b), for which we have not found any factor of a^b-1 larger than 10^11 (so any new factor will do). Note: If I put +- after the number, that means the form a^b +1 is also one for which factors would be helpful. Also, each of the exponents is prime, so you don't have to worry about algebraic factors. I do not know how much p-1 or ECM work has been done on these. You might as well assume none. (But set B1 high enough to capture factors >10^11.) Thanks again. If this list doesn't meet your specification let me know what I can do to change it. (a,b)= 41, 128159 +- 151, 2351 +- 157, 1973 +- 179, 5843 197, 1559443 +- 199, 14869 +- 227, 10069 +- 251, 14487 271, 42157 +- 281, 191281 397, 4657 409, 17291 433, 16187 +- 433, 122201 +- 491, 165440983 499, 4517 607, 1439401 +- 613, 509 +- 809, 2213 809, 20249 823, 577 853, 562703 881, 11192861 929, 31099802339 +- 937, 11171 +-

2006-09-14, 21:43	#97
alpertron Aug 2002 Buenos Aires, Argentina 2·683 Posts	For the exponents in the range 5 to 7 digits, it is better to perform p-1 factoring, since the prime factors of a^b +/- 1 (where a and b are primes as in this case) have the form 2kb + 1. So you have to include the exponent b in your p-1 factoring. Of course you will need a powerful big number library to perform fast modular multiplications with too many digits.