20051015, 17:31  #1 
Aug 2003
Snicker, AL
7×137 Posts 
Formula to calculate number of potential factors?
A factor of an Mp number must always be of form 2kp+1. Using other known restrictions, it is possible to narrow down the number of potential factors to about 1 value of k in 20. I.E. you don't have to trial factor by all potential factors because you can eliminate about 95% beforehand. Also, it is only necessary to trial factor up to the square root.
I'm curious if there is a simple formula that will yield the approximate number of factors that would have to be tested for any given exponent? Fusion 
20051015, 19:23  #2  
Cranksta Rap Ayatollah
Jul 2003
641 Posts 
Quote:
There exists an n such that for all Mp > n, f(Mp) = "a lot" 

20051016, 13:54  #3  
Nov 2003
1110100100100_{2} Posts 
Quote:
Your question is not well posed. You have not specified the testing methods, nor the exact conditions which specify a 'candidate'. Are you asking for the number of primes of the form 2kp+1? It is clear that the trial division process includes composites, so the number of such primes is only a lower bound on the number of candidates. As for the number of primes of the form 2kp+1, look up the Prime Number Theorem for Arithmetic Progressions, as well as Dirichlet's Theorem. 

20051016, 21:52  #4  
"William"
May 2003
New Haven
2369_{10} Posts 
Quote:
ErdosKroc could be a starting point for that approach  I don't know if the special structure of Mersenne factors could be used to refine that. I suspect that Merten's Theorem would be a much more effective way to estimate the success rate of trial factoring. 

20051017, 01:50  #5 
Sep 2002
2·331 Posts 
The number of potential factors upto the square root of Mp is
int( (int(sqrt(Mp))1)/(2p) ) = count of k factors = kcnt kcnt is the worst case, if 95% can be removed then it is kcnt/20 sometimes a factor can be found with k = 1 or some other fairly small value of k, that is why Trial Factoring finds factors while only testing q of 68 bits long for current Mersenne numbers. Example p = 67, Mp = 2^67  1 = 147573952589676412927 potential factors use the form q = 2kp + 1 k = 1, q1 = 2*1*67 + 1 = 135 kcnt = 90656731, qkcnt = 2*90656731*67 + 1 = 12148001955 the smallest (non trivial) factor is ksf = 1445580, qsf = 2*1445580*67 + 1 = 193707721 Only ~ 1.6 % of kcnt were tested, skipping none if 95% were skipped then only ~ 0.079 % of kcnt needed to be tested to find the smallest factor. Last fiddled with by dsouza123 on 20051017 at 01:55 
20051017, 03:56  #6 
"Phil"
Sep 2002
Tracktown, U.S.A.
3·373 Posts 
I moved this thread back to the regular math forum. Even though Fusion_power's original question was not well framed, I don't see that this should automatically send it to the "crank" subforum, and as a lot of interesting discussion tends to come out of these sorts of questions, I prefer to leave it in the regular math forum and see where it goes.
2^(p/2) is the approximate squareroot of Mp, and (2^(p/2))/(2p) of these numbers are of the form 2kp+1. Only half of these are = 1 or 7 mod 8, and of these numbers, the prime number theorem says that roughly 1/ln(2^(p/2)) of these candidates are prime. So there are about (2^(p/2))/(2*ln2*p^2) prime candidates, a truly huge number for large p, but as RDSilverman and Dsouza point out, we cannot even eliminate all composite candidates in practice, but must sieve to the point that we can only eliminate some percentage. The problem does not have much practical significance beyond, say, M127, since even computer power will never be able to directly test all candidates in this range. Between M127 and M761, all factors have been found by other means, but not by direct testing. It would be helpful if you could be more specific about exactly what you want to know. The approximate number of factors to test to prove a number prime? Or to have an x% chance of finding a factor? 
20051017, 12:00  #7  
Nov 2003
1110100100100_{2} Posts 
Quote:
It is ErdosKac. And yes, this theorem can be modified to specifically estimate omega(N) where N is a Mersenne number. [omega(n) is standard notation for #distinct prime divisors of n]. Although I am only a novice in sieve methods, it *seems* that a fairly straightforward application of the BrunTitschmarch theorem will simply give omega(n) = c log log n specifically for n = 2^p1 as p>oo. c is going to be a somewhat complicated expression of the form lim p > oo 1/p * (sum over p, p prime of (product over k, k < p (1  Jacobi(kn))) ) I am sure that I have the kernel of the innermost product incorrectly specified. It will also involve some "corrective" terms to require that 2kp+1 = +/1 mod 8, i.e. not just any k is allowed. It may also involve some Artin symbols (i.e. higher reciprocity) 

20051017, 19:04  #8  
∂^{2}ω=0
Sep 2002
República de California
2D8D_{16} Posts 
Quote:


20051017, 19:09  #9 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
I didn't move it, either. I think I saw the thread shortly after inception, and it was in Miscellaneous from the start.
Alex 
20051017, 21:10  #10 
"Phil"
Sep 2002
Tracktown, U.S.A.
3·373 Posts 
My apologies; I should have checked the moderator log before moving it. I still don't think it belongs there (yet), so I'll leave it where it is. Actually, this would be a nice idea if we could get people like Bearnol to voluntarily post in the Miscellaneous thread to begin with rather than cause the moderators to step in!

20051017, 21:55  #11 
Aug 2003
Snicker, AL
7·137 Posts 
Thank you all for some very informative answers. dsouza123 came especially close to where I was trying to go.
I was indeed trying to determine what percentage of potential factors could realistically be tested given that Prime95 sets a limit of 68 bits. Translated into realistic terms, Prime95 can't possibly test more than a very small percentage of the potential factors. Its successful at doing this because the probability of a small factor is orders of magnitude greater than the probability of finding a large factor i.e. a factor near the square root. The result of the above is that as p increases, the number of potential factors with form 2kp+1 increases but the percentage that can be tested using trial factoring decreases. No rocket science in this, just pointing out what is obvious. Eventually, the numbers will be large enough that trial factoring will not be a realistic option though it will always be capable of finding some percentage of factors. I've gone over the various methods of factoring for about a year now. I'm slightly familiar with the approach of several factoring methods including p1, p+1, elliptic curve, and of course trial division. Trial division is only practical for small values of k. The other three methods are generally more effective at finding factors that are further away from the square root and generally representing lower values of k though much greater than is possible with trial factoring. So I would ask: Who has done significant work on algorithms that can find factors near the square root. If you get right down to it, ECM is not at all efficient. I would like to see some well thought out and relevant discussion of the topic. Please leave this in the miscellaneous math forum. I hope this thread will be usable by a broad group of readers. I had anticipated only one or two answers so thought it would not be as interesting as this seems to have become. Fusion  who is starting to think of numbers in terms of spirals and strange french curves. Last fiddled with by Fusion_power on 20051017 at 21:58 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
How to calculate a fair tax, by wonky formula.  Uncwilly  Soap Box  41  20130423 14:20 
Number of distinct prime factors of a Double Mersenne number  aketilander  Operazione Doppi Mersennes  1  20121109 21:16 
calculate logarithm base 2 of number very close 1  thehealer  Other Mathematical Topics  9  20110420 14:02 
Fastest possible algorithm to calculate the square root of a 10,000,000 digit number  Fusion_power  Math  19  20071102 21:37 
prime number formula  tjmag  Miscellaneous Math  6  20031211 20:21 