mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2006-01-08, 01:36   #1
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

7×13×17 Posts
Default 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.
Zeta-Flux is offline   Reply With Quote
Old 2006-01-08, 01:47   #2
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

53A16 Posts
Default

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.
alpertron is offline   Reply With Quote
Old 2006-01-08, 02:26   #3
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

7·13·17 Posts
Default

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.
Zeta-Flux is offline   Reply With Quote
Old 2006-01-08, 03:07   #4
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23×5×59 Posts
Default

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
wblipp is offline   Reply With Quote
Old 2006-01-08, 03:53   #5
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

7·13·17 Posts
Default

Right. It gives a few values, but not very many.

Oh well. Maybe I can work around the problem.
Zeta-Flux is offline   Reply With Quote
Old 2006-01-08, 04:18   #6
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23×5×59 Posts
Default

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
wblipp is offline   Reply With Quote
Old 2006-01-08, 05:23   #7
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

7×13×17 Posts
Default

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!
Zeta-Flux is offline   Reply With Quote
Old 2006-01-11, 02:14   #8
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

7×13×17 Posts
Default

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
Zeta-Flux is offline   Reply With Quote
Old 2006-01-11, 03:05   #9
PBMcL
 
PBMcL's Avatar
 
Jan 2005

2·31 Posts
Default

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
PBMcL is offline   Reply With Quote
Old 2006-01-11, 03:18   #10
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

7·13·17 Posts
Default

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!
Zeta-Flux is offline   Reply With Quote
Old 2006-01-11, 03:36   #11
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23·5·59 Posts
Default

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
wblipp is offline   Reply With Quote
Reply

Thread Tools


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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.