

Thread Tools 
20160523, 03:06  #1 
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
3×419 Posts 
Can discrete logarithms / factoring be done in P (i.e., deterministic polynomial time)?
To start with an introduction, I reviewed the algorithm for computing Square Roots modulo a prime in the book of Crandall and Pomerance, for primes ≡ 1 (mod 4), it is the part which isn't quite obvious, so it was the part which I did not understand or skipped when I was younger, approximately nine years back.
For example, to write a prime p ≡ 1 (mod 4) as the sum of two squares, (primes ≡ 3 (mod 4) cannot be written as the sum of two squares) we have d^{(p1)/2} ≡ 1 (mod p), such that where d is a quadratic nonresidue (mod p). So, d^{(p1)/4} ≡ √1 (mod p). So, doing GCD(d^{(p1)/4}+i, p) (mod p) will certainly give away the real parts and the imaginary parts as a and b, such that where a^{2}+b^{2} = p. Modular square roots can be done in P for prime modulo; but for composite modulo, it is equivalent to factoring. We need to compute the square roots for each of the prime factors of the composite number and then glue them by using the Chinese Remainder Theorem. No algorithm in P for factoring is currently known. So, turning back to the problem for computing the square roots modulo a prime, x^{2} ≡ a (mod p) If p ≡ 3 (mod 4), then x ≡ a^{(p+1)/4} (mod p). If p ≡ 5 (mod 8), then a^{(p+3)/8} ≡ √±a (mod p). If a^{(p+3)/8} ≡ √a (mod p), then x ≡ 2^{(p1)/4}a^{(p+3)/8} (mod p), else x ≡ a^{(p+3)/8} (mod p). If p ≡ 1 (mod 4), then let p1 = 2^{s}t, such that where t is odd. So, the group order of a^{t} (mod p) is exactly a divisor of 2^{s}. If d is a quadratic nonresidue (mod p), then a^{t} must be an even power of d^{t} (mod p). So, if a^{t} ≡ (d^{t})^{m} (mod p), such that where m is even and t is odd, then a^{t}(d^{t})^{m} ≡ 1 (mod p). a^{t+1}(d^{t})^{m} ≡ a (mod p). So, x ≡ √a ≡ a^{(t+1)/2}(d^{t})^{m/2} (mod p). So, we will have to find a value of m such that A ≡ D^{m} (mod p), such that where A ≡ a^{t} (mod p) and D ≡ d^{t} (mod p). Since the group order of A (mod p) and mainly D (mod p) are exactly a power of two, we can certainly be able to solve this discrete logarithm problem in P, as follows as: A ≡ D^{m} (mod p) m := 0 for i in 1 to s do: if (A^{1}D^{m})^{2[sup]si}[/sup] ≡ 1 (mod p): m := m + 2^{i1} {mod 2^{i}} end if end for return m So, I understand that we would be able to compute discrete logarithms in P modulo primes p such that where φ(p) = p1 is exactly a power of two. As a note, φ(N) is exactly a power of two, (such that where N is either prime or composite), if and only if N is the number of sides of a constructible polygon, i.e. a power of two times 4 or product of one or more distinct Fermat primes. Indeed, I had verified that by using PARI/GP that it was possible to compute 3^{m} ≡ 5 (mod 65537), within only 16 steps, as follows as: 3^{m} ≡ 5 (mod 65537) m := 0 for i in 1 to 16 do: if (5^{1}3^{m})^{2[sup]16i}[/sup] ≡ 1 (mod 65537): m := m + 2^{i1} {mod 2^{i}} end if end for return m Indeed, I did realize that it would be computationally feasible to compute discrete logarithms (mod p), if p1 is smooth, i.e. has no prime factors ≥ 10^{20}. Or may be has no prime factors ≥ 10^{40}?? as follows as: a^{m} ≡ b (mod p) m := 0 t := p1 while t > 1 do: let q be the smallest prime factor of t find out the value of k, 0 ≤ k ≤ q1, such that (ba^{m})^{t/q} ≡ (a^{(p1)/q})^{k} (mod p) then m := m + k(p1)/t {mod (p1)q/t} t := t/q end while return m So, when q is small, such that where q is a prime factor of p1, then Finding out the value of k, 0 ≤ k ≤ q1, such that (ba^{m})^{t/q} ≡ (a^{(p1)/q})^{k} (mod p) can be computationally feasible by using brute force, Pollard's Rho method for discrete logarithms, Baby Steps Giant Steps or Index Calculus method. Question: Does anyone have an idea if k can be computed in P time if q is large, or bit by bit by using some divide and conquer approach of factoring q1, etc.?? Or the N+1 smooth group structure like those of the Fibonacci or the Lucas group structures, or the Elliptic Curve group structure, etc.?? Computing the discrete logarithms for a composite modulo is equivalent to factoring; otherwise we do have the Pohlig Hellman algorithm. That said, factoring a composite number N, P time reduces to discrete logarithm problem as follows as: Finding out the smallest value of m > 0 such that a^{m} ≡ 1 (mod N). m must be a divisor of φ(N). For some value of a, m must be φ(N). Once, we have the value of φ(N), we can compute the ladder a^{φ(N)} (mod N), a^{φ(N)/2} (mod N), a^{φ(N)/4} (mod N), a^{φ(N)/8} (mod N), ..., a^{φ(N)/2[sup]k}[/sup] (mod N). If a^{φ(N)/2[sup]k}[/sup] ≡ 1 (mod N) and a^{φ(N)/2[sup]k+1}[/sup] ≠ ±1 (mod N), then we can certainly be able to extract the factors of N with GCD(a^{φ(N)/2[sup]k+1}[/sup]±1, N) (mod N). Alternatively, by using the discrete logarithms, if we were able to find out the smallest value of m such that where a^{m} ≡ a^{N} (mod N), then Nm must be a divisor of φ(N), and for some value of a, we must have Nm = φ(N). For a semiprime N = pq, so we must have the value of the prime factors of the composite number N, p and q, such that, where a^{N} ≡ a^{pq} (mod N), and a^{N+1} ≡ a^{p+q} (mod N). So, we easily know the values of a^{pq} (mod N), and a^{p+q} (mod N). Further more, so we must have the value of the prime factors of the composite number N, p and q, such that, where a^{N} ≡ a^{q} (mod p), and a^{N} ≡ a^{p} (mod q). Both of Factoring problem and Discrete Logarithm problem are in BQP by using Shor's quantum computing algorithm. So, if Discrete Logarithm problem is in P, and if BQP is contained inside NP or BQP = P, then there is a good chance that Factoring Problem is in P, since both of Factoring problem and Discrete Logarithm problem are not NPcomplete problems, and then Discrete Logarithm problem is harder and then less interesting than Factoring problem. 
20160523, 13:44  #2 
Aug 2006
5,987 Posts 
'Everyone' expects that factoring and discrete log are NPintermediate, that is, in NP but outside P. BQP is expected to neither contain nor be contained in NP. I don't think anyone seriously thinks that BQP is in BPP let alone P.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Semiprimes factoring. Is deterministic? What is computational complexity?  Alberico Lepore  Alberico Lepore  43  20170610 15:42 
Cyclotomic Polynomial Factoring methods  mickfrancis  Factoring  2  20150111 18:31 
Software for discrete logarithms  Lakshmi  Factoring  10  20131216 20:27 
Having a hard time finding a polynomial for a C138  YuL  Msieve  3  20131130 03:16 
AKS  A polynomialtime algorithm for testing primality.  Maybeso  Math  11  20021120 23:39 