mersenneforum.org  

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

Reply
 
Thread Tools
Old 2016-06-17, 01:49   #23
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

263016 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
Or I can generate a simpler list of exponent,factor if that suffices for your purpose, just let me know what you want.
Or you just can generate a list of factors, and pack it. It will save a lot of transfer time.

I know this is only tangent connected, but I already complained to you few times, mersenne.ca will tell me every time I search for a factor which is not in the data base, that the factor is not in the data base. It would be very easy and fast to check if that is a valid factor, and in case it is, add it to the data base together with the exponent that results from that calculus.

Usually I don't add factors to mersenne.ca, i.e. I report them to PrimeNet and let mersenne.ca deal with it. However I look to mersenne.ca quite often to see properties of the factors (like their smoothness of k, size in bits, etc) - those reports look much better there than I could see using pari (like "#binary(factor)", etc).

Therefore it would be very useful if, when somebody search for a factor and you can not find it in the db, you then run something like
Code:
getpfp(n)=
{
    if(!isprime(n),return(0));
    my(c);
    c=divisors(n-1);
    for(i=1,#c,
        if(c[i]<1000000000 && Mod(2,n)^c[i]==1, return(c[i]))
    );
    return(0);
}
and if that returns a prime, then add the pair to the database.
LaurV is offline   Reply With Quote
Old 2016-06-17, 02:29   #24
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

22·53·7 Posts
Default

Quote:
Originally Posted by LaurV View Post
Or you just can generate a list of factors, and pack it.
There is now an export option available for those who need it. PM me if you want access.

Quote:
Originally Posted by LaurV View Post
I already complained to you few times
I don't recall you ever mentioning this before...

Quote:
Originally Posted by LaurV View Post
Usually I don't add factors to mersenne.ca, i.e. I report them to PrimeNet and let mersenne.ca deal with it
Mostly because you can't add factors to mersenne.ca (except above 1000M)

Quote:
Originally Posted by LaurV View Post
mersenne.ca will tell me every time I search for a factor which is not in the data base, that the factor is not in the data base. It would be very easy and fast to check if that is a valid factor, and in case it is, add it to the data base together with the exponent that results from that calculus.
Perhaps not a bad idea, but I'm also cautious about adding a web interface to abuse my server CPU (imagine an evil spider crawling sequential numbers from 1 to infinity looking for factors, for example).
Validating a factor to a known exponent is easy and fast. Validating a known factor to (maybe) one of ~200-million potential exponents I don't think can be described as "fast". As a one-off issue when LaurV queries an unknown factor that's fine, but I'm not quite sure how to safeguard it. Suggestions?
James Heinrich is offline   Reply With Quote
Old 2016-06-17, 02:53   #25
axn
 
axn's Avatar
 
Jun 2003

23×643 Posts
Default

Quote:
Originally Posted by LaurV View Post
Code:
getpfp(n)=
{
    if(!isprime(n),return(0));
    my(c);
    c=divisors(n-1);
    for(i=1,#c,
        if(c[i]<1000000000 && Mod(2,n)^c[i]==1, return(c[i]))
    );
    return(0);
}
Is this faster than just invoking znorder( Mod(2,f) )?
axn is offline   Reply With Quote
Old 2016-06-17, 03:03   #26
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

22×53×7 Posts
Default

Quote:
Originally Posted by axn View Post
Is this faster than just invoking znorder( Mod(2,f) )?
I haven't a clue what the math is doing, but that actually does seem fast, at least tested locally. If that's how fast it is then I can look into adding it as requested.
James Heinrich is offline   Reply With Quote
Old 2016-06-17, 10:29   #27
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts
Default

Quote:
Originally Posted by axn View Post
Is this faster than just invoking znorder( Mod(2,f) )?
I wouldn't think faster except LaurV's code allows the testing of all possible p values that the factor could be a divisor of. if factors q-1 and gets the factorization of 2*k*p into primes back for all p values it could possibly be a candidate factor of. I could think of other optimizations of the code like eliminating p if the remaining factorization isn't of the proper modular class etc.
science_man_88 is offline   Reply With Quote
Old 2016-06-17, 10:39   #28
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

