Or this?

http://groups.google.com/group/sci.math/browse_frm/thread/bb9eb35568ce6026/92dc3f61562b5755?lnk=gst&q=suggestion+factorization#92dc3f61562b5755

http://groups.google.com/group/sci.math/browse_frm/thread/417c69f4c2ff5f26#

J

Finalized(?!) (GMP-)WE algorithm code

/* Factoring general integers with WE method using random base(s).
Author: James Wanless (c) 2000-9
*/

#include
#include
#include

#include
#include
#include

gmp_randclass r (gmp_randinit_default);

mpz_class rand2(long bits)
/* returns random bits-bit integer */
{
return r.get_z_bits(bits);
}

int Rabin_Miller(mpz_class n)
/* given an integer n >= 3 returns 0 composite, 1 probably prime */
{
return mpz_probab_prime_p(n.get_mpz_t(), 10);
}

mpz_class gcd(mpz_class a, mpz_class b)
/* returns greatest common divisor of a and b */
{
mpz_t temp;
mpz_init(temp);
mpz_gcd(temp, a.get_mpz_t(), b.get_mpz_t());
mpz_class temp_class(temp);
mpz_clear(temp);
return temp_class;
}

mpz_class exp_mod(mpz_class x, mpz_class b, mpz_class n)
/* returns x ^ b mod n */
{
mpz_t temp;
mpz_init (temp);
mpz_powm(temp, x.get_mpz_t(), b.get_mpz_t(), n.get_mpz_t());
mpz_class temp_class(temp);
mpz_clear (temp);
return temp_class;
}

bool Wanless (mpz_class n)
{
mpz_class basestested = 0;
mpz_class T = 1;
mpz_class b = 1;
mpz_class A = 2;
mpz_class prodA = 2;
mpz_class wanless = 2;
long nbits = 1;

if (Rabin_Miller(n)) {
cout << n << "\n";
fflush(stdout);
return true;
}

if (n < 2)
return false;

if (n % 2 == 0) {
cout << "2\n";
fflush(stdout);
return Wanless(n / 2);
}


while (wanless < n) {
wanless *= 2;
nbits ++;
}

while (T == 1 || T == n) {
basestested++;
cout << "base#" << basestested << "\r";
fflush(stdout);

prodA = 1;
for (long i = 0; i < nbits; i++) {
A = rand2(nbits);
prodA *= A;
prodA = prodA % n;
}


b = exp_mod(prodA, wanless, n);
T = gcd(n, exp_mod(b, n, n) - b);
}

if (T > 1 && T < n) {
cout << "\n" << T << "\t[prodA=" << prodA << "]\n";
fflush(stdout);
Wanless(n / T);
}


return (false);

}

int main(void)
{
mpz_class N;

for (;;) {
cout << "number to be tested or 0 to quit:\n";
cin >> N;
if (N == 0) break;
Wanless(N);
}
return 0;
}

Factorization Database

The following is a really cool site!
http://factorization.ath.cx/search.php

CRTfac3

I wonder whether (quite simply) this was what I was aiming at...:
(copyright 2009-02-02 JGW, again, just-in-case :)

import java.math.BigInteger;
import java.util.Random;
import java.util.Date;

