 mersenneforum.org Formula to calculate number of potential factors?
 Register FAQ Search Today's Posts Mark Forums Read  2005-10-15, 17:31 #1 Fusion_power   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   2005-10-15, 19:23   #2
Orgasmic Troll
Cranksta Rap Ayatollah

Jul 2003

641 Posts Quote:
 Originally Posted by Fusion_power 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
let f(x) be the above named function.

There exists an n such that for all Mp > n, f(Mp) = "a lot"   2005-10-16, 13:54   #3
R.D. Silverman

Nov 2003

11101001001002 Posts Quote:
 Originally Posted by Fusion_power 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

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.   2005-10-16, 21:52   #4
wblipp

"William"
May 2003
New Haven

236910 Posts Quote:
 Originally Posted by R.D. Silverman Your question is not well posed.
I agree the question was poorly posed. I thought he was asking about the distribution of the number of distinct prime divisors for Mp. I thought he was trying to go in the direction of "x% have at least 4 distinct factors, so at least x% will be factored by trial division to Mp^(1/4) - he was probably hoping for a high value of x with 20 distinct factors.

Erdos-Kroc 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.   2005-10-17, 01:50 #5 dsouza123   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 2005-10-17 at 01:55   2005-10-17, 03:56 #6 philmoore   "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?   2005-10-17, 12:00   #7
R.D. Silverman

Nov 2003

11101001001002 Posts Quote:
 Originally Posted by wblipp I agree the question was poorly posed. I thought he was asking about the distribution of the number of distinct prime divisors for Mp. I thought he was trying to go in the direction of "x% have at least 4 distinct factors, so at least x% will be factored by trial division to Mp^(1/4) - he was probably hoping for a high value of x with 20 distinct factors. Erdos-Kroc 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.
Minor nit:

It is Erdos-Kac. 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 Brun-Titschmarch theorem will simply
give omega(n) = c log log n specifically for n = 2^p-1 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(k|n))) )

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)   2005-10-17, 19:04   #8
ewmayer
2ω=0

Sep 2002
República de California

2D8D16 Posts Quote:
 Originally Posted by philmoore 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.
I never moved it to the "miscellaneous" forum, and I didn't see a note from Alex to the effect that he had done so, either. Perhaps Fusion posted it in "Miscellaneous" to begin with.   2005-10-17, 19:09 #9 akruppa   "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   2005-10-17, 21:10 #10 philmoore   "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!   2005-10-17, 21:55 #11 Fusion_power   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 p-1, 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 2005-10-17 at 21:58   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Uncwilly Soap Box 41 2013-04-23 14:20 aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16 thehealer Other Mathematical Topics 9 2011-04-20 14:02 Fusion_power Math 19 2007-11-02 21:37 tjmag Miscellaneous Math 6 2003-12-11 20:21

All times are UTC. The time now is 05:15.

Wed Oct 27 05:15:55 UTC 2021 up 95 days, 23:44, 0 users, load averages: 0.88, 1.06, 1.07