Factoring Large Numbers: Challenges and Solutions

[damoclark]

CAn anybody help me with this problem.

I am trying to factor $$2^{128}+16+1$$

My version of MATLAB can't handle such big numbers, although I have managed to find some small factors. The problem is the larger factors, of which I don't know whether are even prime. If anyone has a good factoring program they can run this number through, I would really appreciate that.

Any help or suggestion on the best way to factor integers of order of $$10^{30}$$ to $$10^{40}$$ would be great.

 

[robert Ihnot]

I get almost immediately 3x7x13x461x7848923x344481421025753789822679967. Is that any help?

 

[Data]

And all those are indeed prime (at least according to Maple!)

 

[damoclark]

I get almost immediately
3 x 7 x 13 x 461 x 7848923 x 344481421025753789822679967. Is that any help?

That is very helpful, thanks. I was wondering if all the factors could be written down as nth primes, for example 7 is equal to the fourth prime.

I guess that 344481421025753789822679967 can't be written down as an nth prime, as the number of prime numbers under this number is unknown.
Is this correct?

Would someone know the largest value of x for which pi(x) is known, where
pi(x) is the prime counting function, or the most computationally effiecient way of calculating it, without knowledge of all the lesser primes.

Also how can I be so sure that 344481421025753789822679967 is prime?
Is there such a way to be totally sure, as there is when it nends to be demonstrated that a number isn't prime (ie , by finding a factor). It's not that I don't trust computers, but it would nice, given some extra addiational information that maybe a computer could generate, to be able to verify it is prime with pen and paper.

 

[saltydog]

Would someone know the largest value of x for which pi(x) is known, where
pi(x) is the prime counting function, or the most computationally effiecient way of calculating it, without knowledge of all the lesser primes.

There's lots of efficient ways to approximate pi(x) which asymptotically approaches the true value. Check out Mathworld on the net. To me, since there is no known way of "predicting" the next prime, then there would be no known way of calculating pi(x) (exactly) without prior knowledge of the primes before it.

Also how can I be so sure that 344481421025753789822679967 is prime? Is there such a way to be totally sure, as there is when it nends to be demonstrated that a number isn't prime (ie , by finding a factor). It's not that I don't trust computers, but it would nice, given some extra addiational information that maybe a computer could generate, to be able to verify it is prime with pen and paper.

There's some methods which give a "very high level" of confidence the number is prime (I'd have to google too), I think based on Fermat's little theorem. But I think the only "guaranteed" method is brute force factoring.

Finally, check out "PARI" on the net. If you're into Number Theory, you'll love PARI. It's extremely efficient. I've used it for work on RSA.

 

[shmoe]

Would someone know the largest value of x for which pi(x) is known, where pi(x) is the prime counting function, or the most computationally effiecient way of calculating it, without knowledge of all the lesser primes.

You could check Andrew Odlyzko's webpage. He has a few papers on the topic. I think calculations have been done up to the 10^20 range, look for work by Marc Deleglise and Joel Rivat. I don't really follow computational number theory closely, so there may be much better results out there.

Also how can I be so sure that 344481421025753789822679967 is prime?
Is there such a way to be totally sure, as there is when it nends to be demonstrated that a number isn't prime (ie , by finding a factor). It's not that I don't trust computers, but it would nice, given some extra addiational information that maybe a computer could generate, to be able to verify it is prime with pen and paper.

If you don't trust maples "very probably prime" report, you can use primo, which declares it to be prime (this is a guarantee, not a probabilistic algorithm).

 

[shmoe]

To me, since there is no known way of "predicting" the next prime, then there would be no known way of calculating pi(x) (exactly) without prior knowledge of the primes before it.

