mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2005-10-15, 17:31   #1
Fusion_power
 
Fusion_power's Avatar
 
Aug 2003
Snicker, AL

7×137 Posts
Default 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
Fusion_power is offline   Reply With Quote
Old 2005-10-15, 19:23   #2
Orgasmic Troll
Cranksta Rap Ayatollah
 
Orgasmic Troll's Avatar
 
Jul 2003

641 Posts
Default

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"
Orgasmic Troll is offline   Reply With Quote
Old 2005-10-16, 13:54   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2005-10-16, 21:52   #4
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

236910 Posts
Default

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.
wblipp is offline   Reply With Quote
Old 2005-10-17, 01:50   #5
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2·331 Posts
Default

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
dsouza123 is offline   Reply With Quote
Old 2005-10-17, 03:56   #6
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

3·373 Posts
Default

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?
philmoore is offline   Reply With Quote
Old 2005-10-17, 12:00   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Question

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)
R.D. Silverman is offline   Reply With Quote
Old 2005-10-17, 19:04   #8
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

2D8D16 Posts
Default

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.
ewmayer is offline   Reply With Quote
Old 2005-10-17, 19:09   #9
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

I didn't move it, either. I think I saw the thread shortly after inception, and it was in Miscellaneous from the start.

Alex
akruppa is offline   Reply With Quote
Old 2005-10-17, 21:10   #10
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

3·373 Posts
Default

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!
philmoore is offline   Reply With Quote
Old 2005-10-17, 21:55   #11
Fusion_power
 
Fusion_power's Avatar
 
Aug 2003
Snicker, AL

7·137 Posts
Default

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
How to calculate a fair tax, by wonky formula. Uncwilly Soap Box 41 2013-04-23 14:20
Number of distinct prime factors of a Double Mersenne number aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16
calculate logarithm base 2 of number very close 1 thehealer Other Mathematical Topics 9 2011-04-20 14:02
Fastest possible algorithm to calculate the square root of a 10,000,000 digit number Fusion_power Math 19 2007-11-02 21:37
prime number formula 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.