public class CRTfac3 {
static BigInteger zero = new BigInteger("0");
static BigInteger one = new BigInteger("1");
static BigInteger two = new BigInteger("2");
static BigInteger thousand = new BigInteger("1000");

static BigInteger n = new BigInteger("0");
static String s;

static int olds1 = 0;
static int s1 = 0;

public static void main (String args[])
throws java.io.IOException {

CRTfac3 CRTfac3inst = new CRTfac3();

char c;
String sInput;

Date d;
long starttime;
long finishtime;
long duration;

while (true) {
StringBuffer sbInput = new StringBuffer("");

while ((c = (char)System.in.read()) != '\n' && c != '\r')
sbInput.append(c);
System.in.read();
sInput = sbInput.toString().trim();


if (sInput.charAt(0) == 'f' || sInput.charAt(0) == 'F') {
s = sInput.substring(1).trim();

s1 = 0;
olds1 = 0;
n = CRTfac3inst.eval(s);

System.out.println('[' + n.toString() + ']');
}
else {
n = new BigInteger(sInput);
}


d = new Date();
starttime = d.getTime();

CRTfac3inst.factorize(n);

d = new Date();
finishtime = d.getTime();

duration = (finishtime-starttime)/1000;

System.out.println("duration: " + duration + " seconds");

System.out.println();
}
}

public boolean factorize(BigInteger n) {
boolean prime = false;
BigInteger a = new BigInteger("1");
BigInteger b = new BigInteger("1");
BigInteger T = new BigInteger("1");

if (n.isProbablePrime(1000)) {
prime = true;
System.out.println(n);
return prime;
}

while (T.compareTo(one) == 0 || T.compareTo(n) == 0) {
T = n.gcd(b);
if (a.mod(thousand).compareTo(zero) == 0)
System.out.print("a = " + a.toString() + '\r');
a = a.add(one);
b = b.multiply(a).mod(n);
}


if (T.compareTo(one) > 0 && T.compareTo(n) < 0) {
factorize(T);
factorize(n.divide(T));
}
else {
prime = false;
System.out.println("composite" +'\t' + n);
}

return prime;

}


public BigInteger evalRand(char op, BigInteger oldn) {
BigInteger n = new BigInteger("1");


switch (op) {
case 'r':
case 'R':
Random r = new Random();

n = new BigInteger(oldn.intValue(), r);
break;

default:
n = oldn;
break;
}
return n;
}

public BigInteger evalFact(BigInteger oldn, char op) {
BigInteger n = new BigInteger("1");
BigInteger i = new BigInteger("1");
BigInteger j = new BigInteger("1");
boolean prime = true;


switch (op) {
case '!':
for (i = one; i.compareTo(oldn) <= 0; i = i.add(one))
n = n.multiply(i);
break;

case '#':
for (i = one; i.compareTo(oldn) <= 0; i = i.add(one)) {
prime = true;
for (j = two; (prime == true) && (j.multiply(j).compareTo(i) <= 0); j = j.add(one))
if (i.remainder(j).compareTo(zero) == 0)
prime = false;
if (prime == true)
n = n.multiply(i);
}
break;

default:
n = oldn;
break;
}
return n;
}

public BigInteger evalPower(BigInteger oldn, BigInteger n1, char op) {
BigInteger n = new BigInteger("0");

switch (op) {
case '^':
n = oldn.pow(n1.intValue());
break;
default:
n = n1;
break;
}
return n;
}

public BigInteger evalProduct(BigInteger oldn, BigInteger n1, char op) {
BigInteger n = new BigInteger("0");

switch (op) {
case '*':
n = oldn.multiply(n1);
break;
case '/':
n = oldn.divide(n1);
break;
case '%':
n = oldn.remainder(n1);
break;
default:
n = n1;
break;
}
return n;
}

public BigInteger evalSum(BigInteger oldn, BigInteger n1, char op) {
BigInteger n = new BigInteger("0");

switch (op) {
case '+':
n = oldn.add(n1);
break;
case '-':
n = oldn.subtract(n1);
break;
default:
n = n1;
break;
}
return n;
}

public BigInteger eval(String s) {
BigInteger oldn0 = new BigInteger("0");
BigInteger oldn1 = new BigInteger("0");
BigInteger oldn2 = new BigInteger("0");
BigInteger n = new BigInteger("0");

char oldop0 = 0;
char oldop1 = 0;
char oldop2 = 0;
char op = 0;

while (s1 < s.length()) {
switch (s.charAt(s1)) {
case '(':
case '[':
case '{':
s1++;
n = eval(s);
break;

case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
n = readNum(s);
break;

default:
break;
}
if (s1 < s.length()) {
switch (s.charAt(s1)) {

case ')':
case ']':
case '}':
case '!':
case '#':
case 'r':
case 'R':
case '^':
case '*':
case '/':
case '%':
case '+':
case '-':
op = s.charAt(s1);
s1++;
break;

default:
break;
}
}
else
op = 0;


switch (op) {
case 0:
case ')':
case ']':
case '}':
n = evalPower(oldn2, n, oldop2);
n = evalProduct(oldn1, n, oldop1);
n = evalSum(oldn0, n, oldop0);
return n;

case '!':
case '#':
n = evalFact(n, op);
break;

case 'r':
case 'R':
n = readNum(s);
n = evalRand(op, n);
break;

case '^':
n = evalPower(oldn2, n, oldop2);
oldn2 = n;
oldop2 = op;
break;

case '*':
case '/':
case '%':
n = evalPower(oldn2, n, oldop2);
oldop2 = 0;
n = evalProduct(oldn1, n, oldop1);
oldn1 = n;
oldop1 = op;
break;

case '+':
case '-':
n = evalPower(oldn2, n, oldop2);
oldop2 = 0;
n = evalProduct(oldn1, n, oldop1);
oldop1 = 0;
n = evalSum(oldn0, n, oldop0);
oldn0 = n;
oldop0 = op;
break;
default:
break;
}
}
return n;
}

public BigInteger readNum(String s) {
olds1 = s1;
while (s1 < s.length() && Character.isDigit(s.charAt(s1)))
s1++;
n = new BigInteger(s.substring(olds1, s1));

return n;
}


}

