mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2009-10-07, 06:25   #1
boothby
 
Oct 2009

410 Posts
Default 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
boothby is offline   Reply With Quote
Old 2009-10-07, 07:08   #2
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

13·491 Posts
Default

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
fivemack is offline   Reply With Quote
Old 2009-10-07, 16:33   #3
Jeff Gilchrist
 
Jeff Gilchrist's Avatar
 
Jun 2003
Ottawa, Canada

3×17×23 Posts
Default

You can also use this guide to help you out:
http://gilchrist.ca/jeff/factoring/n...ers_guide.html
Jeff Gilchrist is offline   Reply With Quote
Old 2009-10-07, 17:46   #4
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

2×17×73 Posts
Default

Quote:
Originally Posted by fivemack View Post
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
Andi47 is offline   Reply With Quote
Old 2009-10-16, 05:15   #5
boothby
 
Oct 2009

1002 Posts
Default

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
boothby is offline   Reply With Quote
Old 2009-10-16, 06:09   #6
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

16EE16 Posts
Default

Quote:
Originally Posted by boothby View Post
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?
henryzz is offline   Reply With Quote
Old 2009-10-16, 16:27   #7
boothby
 
Oct 2009

22 Posts
Default

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
boothby is offline   Reply With Quote
Old 2009-10-16, 16:50   #8
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

16EE16 Posts
Default

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
henryzz is offline   Reply With Quote
Old 2009-10-16, 17:09   #9
boothby
 
Oct 2009

1002 Posts
Default

Henryzz, uname -m reports "x86_64"
boothby is offline   Reply With Quote
Old 2009-10-16, 17:22   #10
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

133568 Posts
Default

Quote:
Originally Posted by boothby View Post
Henryzz, uname -m reports "x86_64"
they should work then
what is the error message?
henryzz is offline   Reply With Quote
Old 2009-10-16, 17:24   #11
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

638310 Posts
Default

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?
fivemack is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Best approach for P-1? Mark Rose PrimeNet 6 2017-05-23 23:58
Unorthodox approach to primes Erkan PrimeNet 7 2017-01-10 03:34
a backwards approach to Mersenne testing Mini-Geek Information & Answers 14 2010-11-14 16:16
An Analytic Approach to Subexponential Factoring akruppa Math 2 2009-12-11 18:05
Factoring with the birthday problem approach 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.