mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Data > mersenne.ca

Reply
 
Thread Tools
Old 2016-06-18, 21:39   #34
wombatman
I moo ablest echo power!
 
wombatman's Avatar
 
May 2013

110111110002 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
Any suggestions for how to fully factor moderately-large (50-150 digit) numbers? I run into these most often as k values, and the ones that are <50 digits I can factor pretty much instantly, but the large ones can take some time. Until now I've just been aborting and saying "too large" and not showing the relevant details, but I've now started collecting them in hopes of finding some kind of offline processing. I've manually tried a few of them with Dario's Java ECM tool, and some are factored within a second while others (e.g. "5272703229220007874811133810104969405477368739513286723394714036551930163895517204360421097050187418157101219550018359697836") have been crunching for more than 5 hours already. So I'd like to find some kind of offline tool that runs under Windows where I can feed it a list of presumably-composite numbers and let it chew on them and spit out the factorization. Suggestions?
YAFU. Can churn through a list of numbers, especially if they're 100 digits or less each.
wombatman is offline   Reply With Quote
Old 2016-06-19, 09:43   #35
axn
 
axn's Avatar
 
Jun 2003

10100000111112 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
I've manually tried a few of them with Dario's Java ECM tool, and some are factored within a second while others (e.g. "5272703229220007874811133810104969405477368739513286723394714036551930163895517204360421097050187418157101219550018359697836") have been crunching for more than 5 hours already.
What is the source of this number? I can't believe that someone found an actual factor of mersenne number this big!
axn is offline   Reply With Quote
Old 2016-06-19, 11:07   #36
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

9,787 Posts
Default

Quote:
Originally Posted by wombatman View Post
YAFU. Can churn through a list of numbers, especially if they're 100 digits or less each.
+1.
On your particular C124 example, Yafu gets out small composites and a PRP9, leaving a C109 in few seconds, which survives the 0.33 ECM, therefore the time to factor it will be the time to run GNFS on a C109. In 4-cores, 3.8GHz machine where I tried it, ECM is about 24 minutes, poly search about 12-13 minutes, sieving about 90 minutes to 2 hours depending of how a good a poly you got, then the LA and square root up to a hour depending on your luck with the square root. You can't make it faster, with this hardware.
LaurV is offline   Reply With Quote
Old 2016-06-19, 11:27   #37
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

24·3·73 Posts
Default

Quote:
Originally Posted by axn View Post
What is the source of this number? I can't believe that someone found an actual factor of mersenne number this big!
I don't remember which exponent it's from offhand. These numbers will either k-values of factors, which could either be factors as found (either prime or composite factors), but mersenne.ca also displays k-values of all composite factors of all known prime factors as well, which is probably what my example is.
James Heinrich is offline   Reply With Quote
Old 2016-06-19, 11:30   #38
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

263B16 Posts
Default

Quote:
Originally Posted by axn View Post
What is the source of this number? I can't believe that someone found an actual factor of mersenne number this big!
Isn't a factor of M1171?

(edit: here is how I found it:
Code:
gp > p=2; x=0; until(x==p, a=0; until(a,[p=nextprime(p+1), a=isprime(b=2*k*p+1)]); print(p": "x=getp(b,p+1)))
331: 332
379: 380
1171: 1171
gp > ##
  ***   last result computed in 1,382 ms.
gp >
edit 2: getp() is a slower version of getpfp which does not requires anything to be prime, and does not factor the arguments, working by blind additions and shifts:

Code:
/*get smallest p such as n divides 2^p-1*/\
/*print(k++", "ggg=2*k*(1<<31-1)+1", "gggg=getp(ggg,10^10)", "ggg%gggg", "isprime(ggg))*/
getp(n,limt)=
{
    if(n<3 || n%2==0, print("Only odd positive numbers!");return);
    
    rg=1;
    sm=0;
    until(rg==1 || sm>=limt, 
        rg+=n;
        while(rg%2==0 && sm<limt, 
            rg>>=1;
            sm++;
            if(bitand(sm,1048575)==0, printf("...%d...%c",sm,13));
        )
    );
    return(sm);
}
)

edit 3: just realized I didn't give the factors, in case your tool still crunching:

P65 = 79001680667399413021755551127728881024073264821649477463074552981
P44 = 80372772078870023311028629526527251806209541
NFS elapsed time = 8766.1264 seconds.

Last fiddled with by LaurV on 2016-06-19 at 11:44
LaurV is offline   Reply With Quote
Old 2016-06-19, 13:04   #39
axn
 
axn's Avatar
 
Jun 2003

3·17·101 Posts
Default

