Noob Question: What to use

[Dubslow]

Originally Posted by xilman

In which case GMP-ECM isn't very good. It returned

Step 2 took 844ms
********** Factor found in step 2: 40187932388829914099
Found composite factor of 20 digits: 40187932388829914099
Composite cofactor 3022796762436865758652479689958046977795867564387867433730923774249775659151058260449786348808439252499670414861993921076650681 has 127 digits

at one point during my computations, the final results of which are posted above.

To be equally pedantic, I would say then that GMP-ECM does not claim to be a general purpose factoring library, like yafu does. (Rather, it only promises to run ECM on a number, which it did.)

[bozocv]

I was wrong. The offset was good.

[Batalov]

Originally Posted by bozocv

I started it like this:

msieve -v -e 0x392D649F152B84CCE79DD50B63DA0BDDEC57A5A3DF1D2327730A14
FCC1331F7590033D7D9358EC13DA510B3972F520069C62C5E6E438912DB8192207474C35B6

The bytes (or words, or DWords) may be in the wrong endian - because if this is the key then it is an awfully bad key.

[jasonp]

Originally Posted by Dubslow

Wait, were you trying to use the MPQS implementation included in Msieve? That certainly won't work for a 512 bit number. Seriously, read up the links posted here about NFS and how to do it.

Even in 2015, because Msieve doesn't have a lattice sieve it will not attempt to use the number field sieve unless you explicitly tell it to. So that leaves MPQS, even when it is inappropriate.

[LaurV]

Originally Posted by Batalov

The bytes (or words, or DWords) may be in the wrong endian - because if this is the key then it is an awfully bad key.

I was thinking exactly to that, after I found out the number is even (see my post above) and after I saw the factorization from Paul: that is an awful key to use, I think the bytes are swapped by endianeness, or even completely upside-down (a library will store the "digits" of the number in reverse order, think about when you add long numbers, you start from the right, to do the carry). So, playing with pari, there could only be one of these 8 numbers to be factored. Few are even, one lefts a C133 (which I didn't bother to split), one gives a P144, and the others are easy ECM split (not brilliant numbers, but many small factors). There is none which can be used as a "key" for encryption (unless you do xor encryption, but in that case you don't need to factor it )

gp > n=0; forstep(i=1,64,4,n<<=32; n+=v[i+3]<<24; n+=v[i+2]<<16; n+=v[i+1]<<8; n+=v[i]); n
% = 8348000540764041906162024471..........100321162857531765754300548662680552820195655821904967
gp > write("n.num",n)
gp > n=0; forstep(i=1,64,4,n<<=32; n+=v[i+3]<<16; n+=v[i+2]<<24; n+=v[i+1]<<0; n+=v[i]<<8); n
% = 5269999986452698769570894462..........8995846355841282421956137217822060457144252334753612
gp > write("n.num",n)
gp > n=0; forstep(i=1,64,4,n<<=32; n+=v[i+3]<<8; n+=v[i+2]<<0; n+=v[i+1]<<24; n+=v[i]<<16); n
% = 2368630072079093818351229601..........45677896475111803564569370778081436400201910579081229877
gp > write("n.num",n)
gp > n=0; forstep(i=1,64,4,n<<=32; n+=v[i+3]<<0; n+=v[i+2]<<8; n+=v[i+1]<<16; n+=v[i]<<24); n
% = 299461905886505078655364178209410..........54439831397865144445106998690983380373721989264822
gp > write("n.num",n)
gp > n=0; forstep(i=64,1,-4,n<<=32; n+=v[i-3]<<0; n+=v[i-2]<<8; n+=v[i-1]<<16; n+=v[i]<<24); n
% = 95430175150531477728509730384..........700070449718694923039478196726934963045982929196166457
gp > write("n.num",n)
gp > n=0; forstep(i=64,1,-4,n<<=32; n+=v[i-3]<<8; n+=v[i-2]<<0; n+=v[i-1]<<24; n+=v[i]<<16); n
% = 2813127032230262210684515140735..........27190378971179212163358415875341722569447272009906477
gp > write("n.num",n)
gp > n=0; forstep(i=64,1,-4,n<<=32; n+=v[i-3]<<16; n+=v[i-2]<<24; n+=v[i-1]<<0; n+=v[i]<<8); n
% = 3995114264299001392062608683531468513..........15882921975622819213559602826890512979606478692
gp > write("n.num",n)
gp > n=0; forstep(i=64,1,-4,n<<=32; n+=v[i-3]<<24; n+=v[i-2]<<16; n+=v[i-1]<<8; n+=v[i]<<0); n
% = 373416326224504463835632842767039..........327252754754043415672821300321272677077282624201887
gp > write("n.num",n)

