20080407, 15:48  #1 
May 2003
7·13·17 Posts 
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^(p1)1. Sometimes, very rarely, p^2 divides a^(p1)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, ZetaFlux 
20080407, 19:18  #2 
May 2003
11000001011_{2} Posts 
I was trying to get GMPECM 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 gmp4.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? 
20080407, 20:43  #3  
"Mark"
Apr 2003
Between here and the
2·3^{2}·17·19 Posts 
Quote:


20080407, 21:34  #4 
May 2003
7·13·17 Posts 
I clicked all of the options.

20080407, 22:45  #5 
(loop (#_fork))
Feb 2006
Cambridge, England
14316_{8} Posts 
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.

20080407, 23:47  #6 
"Ben"
Feb 2007
5×653 Posts 
I ran all number < 1000 digits to P1 B1=1e8, no factors. I'm now running all > 1000 but < 10000 to B1=1e7.

20080408, 15:17  #7 
"Ben"
Feb 2007
5·653 Posts 
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. 
20080408, 16:18  #8  
Nov 2003
2×3×11×113 Posts 
Quote:
Please explain further. Whether a^(p1) = 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? 

20080408, 18:33  #9  
May 2003
11000001011_{2} Posts 
Quote:
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^{p1}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 squarefree part of 2^{n}1 is. Last fiddled with by ZetaFlux on 20080408 at 18:34 

20080408, 21:20  #10 
"Ben"
Feb 2007
5·653 Posts 

20080409, 03:35  #11 
May 2003
1547_{10} Posts 
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? 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Brent tables reservations  chris2be8  Factoring  446  20200429 17:08 
Vanishing factors  Batalov  Puzzles  8  20141111 16:20 
BrentMontgomeryte Riele numbers  FactorEyes  Factoring  23  20080222 00:36 
brent suyama extension in P1  bsquared  Factoring  9  20070518 19:24 
Brent's p1  How to deal with memory problems?  jhillenb  Factoring  4  20050111 23:50 