## Sunday 30 September 2007

### 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! :)

## Saturday 29 September 2007

### 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++

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

## Friday 28 September 2007

### 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!

http://www.loria.fr/%7Ezimmerma/records/Pplus1.html

Note the largest ever is 52 digits, found by Peter Montgomery - well done Peter!

## Thursday 27 September 2007

### 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!

http://www.loria.fr/%7Ezimmerma/records/Pminus1.html

Note the largest ever is 66 digits, found by Takahiro Nohara - well done Takahiro!

## Wednesday 26 September 2007

### 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!

http://wwwmaths.anu.edu.au/~brent/ftp/champs.txt

Note the largest ever is 67-digits, found by Bruce Dodson - well done Bruce!

## Tuesday 25 September 2007

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

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

## Monday 24 September 2007

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

tiggatoo:~/math james$ java superfac9

f(2^100+277)*(2^100+331)

[1606938044258990275541962093111894167460966469892788384261671]

siqs...

aprtcle: 1267650600228229401496703205653

aprtcle: 1267650600228229401496703205707

duration: 7079 seconds

## Sunday 23 September 2007

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

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

## Saturday 22 September 2007

### 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)

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)

## Friday 21 September 2007

### 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)

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! :)

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

http://tech.groups.yahoo.com/group/xyyxf/surveys?id=1917568

## Thursday 20 September 2007

### 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!

(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

### 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?

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?

### 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]

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

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]

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]

Subscribe to:
Posts (Atom)