View Single Post
Old 2006-04-13, 16:12   #24
S00113
 
S00113's Avatar
 
Dec 2003

23·33 Posts
Default Mfactor on Linksys WRT54G wireless router

I compiled Mfactor (an old version I found on the web) for my Linksys WRT54G router, and it works! The router runs Linux, and I have changed to the OpenWRT distribution to get a more user friendly version. (At least it is more friendly to old unix users like me.) The CPU is a BCM4712 which runs the MIPS32 instruction set at 216MHz. The router also has 16 MiB RAM and 8 MiB flash memory. Frequenzy, RAM and amount of flash varies between versions, and not all versions run Linux. Go to http://www.openwrt.org/ for more information on this and other wireless routers with similar hardware.

This version limits factoring to 60 bits with 32bit integer arithmetic. Here is the result of one of my first tests (the 59 bit factor is known):

Code:
root@line:~# time ./Mfactor -h factorlog 77485997 3 1152921504606846975
# Mersenne factorer.  Author:  Peter L. Montgomery, pmontgom@cwi.nl
# $Id: Mfactor.c,v 1.2 1999/03/24 05:45:50 pmontgom Exp pmontgom $
# Compiled by GCC on 32-bit MIPS under IRIX.
sh: hinv: not found
# ARITHMETIC_MODEL = ARITHMETIC_INT32
# NUM_SIEVING_PRIME = 34567,   SIEVE_LENGTH_BITS = 204800
# SIEVE_STEP_BIT = 840
# TRYQ_BLOCKING = 3,     USING_ASSEMBLY = 0,    USING_POPULATION_COUNT = 0
# VECTOR = 0,    SHORT_VECTOR_LENGTH = 20
# Type sieving_prime_t has 32 bits.
# Type wsieve_t has 32 bits, of which all 32 are used.
# Type natural_t is signed and has 32 bits.
# Type uint32 has 32 bits.  Type uint64 has 64 bits.
# QBITSMAX = 60
#
# Invoked as ./Mfactor -h factorlog 77485997 3 1152921504606846975
# Running on line.(none) at Thu Apr 13 14:04:57 2006
#
# p = 77485997.  Searching q in [154971995, 1152921504488807235]
# The isieve loop in tryp sieves an interval of length
#    13330071035904000 = 1.333e+16  in NSIEVE = 96 pieces.
# It will need   86.49 passes to search from 154971995 to 1152921504488807235.
# 34567-th sieving prime is 409639.  9791 are below SIEVE_LENGTH_BITS/2,
# 8562 more below SIEVE_LENGTH_BITS, 16214 above.
M( 77485997 )C: 1152331426770601081  # line.(none)  @  Thu Apr 13 15:26:51 2006
# 323699721 values of q tried out of 1700467991 sieved.
#  80.96% of potential q's (mod 840*p) were eliminated by sieving.
M( 77485997 )U: 1152921504488807235  # line.(none)  @  Thu Apr 13 15:27:09 2006
real    1h 22m 12s
user    1h 21m 38s
sys     0m 33.76s
Next I'll try to make it faster by adjusting various defines in the source. Are there newer versions of Mfactor out there with new optimizations which may work on 32bit hardware?

Next project is mersfacgmp, which is able to factor higher and talk to a server, but mersfacgmp is much harder to cross-compile.
S00113 is offline   Reply With Quote