What is the prime factorization of
41255343611606411138375939231366289694834484056313057861768858811487469868878228474624914246929660996278138235634617497458296590997620930003

It is likely to split into 2 primes with the smaller prime containing
at least 40 digits (based on my own efforts to factor this number).

---

Clarification of Question by shadowgate-ga on 22 Aug 2002 21:04 PDT

I've already tried factoring the number with the elliptic curve
method. I ran 1800 curves B1=1e6, 5100 curves B1=3e6, and 7000 curves
B1=11e6. Thus it is
unlikely the number contains a factor of less than about 43 digits.
Further, this number has no special properties making it amenable to
the special number field sieve. Therefore, any factorization is likely
to require GNFS.

As philip_lynx points out a GNFS on this number would take significant
computing power. But note his estimate of 3 years is for a single CPU.
Numbers of this size can be factored with small clusters of machines
in under a month.

Hi shadowgate,

this is a 463 bit number. Assuming it contains exactly two prime
factors (which I am virtually sure of), you are asking someone to
spend about 3 CPU years (at least) on this problem. Curiosity arises:
Where did you get the number from?

You may want to have a look at:
http://www.iaeste.dk/~henrik/projects/nfsnet.html

Also, did you consider to acquire the GNFS software that was used for
the RSA-155 challenge?

Good luck,

   Philip

just as an excercize in futility, i'm trying to factor this number
using a BASH script with bc (command line calculator) on a 486

i can tell you that it's larger than 6374

at this rate i should have an answer in
428917496440252629712552703040046760972986210464782978825852513198420850995980949948691625360032572675496941675135962204613375408563
years!

I wouldn't have typed in that number for $3.  Good luck.

This might be the answer to your question?
I am posting this also for tohers interested to read

"POLYNOMIAL TIME PRIME NUMBER TESTING ALGORITHM"
http://www.cse.iitk.ac.in/news/primality.html
http://slashdot.org/articles/02/08/07/0151216.shtml?tid=172

Unluckily tne's comment does not answer shadowgate's question, because
he already knows that the number is composite. There is no need to run
a primality test for the number above.

For the curious, if a^(n-1) != 1 (mod n) the number n is not prime
(the converse is not true).

The exponentiation can be done in about 1.3(log n/log 2)
multiplications using the binary exponentiation method.

Taking a=3 and n the number posted by shadowgate we obtain in a
fraction of second:

a^(n-1) =
3796477839673969003690140114661459934350723235127945290770617\
3851937432211158970815302259003086016178126090007991341518025\
807031118310589718 (mod n)

so the number is composite (the symbol \ indicates that the number
continues in the following line.

hi alpetron

n|(a^(n-1) - 1) if n fails this n is not prime but if passes it maybe prime

I assumed it passes this and it was probably a prime

Thanks for pointing out my mistake.

I did implement this C++ code but was lazy to implement for large numbers.


# include <iostream.h>

int power(int x,int n) {
	if(n<=0) return 1;
	if(n==1) return x;
	int temp = power(x,n/2);
	return (temp * temp * power(x,n%2) );
}


int main() {
	cout << power(3,5) << endl;
	return 0;
}

tne,

For this kind of tasks it is better to start with a program that
handles big numbers. I use UBASIC, that you can download for free on
Internet.

Another possibility is to test it online. Just use my factorization
applet located at:

http://www.alpertron.com.ar/ECM.HTM

Just copy and paste the number on the applet and it will tell you that
the number is composite, then it will start factoring it. Since this
number is very difficult to factor (otherwise shadowgate would not
have posted it here) the applet will not finish execution in a short
period of time.

I hope this helps.

thanks alpetron i might try that

Hi shadowgate,
  I was just wondering if you succeeded in factoring this number
eventually. I'm trying to factor a bigger number and I'd like to test
my programs on this number once I implement them. This was 2 years ago
so I don't know if you still check this email... but if you (or anyone
else) have any comments to share about your successes (or failures)
that would be helpful. Thanks.

Yes the number was factored, the factors were:

1771052383785311834993979061208604132871538232335055323 *
716004722254150586483843313158263592817803974805568194113667109128698119199668739510916110374031

The factorization was performed by Kruppa and Leyland using
the GNFS.

chiyosdad-ga post your number here and any other info you can
give about it.  However if it is much larger than mine was
you need to hope for either a special form to the numebr or
that it as a factor with less than 50 digits that might be
found by ECM (elliptic curve method).

See also: http://www.loria.fr/~zimmerma/records/ecmnet.html