Command-line program for factoring small numbers

[KingKurly]

Originally Posted by James Heinrich

man pages are fine to know what a certain command does, but are not all that useful in solving compile-time errors.

It looks like a dependency issue to me. What Linux distro are you using?

Specifically, I think you are missing GMP-dev (header files, libraries, and such).

[James Heinrich]

Very likely. As far as I know it's some species of RedHat.

[Reed_Young]

Originally Posted by KingKurly

Specifically, I think you are missing GMP-dev (header files, libraries, and such).

{facepalm}
I manually edited ... some .conf file or something, after a lot of Googling, to link the GMP headers to GCC. If finally worked, but it's very nice to know I won't have to do that again! I'll just apt-get install libgmp3-dev instead (or whatever version they're up to the next time I need to install it again). Thanks for the tip.

[Reed_Young]

Originally Posted by James Heinrich

Very likely. As far as I know it's some species of RedHat.

A dependency issue is *definitely* one problem that you're having with GMP right now. It may or may not be the only one, but the GMP header is definitely not being found by GCC.

Originally Posted by James Heinrich

include/yafu.h:49:17: error: gmp.h: No such file or directory

Any *other* problems will be much easier to diagnose if you take care of that first. I think the tool is called "yum" in RedHat? In Debian, I'd apt-get it, so I can't really walk you through the installation, but I can tell you that the package name is "libgmp3-dev" and I'm not sure RedHat will have an identical naming scheme either, but hopefully this helps. Maybe you're happy factoring numbers via PHP, but if you do decide to finish configuring GMP & friends on your workstation (or whatever that machine is), I think King Kurly is right about needing gmp dev, and that just requires using your package manager which isn't really very complicated in any distro.

[bsquared]

Originally Posted by James Heinrich

man pages are fine to know what a certain command does, but are not all that useful in solving compile-time errors.

I wouldn't spend too much time trying to get yafu to work for 32 bit linux, if that's what you're trying to do. It's been ages since I tried, and I'm not at all sure it will work even if you get all of the dependencies installed. For these size numbers, pari/gp will work just fine.

[chris2be8]

Originally Posted by James Heinrich

Very likely. As far as I know it's some species of RedHat.

If it's Red Hat there will be a file called /etc/redhat-release containing the exact version. If it's not Red Hat the file will be named something ending in release so enter "ls /etc/*release" to find it.

Posting the contents and output from "uname -a" would give us a clue.

Chris K

[James Heinrich]

Originally Posted by chris2be8

Posting the contents and output from "uname -a" would give us a clue.

/etc/redhat-release says:

CentOS release 5.4 (Final)

uname -a says:

Linux ip-208-109-249-190.ip.secureserver.net 2.6.18-028stab070.14 #1 SMP Thu Nov 18 16:04:02 MSK 2010 i686 i686 i386 GNU/Linux

[Reed_Young]

CentOS is free RedHat, so "yum" should be the name of your package manager. Fire that up, then get / install any program with "gmp" and "dev" in it. It will likely be "libgmp#-dev" -- 'lib' for library, 'gmp' for GNU multiprecision, which you already know, and 'dev' which KingKurly already mentioned. Anyway, the 'dev' files really should straighten out all the headers including gmp.h, and allow you to use GMP as well as pari-gmp without any trouble.

[Mr. P-1]

Originally Posted by xilman

[pcl@anubis PROCESS]$ echo "17613769033772007210894662109212994801791" | ecm -c 100 1000000
GMP-ECM 6.2.2 [powered by GMP 4.3.1] [ECM]
Input number is 17613769033772007210894662109212994801791 (41 digits)
Using B1=1000000, B2=1045563762, polynomial Dickson(6), sigma=816405928
Step 1 took 1183ms
Step 2 took 990ms
********** Factor found in step 2: 74835908771936093401
Found probable prime factor of 20 digits: 74835908771936093401
Probable prime cofactor 235365205324763482391 has 21 digits
[pcl@anubis PROCESS]$


Paul

A neat trick for resolving composite P-1 factors is to use the P+1 method using the original bounds. This has a 50% chance of success per run.

[James Heinrich]

Originally Posted by Reed_Young

"yum" should be the name of your package manager. Fire that up, then get / install any program with "gmp" and "dev" in it.

