Wednesday 12 March 2008

YAFA (c) JGW 2008

YAFA=Yet another factorization algorithm :)
I don't know whether this is any good (I _think_ it's new) - comments welcome...
Suppose we wish to factor N.
Write N=x^(2^n)-1, s.t. x=(N+1)^(2^-n)
Then N=(x-1)(x+1)(x^2+1)(x^4+1)...(x^2^(n-1)+1)
Start w/ n=1, and evaluate all the 2^n combinations of products of brackets above, testing for exact division into N as you go.
After all unsuccessful 2^n attempts, increment n, and repeat.

Thursday 24 January 2008


Mersenneplustwo project news:
Following up the recent find of the 8-digit factor of (M+2)1257787 by random-based WEP (factorize3), I also confirmed this result with "sequential" WEP (factorize2).
The factor is found on the first attempted base after the factor of 3 comes out:
[james@localhost wec]$ time ./factorize2.gmp4.2.1 -Pp1257787 -a0
a= 5031149 factor=3
a= 7546723 factor=20124593

real 16844m25.553s
user 15836m58.317s
sys 363m38.512s



The FERMATSEARCH.ORG (searching for factors of Fermat numbers) project has a new and improved website!
Its most recently found factor (August 21, 2007) was:
"485.2^338297+1 divides F338295"
Note that for really huge Fermats like this, the only efficient method of searching for factors is modular trial-division. However there is also some ECM work going on on the smaller Fermats... It will be interesting to see cooperation with the new Primenet (factorization) server?

Friday 18 January 2008

PrimeNet v5

Here's an exciting bit of news:
It looks like v5 of the GIMPS server will have built-in automatic reporting of factorization effort on Mersenne (and Fermat) numbers. As with the prime search itself, George Woltman and Scott Kurowski seem to have done a great job!

Tuesday 15 January 2008

Bernoulli and Euler Numbers

Some more recent news culled from the mersenneforum :)
advertising the recent revival of a couple of (related) factorization projects I had previously overlooked:
Sam Wagstaff (of Cunningham project fame) leads an initiative to find factors of Bernoulli, and Euler composites at:
Note that Bruce Dodson has already found some good-sized ECM factors from these targets, presumably as a diversion from the main Cunningham project!
Some links describing these numbers:


Bernstein, Birkner, Lange and Peters present GMP-EECM, a variant of GMP-ECM (and developed from it) but using Edwards curves, rather than the more standard Montgomery curves of regular GMP-ECM.
In one of their tests, this reduced the stage 1 time from 2448mS to 2276mS.
Alex Kruppa has stated that this improvement will also be incorporated into some future version of GMP-ECM.

Sunday 13 January 2008

Tuesday 8 January 2008


Intel officially announces availability of its new "Penryn" chips.
Apple has already incorporated several server versions, including quad-cores, into the Mac Pro line.

Friday 4 January 2008

Eric Landquist

[picture from Wikipedia - copyright Just H, creative commons license]

Here is a link to Eric Landquist's paper on the NFS:
Quote from the above:
"At least one author [17] believes that there
are faster methods out there. It’s my life-long dream to find one. I also
hope to see the Red Sox win a World Series."
Well, the Red Sox have won _two_ World Series since the paper was published (2002) - though personally I am an Astros fan! :)

Tuesday 1 January 2008

Frequency of Posts 2

Having made it to the New Year ( :) ), I expect the frequency of my posts to drop off somewhat, as I'm now running out of useful things to say...


To celebrate New Year 2008, for the past few days I have been factorizing M2008.
Here are the results:
ibu:~/math james$ time java superfac9

brutep: 3
brutep: 5
brutep: 17
brutep: 503
aprtcle: 54217
aprtcle: 238451
aprtcle: 178230287214063289511
aprtcle: 61676882198695257501367
aprtcle: 12070396178249893039969681
aprtcle: 5021
aprtcle: 1972386557777
aprtcle: 1912621
aprtcle: 57762875981
aprtcle: 38508212572597
aprtcle: 45063180240128066017730357
aprtcle: 15992518154179475674328213556857438690614816129
aprtcle: 86245368961389419078481015822433
duration: 40323 seconds