Command-line program for factoring small numbers

[James Heinrich]

I'm looking for a simple *nix program to factor P-1 factors (which, most of the time, will confirm that they're prime). So relatively small numbers, typically under 150 bits. I want something like:

>factor 17613769033772007210894662109212994801791
* 74835908771936093401
* 235365205324763482391

or

>factor 455144877715893163583
* 455144877715893163583

What's my simplest option?

[paulunderwood]

echo "factor(17613769033772007210894662109212994801791)" | gp -q

[74835908771936093401 1]

[235365205324763482391 1]



You could set up an alias with a parameter. Also you could tweak the output. Do any gurus want to give a solution?

[xilman]

Originally Posted by James Heinrich

I'm looking for a simple *nix program to factor P-1 factors (which, most of the time, will confirm that they're prime). So relatively small numbers, typically under 150 bits. I want something like:orWhat's my simplest option?

[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

[James Heinrich]

Please go on the assumption that my *nix knowledge is nonexistant, you won't be far off...

$ echo "factor(17613769033772007210894662109212994801791)" | gp -q
-bash: gp: command not found
-bash: echo: write error: Broken pipe

$ echo "17613769033772007210894662109212994801791" | ecm -c 100 1000000
-bash: ecm: command not found
-bash: echo: write error: Broken pipe

Output formatting is irrelevant, I can take the output in whatever form it cares to present itself and reformat according to my needs, that's not an issue.

[paulunderwood]

-bash: gp: command not found

install pari-gp



I edited ~/.bashrc and added this as the last line

factro () { echo "factor($*)" | gp -q; }

saved it. Restarted the terminal and ran:

factro 7100001

[3 3]

[59 1]

[4457 1]

[James Heinrich]

Originally Posted by paulunderwood

install pari-gp

Unfortunately my *nix-competance extends as far as beginner-level expertise with the commands "cd" and "ls", and not much beyond that.
(and it's a production webserver that I don't want to play with too much at risk of breaking things)

However, I have recently (yes, since posting...) that my server does in fact support PHP-gmp, and my PHP skills are considerably better, so I'll stick to hacking it out that way

[jasonp]

Check the sticky in the factoring subforum here for links to many programs that can do what you want. On unix, though, you'll probably have to compile them.

[xilman]

Originally Posted by jasonp

Check the sticky in the factoring subforum here for links to many programs that can do what you want. On unix, though, you'll probably have to compile them.

Or ask the likes of me to compile them for you.

Paul

[James Heinrich]

Originally Posted by xilman

Or ask the likes of me to compile them for you.

I may have to do that. I picked yafu at random and tried, and failed, ending up with:

[ yafu-1.28.4]$ 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
In file included from include/tfm.h:18,
                 from arith/tfm/fp_mul_comba.c:18:
include/yafu.h:49:17: error: gmp.h: No such file or directory
In file included from include/tfm.h:19,
                 from arith/tfm/fp_mul_comba.c:18:
include/arith.h:170: error: expected ')' before 'src'
include/arith.h:171: error: expected ')' before 'dest'
make: *** [arith/tfm/fp_mul_comba.o] Error 1

Of course, they supply precompiled binaries for Win32/64 and Linux64, but not Linux32, which is what I need :(

[chris2be8]

Originally Posted by James Heinrich

Unfortunately my *nix-competance extends as far as beginner-level expertise with the commands "cd" and "ls", and not much beyond that.

For beginners the best advice is to read the man pages. So typing "man ls" will give you all the options ls supports (probably more than you want).

"man" has it's own man page (type "man man" to read it) and "man intro" gives a relatively gentle introduction to Linux.

I often have 1 window to enter commands and another to read the man page for the command I'm using. Even experts don't want to to guess when using commands like fsck.

Chris K.

[James Heinrich]

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