bear...@gmail.com wrote:
> Is it possible to use CRT to factor integers - or is this in effect
> what modern sieving algorithms already do anyway?
> J

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.

(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

"

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?

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/

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

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.

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

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.

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

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

Arjen Bot

Also there is Arjen Bot's page of factorizations of 2^n+1
http://www.euronet.nl/users/bota/medium-p-odd.txt

Home Primes Search

Let me introduce another factorization project, the Home Primes Search:
http://www.mersennewiki.org/index.php/Home_Prime
http://www.mersennewiki.org/index.php/Home_Primes_Search

NFSNET

Here is a link to the NFSNET project, a distributed attack on Cunningham Project targets using the Number Field Sieve:
http://www.nfsnet.org/

P49_101_87

I can't resist mentioning a fun result I had recently for the XYYXF project:
http://xyyxf.at.tut.by/records.html#ecm
[There I am currently in tenth place! :)]
I can certainly recommend the XYYXF ECMNet server as a slick and easy way to find interesting factors for that project.

WE on Carmichaels

When running WE on Carmichaels, clearly the algorithm will never terminate.
http://en.wikipedia.org/wiki/Carmichael_numbers
However, there is a simple workaround, by simply multiplying the input number to be factored (if Carmichael) by a suitable larg(ish) prime, eg a Mersenne. This will normally eject the factors, additionally, as required.
Here are some examples:
1)
tiggatoo:~/math/we james$ java we2tr2
f168003672409*(2^127-1)

[28584343649372241809274301558307881708368828786343]
base#72
elapsed=0s factor=6073 A=13044086312830013543739988769
base#70
elapsed=0s factor=3037 A=860763419187377590694240501658
base#230
elapsed=1s factor=9109 A=771019052198021707484273222802
170141183460469231731687303715884105727
duration: 1 seconds


2)
tiggatoo:~/math/we james$ java we2tr2
f173032371289*(2^89-1)

[107101850255573582977951074701018631079]
base#43
elapsed=0s factor=3067 A=1236330343540696294158885383112
base#149
elapsed=0s factor=6133 A=559525871748815289923955370298
base#758
elapsed=1s factor=9199 A=194689393018084379227390724801
618970019642690137449562111
duration: 1 seconds


3)
tiggatoo:~/math/we james$ java we2tr2
f973694665856161*(2^127-1)