This is false. You don't have to compute all the primes less than x to find pi(x) exactly. For example, you can compute $$\pi(x)-\pi(x^{1/2})$$ by inclusion-exclusion and knowing only those primes less than $$x^{1/2}$$ (dates back to Legendre). Essentially you are counting integers between x^(1/2) and x that aren't divisible by any primes less than x^(1/2).This isn't the most efficient of methods but the moral is you don't need to know all the primes less than x to find pi(x).

 

[saltydog]

This is false. You don't have to compute all the primes less than x to find pi(x) exactly. For example, you can compute $$\pi(x)-\pi(x^{1/2})$$ by inclusion-exclusion and knowing only those primes less than $$x^{1/2}$$ (dates back to Legendre). Essentially you are counting integers between x^(1/2) and x that aren't divisible by any primes less than x^(1/2).This isn't the most efficient of methods but the moral is you don't need to know all the primes less than x to find pi(x).

Oh Jesus. Sorry about that damoclark. Next time I'll try to remember to make sure before I say anything. Thank you shmoe for correcting that even though it's embarrassing for me. I've since learned you don't need to know any of the primes to calculate pi(n). Here's one from MathWorld for my education:

$$\pi(n)=-1+\sum_{j=3}^{n}((j-2)!-j Floor[\frac{(j-2)!}{j}]$$

It will get into multi-precision with the factorials with large n. There's some other ones. Think I should spend time reviewing . . .

 

[damoclark]

Thanks for the links Shmoe, and salthydog for the reference to PARI

Can I calculate Pi(344481421025753789822679967) practically, though?
where Pi(x) is the prime counting function.
From the methods I've looked at, I figure I would need a powerful computer and about 1 million years of free time to do the calculation.

To calculate Pi(x) for large x, it it entirely possible that no short cuts actually exist, its either, do zillions of computations or have some huge data-base of relevant information, to look up.

 

[saltydog]

Thanks for the links Shmoe, and salthydog for the reference to PARI

Can I calculate Pi(344481421025753789822679967) practically, though?
where Pi(x) is the prime counting function.
From the methods I've looked at, I figure I would need a powerful computer and about 1 million years of free time to do the calculation.

To calculate Pi(x) for large x, it it entirely possible that no short cuts actually exist, its either, do zillions of computations or have some huge data-base of relevant information, to look up.

Let's see damoclark . . . don't want to say anything incorrect. Well, according to Mathworld, Gourdon has the record for pi(10^22). I know Gourdon (indirectly). He's an ace with intensive calculations like that. He wrote PIFAST, a very efficient program for calculating the digits of pi and other numbers. So my claim: If Gourdon can only get to 10^22, then there is no quick way to calculate it.

Also, why are you working on that problem?

 

[damoclark]

Also, why are you working on that problem?

I will try to explain my problem which prompted me to ask the original question.

The question that I originally possed, came up while I was working on a problem to do with the stucture of numbers.

Where as in binary you can represent any integer, with a sequence of two symbols, those being zero and one, if you know the factorisation of a number it is possible to represent it with a geometric arrangemnet of one symbol, that being 1, where that arrangemnat has the structure of a particular geometric object. When I started rotating these object by 180 degrees, the number they represented shifted to another number, sometimes a rotation of 360 degrees did not bring the object to it's original state.

I took the number 93, represented it by a geometric object, rotated that object by 540 degrees, unfortunately to be able to write down the resulting object I have to know :
Pi(344481421025753789822679967),(where Pi(x) is the prime counting function), which is one of the factors of
$$2^{128}+16+1$$.

From your responses,thanks, I can see that I won't be able to calculate
Pi(344481421025753789822679967), This number is 1000 times bigger than the largest x for which Pi(x) is known. So I figure when computer are 1000 times more powerful than they are today, which by Mores law will be in about 15 years time, it should be able to be calculated...

I guess I'll move on to the next number, 94...

 

[saltydog]

where that arrangement has the structure of a particular geometric object

Well, that sounds very interesting. Could you elaborate further or perhaps give me a topic name I could search the web for? If it's related to work you're doing with factoring and wish not to I'd quite understand.