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.

## Wednesday 12 March 2008

## Thursday 24 January 2008

### (M+2)1257787

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

"

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

"

### FermatSearch

The FERMATSEARCH.ORG (searching for factors of Fermat numbers) project has a new and improved website!

http://www.fermatsearch.org/index.html

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?

http://www.fermatsearch.org/index.html

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!

http://v5www.mersenne.org/report_ECM/

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!

http://v5www.mersenne.org/report_ECM/

## Tuesday 15 January 2008

### Bernoulli and Euler Numbers

Some more recent news culled from the mersenneforum :)

http://mersenneforum.org/showthread.php?t=9841

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:

http://homes.cerias.purdue.edu/~ssw/bernoulli/index.html

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:

http://en.wikipedia.org/wiki/Bernoulli_number

http://en.wikipedia.org/wiki/Euler_number

http://mersenneforum.org/showthread.php?t=9841

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:

http://homes.cerias.purdue.edu/~ssw/bernoulli/index.html

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:

http://en.wikipedia.org/wiki/Bernoulli_number

http://en.wikipedia.org/wiki/Euler_number

### GMP-EECM

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.

http://cr.yp.to/papers.html#eecm

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.

http://cr.yp.to/papers.html#eecm

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

### Msieve v1.33

Msieve v1.33 now available:

Announcement at:

http://mersenneforum.org/showpost.php?p=122776&postcount=402

Download from:

http://www.boo.net/~jasonp/qs.html

Announcement at:

http://mersenneforum.org/showpost.php?p=122776&postcount=402

Download from:

http://www.boo.net/~jasonp/qs.html

## Tuesday 8 January 2008

### Harpertown

Intel officially announces availability of its new "Penryn" chips.

http://www.bit-tech.net/news/2008/01/07/intel_announces_16_new_45nm_cpus_at_ces/1

Apple has already incorporated several server versions, including quad-cores, into the Mac Pro line.

http://www.bit-tech.net/news/2008/01/07/intel_announces_16_new_45nm_cpus_at_ces/1

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:

http://www.math.uiuc.edu/~landquis/nfsieve.pdf

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...

### M2008

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

f2^2008-1

[29392145799020915820360529950148658790971333173470597132227654062739616291644680034730482849702560509912216694758079047000246245398094216484503842717866321546017277221199943680176327461949451487085805309456252478664093558693475421170513158666359386616551679118889574095089825179039567782281258040824405166424107240700021377434209148110825999078639302784109824695476896212613634081852488010690884578129204889342821483040517575643751434792922414912394467695078935531662069192598956042024980981047457429185377388949433859975257289323374605954282310600673952044911495373010647749329399156163119321894151520255]

wanless...

brutep: 3

wanless...

brutep: 5

wanless...

brutep: 17

brute...

brutep: 503

wanless...

ecm...

aprtcle: 54217

ecm...

aprtcle: 238451

ecm...

aprtcle: 178230287214063289511

ecm...

aprtcle: 61676882198695257501367

ecm...

aprtcle: 12070396178249893039969681

aprtcle:

5058345723951854688505665428846313806490903121677364358901199128608233

wanless...

brute...

aprtcle: 5021

ecm...

ecm...

aprtcle: 1972386557777

aprtcle: 1912621

ecm...

aprtcle: 57762875981

ecm...

aprtcle: 38508212572597

ecm...

aprtcle: 45063180240128066017730357

siqs...

aprtcle: 15992518154179475674328213556857438690614816129

aprtcle: 86245368961389419078481015822433

aprtcle:

10084786891164868903044000461741193511166162933699139834764709537603304010587634094053631800618313958847949862753441381884114308571221779233867837717363364521350181435128687986278658451823408133532192171438161388219841827075198840055685217831601941566655243743704980863680404547437764128787958275830001

duration: 40323 seconds

Here are the results:

ibu:~/math james$ time java superfac9

f2^2008-1

[29392145799020915820360529950148658790971333173470597132227654062739616291644680034730482849702560509912216694758079047000246245398094216484503842717866321546017277221199943680176327461949451487085805309456252478664093558693475421170513158666359386616551679118889574095089825179039567782281258040824405166424107240700021377434209148110825999078639302784109824695476896212613634081852488010690884578129204889342821483040517575643751434792922414912394467695078935531662069192598956042024980981047457429185377388949433859975257289323374605954282310600673952044911495373010647749329399156163119321894151520255]

wanless...

brutep: 3

wanless...

brutep: 5

wanless...

brutep: 17

brute...

brutep: 503

wanless...

ecm...

aprtcle: 54217

ecm...

aprtcle: 238451

ecm...

aprtcle: 178230287214063289511

ecm...

aprtcle: 61676882198695257501367

ecm...

aprtcle: 12070396178249893039969681

aprtcle:

5058345723951854688505665428846313806490903121677364358901199128608233

wanless...

brute...

aprtcle: 5021

ecm...

ecm...

aprtcle: 1972386557777

aprtcle: 1912621

ecm...

aprtcle: 57762875981

ecm...

aprtcle: 38508212572597

ecm...

aprtcle: 45063180240128066017730357

siqs...

aprtcle: 15992518154179475674328213556857438690614816129

aprtcle: 86245368961389419078481015822433

aprtcle:

10084786891164868903044000461741193511166162933699139834764709537603304010587634094053631800618313958847949862753441381884114308571221779233867837717363364521350181435128687986278658451823408133532192171438161388219841827075198840055685217831601941566655243743704980863680404547437764128787958275830001

duration: 40323 seconds

Subscribe to:
Posts (Atom)