mersenneforum.org > Data Small inconsistencies between mersenne.org and mersenne.ca factor databases
 Register FAQ Search Today's Posts Mark Forums Read

2016-06-18, 21:39   #34
wombatman
I moo ablest echo power!

May 2013

110111110002 Posts

Quote:
 Originally Posted by James Heinrich 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.

2016-06-19, 09:43   #35
axn

Jun 2003

10100000111112 Posts

Quote:
 Originally Posted by James Heinrich 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!

2016-06-19, 11:07   #36
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

9,787 Posts

Quote:
 Originally Posted by wombatman 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.

2016-06-19, 11:27   #37
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

24·3·73 Posts

Quote:
 Originally Posted by axn 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.

2016-06-19, 11:30   #38
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

263B16 Posts

Quote:
 Originally Posted by axn 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

2016-06-19, 13:04   #39
axn

Jun 2003

3·17·101 Posts

Quote:
 Originally Posted by LaurV 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 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)

2016-06-19, 13:07   #40
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

9,787 Posts

Quote:
 Originally Posted by axn 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

2016-06-19, 13:40   #41
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

24×3×73 Posts

Quote:
 Originally Posted by axn k-values of composite factors are meaningless numbers
Thanks. I've taken out the k-values and P-1 bounds for composite factors.

2016-06-19, 14:29   #42
axn

Jun 2003

3·17·101 Posts

Quote:
 Originally Posted by James Heinrich 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.

2016-06-19, 19:04   #43
GP2

Sep 2003

5·11·47 Posts

Quote:
 Originally Posted by axn 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

2016-06-19, 19:18   #44
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by GP2 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

 Similar Threads Thread Thread Starter Forum Replies Last Post Erich PrimeNet 16 2012-09-29 23:08 James Heinrich Math 57 2011-09-12 14:16 kurtulmehtap Math 21 2010-11-08 18:21 bitblit Math 3 2009-05-02 01:20 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