mersenneforum.org Finding factors of cunningham-like numbers
 Register FAQ Search Today's Posts Mark Forums Read

 2006-01-08, 01:36 #1 Zeta-Flux     May 2003 7×13×17 Posts Finding factors of cunningham-like numbers I'm working on a project, and would like to find a table that lists known medium sized factors for numbers $a^{n}-1$ with $a<1000$. I found Brent's tables, but they didn't go high enough for me. For example, I need to find two factors of 13^{862}-1 that are >10^{11}. I found one by ECM, and can probably find a second one, but it would be nice to skip all that work if there is a table somewhere. Thanks.
 2006-01-08, 01:47 #2 alpertron     Aug 2002 Buenos Aires, Argentina 53A16 Posts Brent's table cover the range base < 10000, exponent < 10000, but of course most entries do not have enough ECM done. So you can make us a favor by sending to Richard Brent all factors that you find of numbers in this range. Brent's page is: http://wwwmaths.anu.edu.au/~brent/factors.html. You can find his e-mail there.
 2006-01-08, 02:26 #3 Zeta-Flux     May 2003 7·13·17 Posts Alperton, As I mentioned in my post, I had found that site, and it didn't (as far as I could find) have the needed factorizations. Further (as far as I could find) it DIDN'T cover the range you said. Rather, just pairs (a,n) for which a^n < 10^255.
2006-01-08, 03:07   #4
wblipp

"William"
May 2003
New Haven

23×5×59 Posts

Quote:
 Originally Posted by Zeta-Flux it DIDN'T cover the range you said.
You need to look lower. You want factors.gz. It covers a^n+/-1 for a and n both < 10,000. But, as Dario said, most of the larger entries are still empty. OddPerfect.org has expanded the list by about 2500 factors, mostly for a>1000 and n<100 or a<1000 and n>100.

William

 2006-01-08, 03:53 #5 Zeta-Flux     May 2003 7·13·17 Posts Right. It gives a few values, but not very many. Oh well. Maybe I can work around the problem.
2006-01-08, 04:18   #6
wblipp

"William"
May 2003
New Haven

23×5×59 Posts

Quote:
 Originally Posted by Zeta-Flux For example, I need to find two factors of 13^{862}-1 that are >10^{11}.
The primitive part of this is (13^862-1)*(13^1-1)/(13^431-1)/(13^2-1)

Putting this into Alpertron, I get

863 ^ 2 x 68099 x P469

(It hasn't finished the APRT-CLE proof as I post this, but it would be an exceptional situation if the proof fails after progressing this far)

Are you looking for factors of the algebraic factor 13^431-1, or I have I misunderstood something?

I don't have much computing power available, but I'll help look for factors of any of p^q-1 that you need (p and q odd primes) because OddPerfect.org will eventually be interested in these.

William

 2006-01-08, 05:23 #7 Zeta-Flux     May 2003 7×13×17 Posts William, Thank you. The numbers I am looking at have more to do with odd perfect numbers than you may realize. Give me a couple weeks to settle things down, and I'll send you what I'm working on. Thanks for the factorization in the meantime! That sure is a large prime!
 2006-01-11, 02:14 #8 Zeta-Flux     May 2003 7×13×17 Posts William, Here is my general question. Consider the equation $a^{p-1}\equiv 1\pmod{p^{2}}$. All solutions to this, with $p<1000$ prime, and $a<10^{11}$ prime, are given at http://www.mscs.dal.ca/~joerg/res/fq.html. Write $o_{p}(a)$ for the multiplicative order of $a \pmod{p}$. I'm wondering if it is the case that for those $a>1000$, if $a^{o_{p}(a)}-1$ is divisible by at least two primes $>10^{11}$. Also, I'm interested if anyone has searched for solutions to $3^{p-1}\equiv 1\pmod{p^{2}}$ to a higher bound than on that site. Cheers, Pace
 2006-01-11, 03:05 #9 PBMcL     Jan 2005 2·31 Posts If you still need factors of (13^431-1)/12, here's what I got: 1605907 * 56586870103 * 16002623839393 * 35910496578500372495225262919339090613 * C412 Presumably you already had the three small ones. Phil
 2006-01-11, 03:18 #10 Zeta-Flux     May 2003 7·13·17 Posts Phil, Thanks. Actually, William's factor was fine, but yours is good too. It would be nice to have the factors for the other cases, as explained in my last post. Cheers!
2006-01-11, 03:36   #11
wblipp

"William"
May 2003
New Haven

23·5·59 Posts

Quote:
 Originally Posted by Zeta-Flux Consider the equation $a^{p-1}\equiv 1\pmod{p^{2}}$. All solutions to this, with $p<1000$ prime, and $a<10^{11}$ prime, are given at http://www.mscs.dal.ca/~joerg/res/fq.html.
Pace,
Things are a bit mixed up. The site has $a<1000$ prime, and $p<10^{11}$ prime - a and p reversed from your post.

Let's take a specific example and see if I follow.

I think that

59 2777

is an example you are interested in.

The multiplicative order of 59 mod 2777 is 1388.

You want to know if 591388-1 has at least two prime factors > 1011.

Or perhaps that isn't enough - it sounds like you want to know the values of two such prime factors - not merely their existence.

Is that right?

Which ones have already been solved?

William

Last fiddled with by akruppa on 2006-09-03 at 18:02 Reason: Fixed typesetting tags

 Similar Threads Thread Thread Starter Forum Replies Last Post wpolly Factoring 26 2016-07-29 04:34 NeoGen Math 7 2007-03-13 00:04 jasong GMP-ECM 6 2006-06-30 08:51 jasong Factoring 1 2006-04-03 17:18 jasong Factoring 27 2006-03-21 02:47

All times are UTC. The time now is 08:46.

Thu Dec 3 08:46:43 UTC 2020 up 4:58, 0 users, load averages: 1.69, 1.63, 1.37