mersenneforum.org Can discrete logarithms / factoring be done in P (i.e., deterministic polynomial time)?
 Register FAQ Search Today's Posts Mark Forums Read

 2016-05-23, 03:06 #1 Raman 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(p-1)/2 ≡ -1 (mod p), such that where d is a quadratic non-residue (mod p). So, d(p-1)/4 ≡ √-1 (mod p). So, doing GCD(d(p-1)/4+i, p) (mod p) will certainly give away the real parts and the imaginary parts as a and b, such that where a2+b2 = 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, x2 ≡ 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(p-1)/4a(p+3)/8 (mod p), else x ≡ a(p+3)/8 (mod p). If p ≡ 1 (mod 4), then let p-1 = 2st, such that where t is odd. So, the group order of at (mod p) is exactly a divisor of 2s. If d is a quadratic non-residue (mod p), then at must be an even power of dt (mod p). So, if at ≡ (dt)m (mod p), such that where m is even and t is odd, then at(d-t)m ≡ 1 (mod p). at+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 ≡ Dm (mod p), such that where A ≡ at (mod p) and D ≡ dt (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 ≡ Dm (mod p) m := 0 for i in 1 to s do: if (A-1Dm)2[sup]s-i[/sup] ≡ -1 (mod p): m := m + 2i-1 {mod 2i} 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) = p-1 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 3m ≡ 5 (mod 65537), within only 16 steps, as follows as: 3m ≡ 5 (mod 65537) m := 0 for i in 1 to 16 do: if (5-13m)2[sup]16-i[/sup] ≡ -1 (mod 65537): m := m + 2i-1 {mod 2i} end if end for return m Indeed, I did realize that it would be computationally feasible to compute discrete logarithms (mod p), if p-1 is smooth, i.e. has no prime factors ≥ 1020. Or may be has no prime factors ≥ 1040?? as follows as: am ≡ b (mod p) m := 0 t := p-1 while t > 1 do: let q be the smallest prime factor of t find out the value of k, 0 ≤ k ≤ q-1, such that (ba-m)t/q ≡ (a(p-1)/q)k (mod p) then m := m + k(p-1)/t {mod (p-1)q/t} t := t/q end while return m So, when q is small, such that where q is a prime factor of p-1, then Finding out the value of k, 0 ≤ k ≤ q-1, such that (ba-m)t/q ≡ (a(p-1)/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 q-1, 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 am ≡ 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 am ≡ aN (mod N), then N-m must be a divisor of φ(N), and for some value of a, we must have N-m = φ(N). For a semi-prime N = pq, so we must have the value of the prime factors of the composite number N, p and q, such that, where aN ≡ apq (mod N), and aN+1 ≡ ap+q (mod N). So, we easily know the values of apq (mod N), and ap+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 aN ≡ aq (mod p), and aN ≡ ap (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 NP-complete problems, and then Discrete Logarithm problem is harder and then less interesting than Factoring problem.
 2016-05-23, 13:44 #2 CRGreathouse     Aug 2006 5,987 Posts 'Everyone' expects that factoring and discrete log are NP-intermediate, 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Alberico Lepore Alberico Lepore 43 2017-06-10 15:42 mickfrancis Factoring 2 2015-01-11 18:31 Lakshmi Factoring 10 2013-12-16 20:27 YuL Msieve 3 2013-11-30 03:16 Maybeso Math 11 2002-11-20 23:39

All times are UTC. The time now is 12:53.

Sun Jan 29 12:53:20 UTC 2023 up 164 days, 10:21, 0 users, load averages: 1.70, 2.56, 2.20