Then: "yafu factor(@) -batchfile n.num"
(one already full factored by Paul)

EDIT: GRRRRR! What's wrong with code tags? They don't crop the size anymore!

[Dubslow]

Originally Posted by LaurV

EDIT: GRRRRR! What's wrong with code tags? They don't crop the size anymore!

Good to know I'm not the only one who thought something was weird.

For the record, the C133 comes from the version considered precisely in little-endian form.

[LaurV]

Originally Posted by Dubslow

Good to know I'm not the only one who thought something was weird

Well, you used "quote" tags in post #23, which are not supposed to cut the length anyhow...
(edit: now I expect to see you posting the davieddy icon...haha)

[Xyzzy]

Originally Posted by LaurV

EDIT: GRRRRR! What's wrong with code tags? They don't crop the size anymore!

The width setting keeps reverting to "auto". We don't know why. It should be 800 pixels now.

[Dubslow]

Originally Posted by LaurV

Well, you used "quote" tags in post #23, which are not supposed to cut the length anyhow...

I was referring to this former monstrosity of a post: http://mersenneforum.org/showthread....829#post418829

Thanks Mike!
Though as you apparently know, I do very much enjoy that emote, in this case I feel it is not appropriate :)

[jux]

Originally Posted by VBCurtis

YAFU does not use the GPU-enabled version of msieve, but the GPU is only used for one part of one step; you might save half a day using the GPU yourself

I'm curious how much time the GPU version of msieve will actually save. It seems like you're saying 12 hours for a 154 digit number? The msieve README claims 50 to 100 times faster for polynomial selection, but I don't have enough experience to know how important giving more time to polynomial selection is for overall speed.

[VBCurtis]

Jux-
GPU poly select is indeed 50-100x faster for the part of poly select that uses the GPU (75% or so of the poly-select step). It's standard practice to spend 3-4% of expected factorization time on the poly select step; rather than divide this by 50, one usually lets the GPU run for only a little less time than the CPU-poly-select would have run, but one finds a poly that shortens the task by single-digit percentages compared to a typical CPU-found poly.

So, you could choose to shorten the poly select step by 12 hrs, or expect a factorization to take 12 hrs less with the GPU-poly. That said, these are averages- I've seen CPU-found polys that sieve as well as a GPU-found poly, etc etc. Rather than spend a fixed time on poly search, I stop when I have a poly comparable in score to a previous same-sized-number's poly; that's less useful a guide for someone without a list of previous jobs. Try mklasson.com/factors, "100 largest prime factors (GNFS)" for a listing of a bunch of GNFS runs and their poly scores.

An example: I did a C156 in 7 days on a hex-core i7, not counting poly search. The poly used had Murphy E-score 2.5e-12 according to msieve. I don't remember how long I spent on poly search; my CUDA rig was a laptop that didn't have much else to do, so I likely spent ~4 laptop GPU-days for the 42 core-day job.
Edit/TL;DR: A GPU might find a poly 5% better score. 5% of 42 core-days is 2 core-days, or 12 hrs on a quad core. 5% better is a guess, but that's where I got 12 hrs.