Bjarne Stroustrup

This is a picture (from Wikipedia) of Bjarne Stroustrup - the inventor of C++.
I only found out recently, apparently he went to the same college I did! :)

Number Theory Software Libraries

Here are links to four Number-Theory software libraries - PARI, NTL, LiDIA and GiNaC - useful for writing factorizing routines...
http://pari.math.u-bordeaux.fr/
http://www.shoup.net/ntl/
http://www.cdc.informatik.tu-darmstadt.de/TI/LiDIA/
http://www.ginac.de/
Note that these are all C or C++

P+1 Champs

Here is a list of P+1 "champions" (maintained by Paul Zimmermann), that is to say, record-size factors (of general numbers) found by Williams' P+1 method:
http://www.loria.fr/%7Ezimmerma/records/Pplus1.html
Note the largest ever is 52 digits, found by Peter Montgomery - well done Peter!

P-1 Champs

Here is a list of P-1 "champions" (maintained by Paul Zimmermann), that is to say, record-size factors (of general numbers) found by Pollard's P-1 method:
http://www.loria.fr/%7Ezimmerma/records/Pminus1.html
Note the largest ever is 66 digits, found by Takahiro Nohara - well done Takahiro!

ECM Champs

Here is a list of ECM "champions" (maintained by Richard Brent), that is to say, record-size factors (of general numbers) found by ECM:
http://wwwmaths.anu.edu.au/~brent/ftp/champs.txt
Note the largest ever is 67-digits, found by Bruce Dodson - well done Bruce!

RSA-200: Factoring a 200DIGIT semiprime by GNFS

[1 DIGIT = log_2(10) bits ~ 3.3 bits]
From the following link:
http://en.wikipedia.org/wiki/RSA-200
"In mathematics, RSA-200 is one of the RSA numbers, large semiprimes that are part of the RSA Factoring Challenge."
"On May 9, 2005, F. Bahr, M. Boehm, J. Franke, and T. Kleinjung announced that they had factorized the number using GNFS as follows:
RSA-200 = 3532461934402770121272604978198464368671197400197625023649303468776121253679423200058547956528088349
* 7925869954478333033347085841480059687737975857364219960734330341455767872818152135381409304740185467"
"The CPU time spent on finding these factors by a collection of parallel computers amounted – very approximately – to the equivalent of 75 years work for a single 2.2 GHz Opteron-based computer."

Factoring a 200-bit semiprime with superfac9 (by SIQS)

A semiprime is the product of only 2 primes, each of a similar size:

tiggatoo:~/math james$ java superfac9
f(2^100+277)*(2^100+331)

[1606938044258990275541962093111894167460966469892788384261671]
siqs...
aprtcle: 1267650600228229401496703205653
aprtcle: 1267650600228229401496703205707
duration: 7079 seconds

What is an 'Aurifeuillian' factor?

A type of algebraic factorization, of specific types of number (particularly a^n+/-b^n - see Cunningham Project), involving polynomials, particularly cyclotomic.
Some links:
http://mathworld.wolfram.com/AurifeuilleanFactorization.html
http://www.numericana.com/answer/numbers.htm#aurifeuille
http://www.ams.org/mcom/2006-75-253/S0025-5718-05-01766-7/home.html
http://perso.orange.fr/colin.barker/lpa/cycl_fac.htm
http://web.comlab.ox.ac.uk/oucl/work/richard.brent/pd/rpb127.pdf

GGNFS on PPC

Does anybody have any tips/experience on compiling and running GGNFS on PPC?
It (version 0.77.1) seems to compile for me (gcc 4.0.0 darwin8) in pretty much the same way as on a Lintel system, and runs similarly, too, for input numbers up to about 80 digits, but then above that, on PPC I get fatal errors that do _not_ appear on Lintel.
The errors are all at the start of the sieving stage, and of the form:
"warning: not enough polynomials in mpqs with 121051732500949"
(It would seem the same sieve executable - gnfs-lasieve4I12e - is being used as for the smaller inputs that complete successfully)

on Wanless' Fifth Conjecture

