History of factorization records by sieving methods

This graph is by Francois Morain. http://algo.inria.fr/seminars/sem00-01/morain.html
(image linked to in situ)
The relevant figure is towards the bottom of the article, in Section 4.

Penryn

It would appear that Intel's next-generation processors (Penryn) draw up to 40% less power than current CPUs, under full load. :))) Quite welcome I imagine, in the current climate (pun intended :( ).
http://www.tomshardware.com/2007/10/29/intel_penryn_4ghz_with_air_cooling/page14.html
This is no doubt due to moving to the smaller 45nm die resolution. Paul Otellini (CEO) has said that Penryn will ship 12 November 2007...

Coincidence?

Is it coincidence that Fermat's method works best with factors close to the square root of the input number, while NFS is particularly good at factoring semiprimes?

XYYXF Project milestone

Congratulations to the XYYXF project, who have just finished their original target of factoring all composites with x and y <=100, after 6 years! The search continues with x and y extended to 150...

http://xyyxf.at.tut.by/news.html#0

Daylight Savings Time

Now the clocks have gone back, all my ECMNet times are correct again ! :)

Msieve v1.29

New version of msieve (by Jason Papadopoulos) now available.
Download from:
http://www.boo.net/~jasonp/qs.html
Announcement at:
http://mersenneforum.org/showthread.php?p=117235#post117235

Fermat's Method

This 400-yr old method is the basis for many modern sieving factorization methods.
It relies on the discovery of an expression for the input number, as the difference between two (integral) squares.

http://en.wikipedia.org/wiki/Fermat%27s_factorization_method

Also, the pseudocode immediately below is taken from a PD document by Connelly Barnes of Oregon State University
http://oregonstate.edu/~barnesc/documents/factoring.pdf

function fermatFactor(N)
for x from ceil(sqrt(N)) to N
ySquared := x * x - N
if isSquare(ySquared) then
y := sqrt(ySquared)
s := (x - y)
t := (x + y)
if s <> 1 and s <> N then
return s, t
end if
end if
end for
end function

And here is its Java implementation (from superfac9) [with thanks to DT]:

BigInteger factorizefermat(BigInteger n) {
BigInteger a, bSq;
long iterations = 1L;

a = sqrt(n);
if(n.mod(a).compareTo(ZERO) == 0) return a;

while(iterations<10000000) {
bSq = a.multiply(a).subtract(n);
if(fastsquareQ(bSq))
return a.subtract(sqrt(bSq)); // bSq is a square, factorization found
a = a.add(ONE);
iterations++;
}

return n;
}