[165665562777913375106491436985024163141370898298334047]
base#3
elapsed=0s factor=6841 A=1245204978926759694403655173839
base#0
elapsed=0s factor=2281 A=1024632434440788626941999868632
base#7
elapsed=0s factor=4561 A=457244767350940464517786915322
base#12
elapsed=0s factor=13681 A=85779304638188382542657979233
170141183460469231731687303715884105727
duration: 0 seconds


And here, for the record/or in case anyone wants to confirm results above, is the Java source code to we2tr2 (Copyright JGW ~ 2000):

import java.math.BigInteger;
import java.util.Random;
import java.util.Date;

public class we2tr2 {
static BigInteger zero = new BigInteger("0");
static BigInteger one = new BigInteger("1");
static BigInteger two = new BigInteger("2");
static BigInteger hundred = new BigInteger("100");
static BigInteger thousand = new BigInteger("1000");

static BigInteger n = new BigInteger("0");
static BigInteger p = new BigInteger("0");
static BigInteger known = new BigInteger("0");
static BigInteger numtrials = new BigInteger("0");
static String s;

static int olds1 = 0;
static int s1 = 0;

static Date d;
static long starttime;
static long finishtime;
static long duration;




public static void main (String args[])
throws java.io.IOException {

we2tr2 we2tr2inst = new we2tr2();

char c;
String sInput;

StringBuffer sbInput = new StringBuffer("");

while ((c = (char)System.in.read()) != '\n' && c != '\r')
sbInput.append(c);
System.in.read();
sInput = sbInput.toString().trim();


if (sInput.charAt(0) == 'f' || sInput.charAt(0) == 'F') {
s = sInput.substring(1).trim();

s1 = 0;
olds1 = 0;
p = we2tr2inst.eval(s);

System.out.println('[' + p.toString() + ']');
}
else {
p = new BigInteger(sInput);
}


n = p;

d = new Date();
starttime = d.getTime();

we2tr2inst.factorize(n);

d = new Date();
finishtime = d.getTime();

duration = (finishtime-starttime)/1000;

System.out.println("duration: " + duration + " seconds");

System.out.println();
}

public boolean factorize(BigInteger n) {
boolean prime = false;
BigInteger numtested = new BigInteger("0");
BigInteger T = new BigInteger("1");
BigInteger b = new BigInteger("1");
BigInteger A = new BigInteger("2");
BigInteger wanless = new BigInteger("2");

if (n.isProbablePrime(1000)) {
prime = true;
System.out.println(n);
return prime;
}

// workaround - apparent java bug in modPow - JGW
if (n.compareTo(two) < 0)
return false;

if (n.remainder(two).compareTo(zero) == 0) {
System.out.println(two.toString());
// added 2006-06-09
return(factorize(n.divide(two)));
}
// end workaround

while (wanless.compareTo(n) < 0)
wanless = wanless.multiply(two);

Random r = new Random();

numtested = zero;

while (T.compareTo(one) == 0 || T.compareTo(n) == 0) {
// changed JW 2005-3-23
A = new BigInteger(hundred.intValue(), r);

// added JGW 2006-06-09
System.out.print("base#" + numtested + '\r');



// changed DT 2005-2-20
b = A.modPow(wanless, n);
T = n.gcd(b.modPow(n, n).subtract(b));

numtested = numtested.add(one);
}





if (T.compareTo(one) > 0 && T.compareTo(n) < 0) {

d = new Date();
finishtime = d.getTime();

duration = (finishtime-starttime)/1000;


System.out.println();
System.out.println("elapsed=" + duration + "s" + '\t' + "factor=" + T.toString() + '\t' + "A=" + A.toString() + '\t');
factorize(n.divide(T));
}

return prime;

}


public BigInteger evalRand(char op, BigInteger oldn) {
BigInteger n = new BigInteger("1");


switch (op) {
case 'r':
case 'R':
Random r = new Random();

n = new BigInteger(oldn.intValue(), r);
break;

default:
n = oldn;
break;
}
return n;
}

public BigInteger evalFact(BigInteger oldn, char op) {
BigInteger n = new BigInteger("1");
BigInteger i = new BigInteger("1");
BigInteger j = new BigInteger("1");
boolean prime = true;


switch (op) {
case '!':
for (i = one; i.compareTo(oldn) <= 0; i = i.add(one))
n = n.multiply(i);
break;

case '#':
for (i = one; i.compareTo(oldn) <= 0; i = i.add(one)) {
prime = true;
for (j = two; (prime == true) && (j.multiply(j).compareTo(i) <= 0); j = j.add(one))
if (i.remainder(j).compareTo(zero) == 0)
prime = false;
if (prime == true)
n = n.multiply(i);
}
break;

default:
n = oldn;
break;
}
return n;
}

public BigInteger evalPower(BigInteger oldn, BigInteger n1, char op) {
BigInteger n = new BigInteger("0");

switch (op) {
case '^':
n = oldn.pow(n1.intValue());
break;
default:
n = n1;
break;
}
return n;
}

public BigInteger evalProduct(BigInteger oldn, BigInteger n1, char op) {
BigInteger n = new BigInteger("0");

switch (op) {
case '*':
n = oldn.multiply(n1);
break;
case '/':
n = oldn.divide(n1);
break;
case '%':
n = oldn.remainder(n1);
break;
default:
n = n1;
break;
}
return n;
}

public BigInteger evalSum(BigInteger oldn, BigInteger n1, char op) {
BigInteger n = new BigInteger("0");

switch (op) {
case '+':
n = oldn.add(n1);
break;
case '-':
n = oldn.subtract(n1);
break;
default:
n = n1;
break;
}
return n;
}

public BigInteger eval(String s) {
BigInteger oldn0 = new BigInteger("0");
BigInteger oldn1 = new BigInteger("0");
BigInteger oldn2 = new BigInteger("0");
BigInteger n = new BigInteger("0");

char oldop0 = 0;
char oldop1 = 0;
char oldop2 = 0;
char op = 0;

while (s1 < s.length()) {
switch (s.charAt(s1)) {
case '(':
case '[':
case '{':
s1++;
n = eval(s);
break;

case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
n = readNum(s);
break;

default:
break;
}
if (s1 < s.length()) {
switch (s.charAt(s1)) {

case ')':
case ']':
case '}':
case '!':
case '#':
case 'r':
case 'R':
case '^':
case '*':
case '/':
case '%':
case '+':
case '-':
op = s.charAt(s1);
s1++;
break;

default:
break;
}
}
else
op = 0;


switch (op) {
case 0:
case ')':
case ']':
case '}':
n = evalPower(oldn2, n, oldop2);
n = evalProduct(oldn1, n, oldop1);
n = evalSum(oldn0, n, oldop0);
return n;

case '!':
case '#':
n = evalFact(n, op);
break;

case 'r':
case 'R':
n = readNum(s);
n = evalRand(op, n);
break;

case '^':
n = evalPower(oldn2, n, oldop2);
oldn2 = n;
oldop2 = op;
break;

case '*':
case '/':
case '%':
n = evalPower(oldn2, n, oldop2);
oldop2 = 0;
n = evalProduct(oldn1, n, oldop1);
oldn1 = n;
oldop1 = op;
break;

case '+':
case '-':
n = evalPower(oldn2, n, oldop2);
oldop2 = 0;
n = evalProduct(oldn1, n, oldop1);
oldop1 = 0;
n = evalSum(oldn0, n, oldop0);
oldn0 = n;
oldop0 = op;
break;
default:
break;
}
}
return n;
}

public BigInteger readNum(String s) {
BigInteger n = new BigInteger("0");

olds1 = s1;
while (s1 < s.length() && Character.isDigit(s.charAt(s1)))
s1++;
n = new BigInteger(s.substring(olds1, s1));

return n;
}


}