Quote:
Originally Posted by LaurV View Post
Isn't a factor of M1171?
Indeed, I should've known that this would've come out of a big NFS factor of a small mersenne.

Quote:
Originally Posted by James Heinrich View Post
I don't remember which exponent it's from offhand. These numbers will either k-values of factors, which could either be factors as found (either prime or composite factors), but mersenne.ca also displays k-values of all composite factors of all known prime factors as well, which is probably what my example is.
k-values of composite factors are meaningless numbers. And it is a good thing you're not showing them on the site (eg:- http://www.mersenne.ca/exponent/1009)
axn is offline   Reply With Quote
Old 2016-06-19, 13:07   #40
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

9,787 Posts
Default

Quote:
Originally Posted by axn View Post
And it is a good thing you're not showing them on the site (eg:- http://www.mersenne.ca/exponent/1009)
He does (in tooltips)
Which is ok, even if they are meaningless.
(edit: the "too big" in this case is a very good thing too, they don't need to waste cpu time for factoring)

Last fiddled with by LaurV on 2016-06-19 at 13:08
LaurV is offline   Reply With Quote
Old 2016-06-19, 13:40   #41
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

24×3×73 Posts
Default

Quote:
Originally Posted by axn View Post
k-values of composite factors are meaningless numbers
Thanks. I've taken out the k-values and P-1 bounds for composite factors.
James Heinrich is offline   Reply With Quote
Old 2016-06-19, 14:29   #42
axn
 
axn's Avatar
 
Jun 2003

3·17·101 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
Thanks. I've taken out the k-values and P-1 bounds for composite factors.
The P-1 bounds for composite factors is derived from the P-1 bounds of the individual prime factors that make up the composite: {max(B1), max(B2)}. AFAICT the values you were displaying was according to this logic, so they were correct (if a bit useless). Obviously, this doesn't involve factoring the composite factor's k -- that part is very much useless.

PS:- I am also unsure of the usefulness of the TF GHz days displayed against composite factors, because it doesn't correspond to the actual way in which TF would discover those factors.
axn is offline   Reply With Quote
Old 2016-06-19, 19:04   #43
GP2
 
GP2's Avatar
 
Sep 2003

5·11·47 Posts
Default

Quote:
Originally Posted by axn View Post
k-values of composite factors are meaningless numbers.
It's redundant to store both the factor and the k-value in the database, since one is so easily derived from the other, via f = 2kp + 1.

But arguably it's k that we should store and keep track of, and not the full factor.

The factor itself is relatively uninteresting, in the same way that the actual decimal expansion of a Mersenne number is uninteresting, as opposed to the exponent.

At the moment 28,869,906 factors are known, for p between 0M and 1000M. Since p is on average a bit less than 9 decimal digits, that means just under 259MB (247 MiB) of wasted storage, since the factors are stored as strings.

Since the distribution of k skews overwhelmingly toward small values, the savings would be even greater percentage-wise. In the vast majority of cases, we could replace a 9 or 10 digit factor with a one or two digit k value.


On the other hand, one advantage of storing the factor itself is that mathematically any given number can be a factor of at most one Mersenne number with a prime exponent (i.e., the exponents that we care about). So you can make the factor field the primary index of your database table. But presumably it would be just as efficient to use (exponent, k) as a unique index.

Last fiddled with by GP2 on 2016-06-19 at 19:20
GP2 is offline   Reply With Quote
Old 2016-06-19, 19:18   #44
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by GP2 View Post
On the other hand, one advantage of storing the factor itself is that mathematically any given number can be a factor of at most one Mersenne number with a prime exponent (i.e., the exponents that we care about). So you can make the factor field the primary index of your database table.
one other positive is that to know which k belong with which p if that is wanted it's to store both k and p separately it takes log_2(k)+log_2(p) bits at very least where as storing the factor alone takes about the same anyways so other than having to figure out the p costing a little more it allows all the functionality and potentially more to store the factor and p values.

Last fiddled with by science_man_88 on 2016-06-19 at 19:19
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
ECM on small Mersenne Numbers Erich PrimeNet 16 2012-09-29 23:08
Can two Mersenne numbers share a factor? James Heinrich Math 57 2011-09-12 14:16
mersenne prime as a factor of another number kurtulmehtap Math 21 2010-11-08 18:21
Mersenne factor bitblit Math 3 2009-05-02 01:20
Fast calculations modulo small mersenne primes like M61 Dresdenboy Programming 10 2004-02-29 17:27

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


Mon Oct 25 05:41:15 UTC 2021 up 94 days, 10 mins, 0 users, load averages: 1.24, 0.98, 0.99

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.