24·13·47 Posts
Default

Quote:
Originally Posted by axn View Post
Is this faster than just invoking znorder( Mod(2,f) )?
If you ignore the two primality tests (one for factor, one for result) and the limit check (which would be 2^32 for James, not 1G as in my example) and consider the argument always prime, then yes, my routine is faster. The limit will also avoid testing for larger divisors, gaining more time either. They are done about the same internally; znorder needs to know the divisors list (it gets slower for a non-prime, where my routine without isprime() will fail, returning a wrong result). Otherwise we would have a very fast way to factor numbers by invoking znorder so.

However, faster or not, my piece of code give James an insight if he wants a perl or php implementation (to which I know he is very good), versus znorder which he may not know what is it or how to php it.

The isprime() test is not included in my initial routine (but the <1G test is) and I added it "on spot" when I did the paste, because I assumed someone can try reporting factors which are not prime. The name itself says "get the p from a prime q" where q is a (known) factor of (an unknown) m=2^p-1. (you may recall that I keep this notation in all my posts). This as opposite of the general "getp()" which will accept a non-prime argument too, but is slower (same speed as znorder).

edit: re SM's post: that is bull

edit 2: re "I don't recall you ever mentioning this before...", it is on the posts where I was talking about "factoring by k". This is what is doing, take a k, compute 2kp+1, get its order, if prime, we found a factor. There I mentioned about searching for previously unknown factors on mersenne.ca (by searching I mean I press the search button and type my new-found factor, the site should do an evaluation and give me the p, instead of telling me "factor not found")

Last fiddled with by LaurV on 2016-06-17 at 10:51
LaurV is offline   Reply With Quote
Old 2016-06-17, 10:54   #29
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

Quote:
Originally Posted by LaurV View Post
edit: re SM's post: that is bull
well that's what your code allows if you tested n to see if it's not 3 or 5 mod 8 or some other modular classes you could speed it up even more potentially, factoring n-1 is going to give you 2*k*p 's factorization extract a new p from the possibility list and it allows you to test divisibility for all of them. I'm wondering what you think it bull ?

Last fiddled with by science_man_88 on 2016-06-17 at 10:57
science_man_88 is offline   Reply With Quote
Old 2016-06-17, 11:11   #30
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

230608 Posts
Default

First because "LaurV's code allows the testing of all possible p values that the factor could be a divisor of" is not needed, two mersenne with prime exponents can't share a factor, so you stop at the first p. Second, that is what znorder does too, it factors q-1. About optimizations, we were not discussing finding factors, this piece of code and other even more optimized I posted in the past here:
Code:
/* trial factoring by k, specify a starting point and the outfput file */
ratf(q=2,fis="mf_by_k.out")=
{
    while(1,
        until(q%8==1 || q%8==7,q=nextprime(q+1));
        c=factorint(q-1)[,1]~;
        for(i=1,#c,
            if(c[i]<1000000000 && Mod(2,q)^c[i]==1, print(q" divides M"c[i]); write(fis,q","c[i]))
        )
    );
}
edit: this doesn't need the full list of divisors, but yet, the most time is not spent enumerating the primes and their modular class, but factoring q-1. Anyhow, this is another discussion, not related to the (current) title of the subforum

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

22×53×7 Posts
Default

Quote:
Originally Posted by LaurV View Post
it would be very useful if, when somebody search for a factor and you can not find it in the db ... add the pair to the database.
And since you were kind enough to provide the code, it now does just that.
James Heinrich is offline   Reply With Quote
Old 2016-06-17, 16:41   #32
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

24·13·47 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
And since you were kind enough to provide the code, it now does just that.
You are on the way to rival Scott, who fixes the Misfit bugs few minutes before we report them!
Good job, thanks a lot. I go to bed now (23:40 here) and tomorrow is my working Saturday (here we work alternating Sat's)
LaurV is offline   Reply With Quote
Old 2016-06-18, 19:33   #33
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

66548 Posts
Default

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?
James Heinrich 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 07:11.


Sun Oct 17 07:11:13 UTC 2021 up 86 days, 1:40, 0 users, load averages: 1.43, 1.63, 1.42

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.