20091007, 06:25  #1 
Oct 2009
4_{10} Posts 
Best approach for 130 digits?
As part of my research for my Masters thesis, I've computed and factored discriminants of weight2 Hecke algebras for all levels up to 1000 (almost). Don't worry about "what's a discriminant" or "what the heck is a Hecke algebra"; the problem I'm having is with the factorization. And, I guess, if you know what a Hecke algebra is, I'm aware of divisibility conditions that arise from discriminants of the algebras acting on new subpaces that've helped me break down the numbers quite a bit, but not quite enough.
I'm left with one 131digit, and one 133digit composite number. I did a bit of searching here and elsewhere, and I wasn't able to come up with a good answer to: "What's the best software to use for a 130 digit composite number?" I expect each to be a product of two primes of similar sizes  I've used ECM and trial division to peel out small factors, sent it to PARI and watched MPQS barf (it actually said "I'm giving up on this"), and I've watched qsieve churn on it for a week. I started msieve a couple of days ago, but it looks like it'll be almost a month before it gets enough relations  and I don't think the available 128GB of RAM is enough to handle 18 million relations (also, I have no idea how long that process will take). Am I on the right track? Have I missed anything? I can facor N+1 and N1, but neither is terribly smooth (I think each had a prime divisor on the order of 50 digits). The numbers aren't of a nice form that SNFS can handle. Does anybody know how much RAM the relation matrix is supposed to take up, and how long it'll take to echelonize? Thanks, tom 
20091007, 07:08  #2 
(loop (#_fork))
Feb 2006
Cambridge, England
13·491 Posts 
The best approach to use for a 130digit number is gnfs; it will take under a day on one CPU to find a good polynomial, about two days on four CPUs to do the sieving, and well under one day on one CPU using about a gigabyte of memory to do the linear algebra.
Download the current version of msieve from http://sourceforge.net/projects/msieve/files/, create a new directory containing a file worktodo.ini which contains the number, and do msieve v np which will find a polynomial over a period of about 24 hours, putting it in a file msieve.fb. Take a copy of msieve.fb as, say, 'poly', and change the formatting of the startsofline from Code:
N xxx SKEW yyy R0 zzz R1 qqq A0 aaa A1 bbb ... Code:
n: xxx skew: yyy Y0: zzz Y1: qqq c0: aaa c1: bbb ... Code:
alim: 8000000 rlim: 8000000 lpbr: 28 lpba: 28 mfbr: 56 mfba: 56 alambda: 2.6 rlambda: 2.6 and run gnfslasieve4I14e a poly f 4000000 c 1000000 gnfslasieve4I14e a poly f 5000000 c 1000000 gnfslasieve4I14e a poly f 6000000 c 1000000 gnfslasieve4I14e a poly f 7000000 c 1000000 on four CPUs in parallel; each of those will take about a day Then Code:
head n 1 msieve.fb > msieve.dat cat *lasieve* >> msieve.dat msieve v nc Ask again if you have any more questions; you should have results by the start of next week. Last fiddled with by fivemack on 20091007 at 07:08 
20091007, 16:33  #3 
Jun 2003
Ottawa, Canada
3×17×23 Posts 
You can also use this guide to help you out:
http://gilchrist.ca/jeff/factoring/n...ers_guide.html 
20091007, 17:46  #4  
Oct 2004
Austria
2×17×73 Posts 
Quote:
If you don't specify the output file name (e.g. gnfslasieve4I14e a poly f 4000000 c 1000000 o c132_4M.out) (which I normally do), what will the output file be named? fivemack: poly.lasieve0.40000005000000 Last fiddled with by fivemack on 20091007 at 22:15 Reason: inline answer 

20091016, 05:15  #5 
Oct 2009
100_{2} Posts 
Fivemack, (and Jeff)
Thank you! The binaries you linked to don't work on this hardware, for some reason, but I shouldn't have too much trouble building them myself. Update halfway through writing this post (a few hours later): Either my architecture doesn't seem to be very wellsupported by either ggnfs of msieve, or my gcc is screwy. I'll try this on a different box and report back. tom Last fiddled with by boothby on 20091016 at 05:55 
20091016, 06:09  #6  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
16EE_{16} Posts 
Quote:


20091016, 16:27  #7 
Oct 2009
2^{2} Posts 
It's a Sun box, but I don't think that should matter. Things that probably matter:
OS: Ubuntu 8.04.3 LTS /proc/version: Code:
Linux version 2.6.2423server (buildd@crested) (gcc version 4.2.4 (Ubuntu 4.2.41ubuntu3)) #1 SMP Wed Apr 1 22:14:30 UTC 2009 Code:
...*snip*... processor : 23 vendor_id : GenuineIntel cpu family : 6 model : 29 model name : Intel(R) Xeon(R) CPU X7460 @ 2.66GHz stepping : 1 cpu MHz : 2666.762 cache size : 16384 KB physical id : 3 siblings : 6 core id : 5 cpu cores : 6 fpu : yes fpu_exception : yes cpuid level : 11 wp : yes flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx lm constant_tsc arch_perfmon pebs bts rep_good pni monitor ds_cpl vmx est tm2 ssse3 cx16 xtpr dca sse4_1 lahf_lm bogomips : 5333.64 clflush size : 64 cache_alignment : 64 address sizes : 40 bits physical, 48 bits virtual power management: Last fiddled with by boothby on 20091016 at 16:28 
20091016, 16:50  #8 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
16EE_{16} Posts 
i think that you have 32bit linux not 64bit linux that the binaries were compiled for
does anyone have any 32bit linux binaries? if no one posts by saturday i will try and compile some 32bit binaries in a virtual machine for you for compiling you will need to install "buildessentials" using aptget or similar hopefully it should then work Last fiddled with by henryzz on 20091016 at 17:20 
20091016, 17:09  #9 
Oct 2009
100_{2} Posts 
Henryzz, uname m reports "x86_64"

20091016, 17:22  #10 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
13356_{8} Posts 

20091016, 17:24  #11 
(loop (#_fork))
Feb 2006
Cambridge, England
6383_{10} Posts 
I am using those very binaries on an ubuntu8.04 machine at home, so I'm surprised they don't work for you: what's the exact error message?

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Best approach for P1?  Mark Rose  PrimeNet  6  20170523 23:58 
Unorthodox approach to primes  Erkan  PrimeNet  7  20170110 03:34 
a backwards approach to Mersenne testing  MiniGeek  Information & Answers  14  20101114 16:16 
An Analytic Approach to Subexponential Factoring  akruppa  Math  2  20091211 18:05 
Factoring with the birthday problem approach  ThiloHarich  Factoring  0  20090818 16:48 