mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2008-04-07, 15:48   #1
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

7·13·17 Posts
Default Vanishing Fermat Quotients and Brent's List

Fermat's little theorem says that if p is a prime, and gcd(a,p)=1, then p divides a^(p-1)-1. Sometimes, very rarely, p^2 divides a^(p-1)-1. My research is intricately tied to when this happens, and so William Lipp and I have been factoring numbers related to this phenomenon. See http://mersenneforum.org/showthread.php?t=5304 for some of our previous exploits.

William has put together a nice page at: http://oddperfect.org/FermatQuotients3.html

It lists all of the numbers I'm interested in factoring that overlap with Brent's extended Cunningham tables. Click on a column and it will sort the numbers according to your preference (size, ECM done, and so forth). All who are interested please feel free to contribute. Your numbers will likely show up on Brent's tables when he updates them, and will also help my project.

If you have any questions feel free to ask.

Best,
Zeta-Flux
Zeta-Flux is offline   Reply With Quote
Old 2008-04-07, 19:18   #2
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

110000010112 Posts
Default

I was trying to get GMP-ECM on my laptop, to contribute to my own project, but something seems to be going badly. I downloaded MinGW and MSYS, and they seem to be working fine. I unpacked gmp-4.2.1, but when trying to configure it I got: configure: error: could not find a working compiler, see config.log for details

Any suggestions?
Zeta-Flux is offline   Reply With Quote
Old 2008-04-07, 20:43   #3
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

2·32·17·19 Posts
Default

Quote:
Originally Posted by Zeta-Flux View Post
I was trying to get GMP-ECM on my laptop, to contribute to my own project, but something seems to be going badly. I downloaded MinGW and MSYS, and they seem to be working fine. I unpacked gmp-4.2.1, but when trying to configure it I got: configure: error: could not find a working compiler, see config.log for details

Any suggestions?
When you installed, was there an option to choose any development tools? I know in CygWin that you need to specify the gcc package before it will install it.
rogue is offline   Reply With Quote
Old 2008-04-07, 21:34   #4
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

7·13·17 Posts
Default

I clicked all of the options.
Zeta-Flux is offline   Reply With Quote
Old 2008-04-07, 22:45   #5
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

143168 Posts
Default

I have left the numbers with less than 1000 digits running 400 curves of ecm at 1e6 while I go to a conference; results on Friday morning.
fivemack is offline   Reply With Quote
Old 2008-04-07, 23:47   #6
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

5×653 Posts
Default

I ran all number < 1000 digits to P-1 B1=1e8, no factors. I'm now running all > 1000 but < 10000 to B1=1e7.
bsquared is offline   Reply With Quote
Old 2008-04-08, 15:17   #7
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

5·653 Posts
Default

Input number is (353^1201+1)/(354) (3058 digits)
Using B1=10000000, B2=880276332, polynomial x^24, x0=1708104112
Step 1 took 889710ms
Step 2 took 143770ms
********** Factor found in step 2: 1450492427081940778189
Found probable prime factor of 22 digits: 1450492427081940778189
Composite cofactor ((353^1201+1)/(354))/1450492427081940778189 has 3037 digits

6 more to test in this range... hopefully I'll have more luck!

- ben.
bsquared is offline   Reply With Quote
Old 2008-04-08, 16:18   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

2×3×11×113 Posts
Default

Quote:
Originally Posted by Zeta-Flux View Post
Fermat's little theorem says that if p is a prime, and gcd(a,p)=1, then p divides a^(p-1)-1. Sometimes, very rarely, p^2 divides a^(p-1)-1. My research is intricately tied to when this happens, and so William Lipp and I have been factoring numbers related to this phenomenon.

Please explain further. Whether a^(p-1) = 1 mod p^2 has been tested
up to 10^12. There are only 2 known solutions. Solutions are known
on heuristical reasoning to be quite sparse. How does your factoring
work tie into this? What does "related to this phenomenon" mean?
R.D. Silverman is offline   Reply With Quote
Old 2008-04-08, 18:33   #9
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

110000010112 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Please explain further. Whether a^(p-1) = 1 mod p^2 has been tested
up to 10^12. There are only 2 known solutions. Solutions are known
on heuristical reasoning to be quite sparse. How does your factoring
work tie into this? What does "related to this phenomenon" mean?
Your wish is my command.

You are correct that there are only 2 known solutions, when a=2. I'm more interested in the case when a is an odd prime, which provides a few more solutions.

The factoring work ties into my research by allowing me to eliminate lots of special cases by one ad hoc sweep, rather than dealing with each case separately. By eliminating the cases when p^2 | a^{p-1}-1 (for relatively small p) I can force the size of factors of a^{n}-1 to be relatively large.

---------

Additional information you might find interesting: One problem that has interested a few number theorists lately is to find a good lower bound on the size of the largest prime divisor of 2^{n}-1, in terms of n. The best unconditional bound to date is O(n). When n=p is a prime, I think there is an unconditional bound of size O(p*log(p)). Under the Riemann hypothesis (or perhaps it is the ABC conjecture) one gets O(n^2). These are all TERRIBLE bounds.

One question that ties into my research is whether some of these bounds could be improved if we knew how big the square-free part of 2^{n}-1 is.

Last fiddled with by Zeta-Flux on 2008-04-08 at 18:34
Zeta-Flux is offline   Reply With Quote
Old 2008-04-08, 21:20   #10
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

5·653 Posts
Default

Quote:
Originally Posted by bsquared View Post

6 more to test in this range...
no more factors to report. I'll do the rest of the numbers (those > 10000 digits) up to B1=1e6
bsquared is offline   Reply With Quote
Old 2008-04-09, 03:35   #11
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

154710 Posts
Default

I tried to use Cygwin instead of MinGW, and this time I got a different error:

checking for suitable m4... configure: error: No usable m4 in $PATH or /usr/5bin

Then I though, maybe I can just install ECM without having to configure gmp, since I had Cygwin come with gmp already. So, I tried to configure ecm, and it couldn't find gmp.

Any suggestions?
Zeta-Flux is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Brent tables reservations chris2be8 Factoring 446 2020-04-29 17:08
Vanishing factors Batalov Puzzles 8 2014-11-11 16:20
Brent-Montgomery-te Riele numbers FactorEyes Factoring 23 2008-02-22 00:36
brent suyama extension in P-1 bsquared Factoring 9 2007-05-18 19:24
Brent's p-1 - How to deal with memory problems? jhillenb Factoring 4 2005-01-11 23:50

All times are UTC. The time now is 07:27.

Wed Jul 15 07:27:36 UTC 2020 up 112 days, 5 hrs, 0 users, load averages: 1.50, 1.36, 1.25

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.