You are correct.  I fixed it in both posts.  Also, the sieve would require a huge amount of space for it, and I barely understand the concepts in a sieve like this.  The idea of this thread was to create better alternatives for the current algorithms, so what are your ideas to make it faster?

The amount of bits can be seen by 2^n where 'n' is the amount of bits a number is.
8-bit: 2^8=256
16-bit: 2^16=65536
etc...

EDIT: The result refers to the largest possible number that the bit can hold.

Quote

Computing phi(n) is polynomial-time equivalent to factoring n. It is generally accepted that the two problems are equally hard.

"equally hard" in the sense of "the only way we know HOW to find phi(n) is to factor n, hence, they take the same amount of time". But i'm suggesting to find a different way to find phi(n)

"Equally hard" as in find phi(n) would allow us to factor n too.

The idea of this thread was to create better alternatives for the current algorithms, so what are your ideas to make it faster?

A new algorithm that is asymptotically faster than the NFS would be a monumental achievement. The top researchers in the field have been working on it for a couple decades now, and so far no they've had no luck.
If you want to start building  a new algorithm, its best to look at the current ones first. In case anyone is interested, here is a summary of the Quadratic Sieve, the (slower) predecessor to the NFS. It uses the same ideas, but is much, much simpler (no prime ideals, rings of algebraic integers, etc., just good old integers!).

The Quadratic Sieve
Let n be the number we are attempting to factor. The gist of the QS (and the NFS) is to find x^2 = y^2 (mod n) with x and y integers. Then we may compute gcd(x - y, n) and gcd(x + y, n), which each has a high probability of being a nontrivial factor of n.
But how do we find such x and y? That is what the algorithm does.
We define a factor base F = {p_1, p_2, ... p_k} to be the set of all primes less than or equal to some predetermined bound B. Let f(x) = x^2 - n. Let I be the set of integers contained in the interval [sqrt(n), sqrt(n) + M] for some predetermined bound M. Finally, we say that an integer m in I is smooth over F if all prime factors of m are in F.
Step 1: Sieving
The sieving step tries to find k integers a_1, a_2, a_3, ... a_k in I such that f(a_i) is smooth over F for all i = 1, 2, ... k. It works as follows:
*Initialize an array T to the values of f(a), where a is in the interval I.
*For each prime p in F:
    *Find solutions x0, x1 to the congruence x^2 = n (mod p) using the Shanks-Tonelli algorithm.
    *Divide the elements of T corresponding to x0 + t * p, x1 + t * p (t is an integer) by the largest value of p that divide them. Note that since
      x0, x1 satisfy x^2 = n (mod p), f(x0 + t * p) and f(x1 + t * p) are divisible by p. Indeed, the are the only elements of T divisible by p.
*Store the values of f corresponding to those elements of T that are now 1 into an array R. The elements of R are precisely those values of f(a) that
  are smooth over F.
Step 2: Linear algebra
*We now have {a_1, a_2, ... a_k} with f(a_i) smooth over F. We want to find a subset of the f(a_i) such that their product is a square.
*To so, write f(a_i) = p_1^e_i1 * p_2^e_i2 * ... * p_k^e_ik. Associate with a_i the binary vector A_i = (e_i1 % 2, e_i2 % 2, ... e_ik % 2). If we can 
  find a binary vector (c_1, c_2, ... c_k) such that sum (c_i * A_i) = (0, 0, 0, ...0) mod 2, we'd have our subset. This is because the product of the
  a_i corresponding to those c_i that are 1 would have the property that the exponent of each p_i is even.
*Now let the matrix A = [A_1, A_2, ...A_k] (we are placing the column representations of the A_i side by side to form A). A moment's thought shows
  that finding the c_i corresponds to solving the system A * C = 0. This is a well known problem from linear algebra, and can be solved with Gaussian 
  elimination or the Lanczos algorithm.
*When all is said and done, we have our subset of the a_i. Call these {b_1, b_2, ... b_m}.
Step 3: Finding x and y
*We simply let x = b_1 * b_2 * ... * b_m and y = sqrt(f(b_1) * f(b_2) * ... * f(b_m)). By the definition of the b_i and f, y is an integer, and x^2 =
  y^2 (mod n)
*We have x and y, so we can factor n!

You are correct Mapar007, AFAIK.

@bwang.  Thank you for explaining that, I think the quadratic sieve will help.  quick question,though.  Do you mind explaining what the difficult part or what part takes the most time is? eg. why is it ineffective?

Thank you Bwang, for that information.

I thought about a recursive algorithm that finds the factors, but have no idea how it would be done.  It would stop once it found p or q, but where to start.  Obviously, we are talking about integers, here. (eg, not decimals or fractions)  Any ideas?

So can the matrix be done over a network type thing?  Can you explain Tonelli-Shanks algorithm or give a link to a better article than wikipedia?

Basically, though, if we could solve the matrix over a network of computers, would it be more efficient for these numbers? eg. not take forever?

You have no idea how they work, and yet you host a grid.  Wow.  Wait, grid?  what Grid?

Anyway, yeah, so what did you think of the recursive idea? Is it possible?

Either I am a genius or I entirely misunderstand the concept of factoring but I managed to yesterday crack a 32 bit key on my calculator under a second. I think I entirely misunderstand the whole RSA encryption technology

well if I am back home (where I have boinc) I'll usrely support the project.