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

2016-06-17, 01:49   #23
LaurV
Romulan Interpreter

Jun 2011
Thailand

263016 Posts

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

2016-06-17, 02:29   #24
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

22·53·7 Posts

Quote:
 Originally Posted by LaurV 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 I already complained to you few times
I don't recall you ever mentioning this before...

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

2016-06-17, 02:53   #25
axn

Jun 2003

23×643 Posts

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

2016-06-17, 03:03   #26
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

22×53×7 Posts

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

2016-06-17, 10:29   #27
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts

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

2016-06-17, 10:39   #28
LaurV
Romulan Interpreter

Jun 2011
Thailand

24·13·47 Posts

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

2016-06-17, 10:54   #29
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

838410 Posts

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

 2016-06-17, 11:11 #30 LaurV Romulan Interpreter     Jun 2011 Thailand 230608 Posts 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
2016-06-17, 13:35   #31
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

22×53×7 Posts

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

2016-06-17, 16:41   #32
LaurV
Romulan Interpreter

Jun 2011
Thailand

24·13·47 Posts

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

 2016-06-18, 19:33 #33 James Heinrich     "James Heinrich" May 2004 ex-Northern Ontario 66548 Posts 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?

 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 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