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 SieveLet 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: SievingThe 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!
Show Posts
We need more of these.