mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2016-05-23, 03:06   #1
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3·419 Posts
Default 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.
Raman is offline   Reply With Quote
Old 2016-05-23, 13:44   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

'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.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Semiprimes factoring. Is deterministic? What is computational complexity? Alberico Lepore Alberico Lepore 43 2017-06-10 15:42
Cyclotomic Polynomial Factoring methods mickfrancis Factoring 2 2015-01-11 18:31
Software for discrete logarithms Lakshmi Factoring 10 2013-12-16 20:27
Having a hard time finding a polynomial for a C138 YuL Msieve 3 2013-11-30 03:16
AKS - A polynomial-time algorithm for testing primality. Maybeso Math 11 2002-11-20 23:39

All times are UTC. The time now is 06:51.


Mon Nov 29 06:51:38 UTC 2021 up 129 days, 1:20, 0 users, load averages: 1.09, 1.03, 0.99

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.