http://groups.google.com/group/sci.math/browse_frm/thread/a71227bb887498cf/7722fe04afa1117a?lnk=st&q=wanless+fifth+conjecture&rnum=1#7722fe04afa1117a

wrt the above post of mine, the two caveats I had were:
1) Although the number of bases needed to be tested may be finite, the _time_ taken to test each base can still rise without limit (serious problem)
2) There is no guarantee that factors found will necessarily be prime (less serious)

Musings on ECM/NFS

One thought occurs to me:
ECM is basically Pollard with fields, while NFS is Fermat with polynomials...
There's some symmetry there! :)

XYYXF project status and drive

I'm currently participating in the XYYXF project's latest drive, to complete factorization of all xyyx composites with x<=100 as soon as possible. Note that these latter comprise the entire original scope of the project, which has its sixth anniversary on November 23rd. There is automatic work-distribution via an ECMNet server, and it is through this that I, for one, am contributing. Though the bulk of the effort is of type NFS. It's even possible that the current target will be achieved by end-October... see this poll for current opinion:
http://tech.groups.yahoo.com/group/xyyxf/surveys?id=1917568

superfac9.java

http://bearnol.is-a-geek.com/superfac9.java
(with thanks to Dario Alpern)

Explanation of input format:

1) You can either enter just a (denary) number in the normal way:
eg, 123 or 7654321 or

2) you can enter a formula using the following operators by prefixing with f or F:
+ for addition
- for subtraction
* for multiplication
/ for integer division
% for modulo division
^ or # for exponentiation
[ or { or ( for open parenthesis (nestable)
] or } or ) for close parenthesis (nestable)
eg, f2#700+1 or F2#(2#12)+1 or

3) you can enter a randomly generated number of approximate size 2^n, by using the syntax rn or Rn, where n is an integer:
eg, r200 or R1000


[please note, in particular, the speed with which algebraic factors are found]
Enjoy!

GGNFS Relations plot

Here is the plot of the relations accrued in my latest GGNFS factorization.
(It's hopefully about half-way through)
Anybody know why there has recently been an episode of _decrease_?

Fundamental Theorem of Arithmetic

Check the following link for the standard exposition of the proof of this theorem:
http://www.bearnol.pwp.blueyonder.co.uk/Math/fundarit.htm

However a simpler proof might go as follows:
1) every a*b is uniquely = ab
2) therefore every a*(1/b) is uniquely = a/b
3) consider b prime
4) induction completes the proof

I can't see anything wrong with this - and you?

Some links to factorization projects

http://www.leyland.vispa.com/numth/factorization/anbn/main.htm
http://xyyxf.at.tut.by/
http://bearnol.is-a-geek.com/Mersenneplustwo/Mersenneplustwo.html
http://hjem.get2net.dk/jka/math/consecutive_factorizations.htm
http://homes.cerias.purdue.edu/~ssw/cun/

Frequency of Posts

I hope to post at least one new post a day...

Installing GMP-ECM on a Mac

This can either be done by compiling from the tarball in the normal way:
0) N.B. requirement for GMP library present first
1) untar
2) configure
3) make
4) (optionally) make install

or, more conveniently, download and install DarwinPorts, followed by simply:
1) 'sudo port install gmp-ecm'

[note the similarity to Ubuntu's apt-get process]

Some links to factorization software

http://www.alpertron.com.ar/ECM.HTM
http://www.boo.net/~jasonp/qs.html
http://ecm.gforge.inria.fr/
http://www.math.ttu.edu/~cmonico/software/ggnfs/

Some introductory links

Definitions of factorization:
http://en.wikipedia.org/wiki/Factorization
http://en.wikipedia.org/wiki/Integer_factorization

Some factorization methods:
http://en.wikipedia.org/wiki/Trial_division
http://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
http://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization
http://en.wikipedia.org/wiki/General_number_field_sieve
http://www.bearnol.pwp.blueyonder.co.uk/Math/Factor/Factorwpa2.html

Factorization Blog Created

Hello, and welcome to the 'Factorization' Blog Site.
This aims to become the definitive word on all things related to integer-factorization (number theory)... you are encouraged to contribute
Happy factoring, and good luck!
James (Wanless) [admin]