yum told me that I had:

gmp.i386 4.1.4-10.el5 installed
...
gmp-devel.i386 4.1.4-10.el5 base

So I told it to install gmp-devel.i386 and it didn't complain.

I tried compiling yafu again, and it got a lot further than last time, but still failed:

# make x86
gcc -g -O3 -fomit-frame-pointer -Wall  -I. -Iinclude -m32 -c -o arith/tfm/fp_mul_comba.o arith/tfm/fp_mul_comba.c
gcc -g -O3 -fomit-frame-pointer -Wall  -I. -Iinclude -m32 -c -o arith/tfm/fp_mul_comba_small_set.o arith/tfm/fp_mul_comba_small_set.c
gcc -g -O3 -fomit-frame-pointer -Wall  -I. -Iinclude -m32 -c -o arith/tfm/fp_sqr_comba.o arith/tfm/fp_sqr_comba.c
gcc -g -O3 -fomit-frame-pointer -Wall  -I. -Iinclude -m32 -c -o arith/tfm/fp_sqr_comba_small_set.o arith/tfm/fp_sqr_comba_small_set.c
gcc -g -O3 -fomit-frame-pointer -Wall  -I. -Iinclude -m32 -c -o arith/tfm/fp_sqr_comba_generic.o arith/tfm/fp_sqr_comba_generic.c
gcc -g -O3 -fomit-frame-pointer -Wall  -I. -Iinclude -m32 -c -o arith/tfm/fp_2expt.o arith/tfm/fp_2expt.c
gcc -g -O3 -fomit-frame-pointer -Wall  -I. -Iinclude -m32 -c -o arith/tfm/fp_cmp_mag.o arith/tfm/fp_cmp_mag.c
gcc -g -O3 -fomit-frame-pointer -Wall  -I. -Iinclude -m32 -c -o arith/tfm/fp_mont_small.o arith/tfm/fp_mont_small.c
gcc -g -O3 -fomit-frame-pointer -Wall  -I. -Iinclude -m32 -c -o arith/tfm/fp_montgomery_calc_normalization.o arith/tfm/fp_montgomery_calc_normalization.c
gcc -g -O3 -fomit-frame-pointer -Wall  -I. -Iinclude -m32 -c -o arith/tfm/fp_montgomery_reduce.o arith/tfm/fp_montgomery_reduce.c
gcc -g -O3 -fomit-frame-pointer -Wall  -I. -Iinclude -m32 -c -o arith/tfm/fp_montgomery_setup.o arith/tfm/fp_montgomery_setup.c
gcc -g -O3 -fomit-frame-pointer -Wall  -I. -Iinclude -m32 -c -o arith/tfm/fp_mul_2.o arith/tfm/fp_mul_2.c
gcc -g -O3 -fomit-frame-pointer -Wall  -I. -Iinclude -m32 -c -o arith/tfm/s_fp_sub.o arith/tfm/s_fp_sub.c
gcc -g -O3 -fomit-frame-pointer -Wall  -I. -Iinclude -m32 -c -o factor/qs/msieve/lanczos.o factor/qs/msieve/lanczos.c
factor/qs/msieve/lanczos.c: In function 'yafu_mul_Nx64_64x64_acc':
factor/qs/msieve/lanczos.c:282: error: unknown register name '%mm1' in 'asm'
factor/qs/msieve/lanczos.c:282: error: unknown register name '%mm0' in 'asm'
factor/qs/msieve/lanczos.c: In function 'yafu_mul_64xN_Nx64':
factor/qs/msieve/lanczos.c:384: error: unknown register name '%mm1' in 'asm'
factor/qs/msieve/lanczos.c:384: error: unknown register name '%mm0' in 'asm'
make: *** [factor/qs/msieve/lanczos.o] Error 1

I do seem to have managed to compile PARI/GP, but I can't figure out how to get it to spit out an answer from the command line. I want to simply call [gp "factor(12345)"] and get the answer, how do I do that?

Or suggestions for what simple factoring program to try next?

[James Heinrich]

Originally Posted by paulunderwood

echo "factor(17613769033772007210894662109212994801791)" | gp -q

[74835908771936093401 1]

[235365205324763482391 1]

Hey, now that I go back and read this again, it makes sense, and works perfectly!