Can discrete logarithms / factoring be done in P (i.e., deterministic polynomial time)?

[Raman]

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 a²+b² = 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² ≡ 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 = 2^st, 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 non-residue (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^-1D^m)^2[sup]s-i[/sup] ≡ -1 (mod p):
m := m + 2^i-1 {mod 2ⁱ}
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 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^-13^m)^2[sup]16-i[/sup] ≡ -1 (mod 65537):
m := m + 2^i-1 {mod 2ⁱ}
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 ≥ 10²⁰. Or may be has no prime factors ≥ 10⁴⁰??
as follows as:
a^m ≡ 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 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 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 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 NP-complete problems, and then Discrete Logarithm problem is harder and then less interesting than Factoring problem.

[CRGreathouse]

'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.