mersenneforum.org Best approach for 130 digits?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2009-10-07, 06:25 #1 boothby   Oct 2009 410 Posts Best approach for 130 digits? As part of my research for my Masters thesis, I've computed and factored discriminants of weight-2 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 131-digit, and one 133-digit 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 N-1, 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
 2009-10-07, 07:08 #2 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 13·491 Posts The best approach to use for a 130-digit 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 starts-of-line from Code: N xxx SKEW yyy R0 zzz R1 qqq A0 aaa A1 bbb ... to Code: n: xxx skew: yyy Y0: zzz Y1: qqq c0: aaa c1: bbb ... and add at the end Code: alim: 8000000 rlim: 8000000 lpbr: 28 lpba: 28 mfbr: 56 mfba: 56 alambda: 2.6 rlambda: 2.6 Get gnfs-lasieve4I14e (64-bit Linux executable) from http://www.chiark.greenend.org.uk/~t...updated16e.zip and run gnfs-lasieve4I14e -a poly -f 4000000 -c 1000000 gnfs-lasieve4I14e -a poly -f 5000000 -c 1000000 gnfs-lasieve4I14e -a poly -f 6000000 -c 1000000 gnfs-lasieve4I14e -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 will finish the job. Ask again if you have any more questions; you should have results by the start of next week. Last fiddled with by fivemack on 2009-10-07 at 07:08
 2009-10-07, 16:33 #3 Jeff Gilchrist     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
2009-10-07, 17:46   #4
Andi47

Oct 2004
Austria

2×17×73 Posts

Quote:
 Originally Posted by fivemack and run gnfs-lasieve4I14e -a poly -f 4000000 -c 1000000 gnfs-lasieve4I14e -a poly -f 5000000 -c 1000000 gnfs-lasieve4I14e -a poly -f 6000000 -c 1000000 gnfs-lasieve4I14e -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
Just a question, as I normally specify the output-file's name:

If you don't specify the output file name (e.g. gnfs-lasieve4I14e -a poly -f 4000000 -c 1000000 -o c132_4M.out) (which I normally do), what will the output file be named?

fivemack: poly.lasieve-0.4000000-5000000

Last fiddled with by fivemack on 2009-10-07 at 22:15 Reason: in-line answer

 2009-10-16, 05:15 #5 boothby   Oct 2009 1002 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 half-way through writing this post (a few hours later): Either my architecture doesn't seem to be very well-supported 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 2009-10-16 at 05:55
2009-10-16, 06:09   #6
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

16EE16 Posts

Quote:
 Originally Posted by boothby 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 half-way through writing this post (a few hours later): Either my architecture doesn't seem to be very well-supported by either ggnfs of msieve, or my gcc is screwy. I'll try this on a different box and report back. --tom
what is the hardware and operating system?

 2009-10-16, 16:27 #7 boothby   Oct 2009 22 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.24-23-server (buildd@crested) (gcc version 4.2.4 (Ubuntu 4.2.4-1ubuntu3)) #1 SMP Wed Apr 1 22:14:30 UTC 2009 /proc/cpuinfo 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 2009-10-16 at 16:28
 2009-10-16, 16:50 #8 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 16EE16 Posts i think that you have 32-bit linux not 64-bit linux that the binaries were compiled for does anyone have any 32-bit linux binaries? if no one posts by saturday i will try and compile some 32-bit binaries in a virtual machine for you for compiling you will need to install "build-essentials" using apt-get or similar hopefully it should then work Last fiddled with by henryzz on 2009-10-16 at 17:20
 2009-10-16, 17:09 #9 boothby   Oct 2009 1002 Posts Henryzz, uname -m reports "x86_64"
2009-10-16, 17:22   #10
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

133568 Posts

Quote:
 Originally Posted by boothby Henryzz, uname -m reports "x86_64"
they should work then
what is the error message?

 2009-10-16, 17:24 #11 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 638310 Posts I am using those very binaries on an ubuntu-8.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 Mark Rose PrimeNet 6 2017-05-23 23:58 Erkan PrimeNet 7 2017-01-10 03:34 Mini-Geek Information & Answers 14 2010-11-14 16:16 akruppa Math 2 2009-12-11 18:05 ThiloHarich Factoring 0 2009-08-18 16:48

All times are UTC. The time now is 10:48.

Tue May 11 10:48:59 UTC 2021 up 33 days, 5:29, 1 user, load averages: 2.23, 2.01, 1.72

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.