We’re pretty sure that classical computers can’t break RSA (because it is hard to factor large numbers on them), but we know tha
t quantum computers theoretically could. In this question, we will prove a fact that is a key part of Shor’s Algorithm, a quantum algorithm for factoring large numbers quickly1 . Let N = pq where p,q are primes throughout this question. (a) Prove that, for all a ∈ N, there are only four possible values for gcd(a,N). (b) Using part (a), prove that, if r 2 ≡ 1 mod N and r 6≡ ±1 (mod N) (i.e. r is a "nontrivial square root of 1" mod N), then gcd(r −1,N) is one of the prime factors of N. Hint: r2 = 1 mod N can be rewritten as r2 −1 = 0 mod N or (r +1)(r −1) = 0 mod N.
1 answer:
You might be interested in
Answer: The correct option is second, i.e., x>0.
Explanation:
As we know that the domain is the set of all possible inputs. If function is defined as, f(x) then all possible value of x for which the function f(x) is defined is called domain.
In a graph the domain is defined on the x axis and the range of the function is defined on y-axis.
In the given graph the function is defined from x=0 to because for
the graph is not defined. It means for
the function is not defined.
Sicen the graph is defined for all positive values of x, therefore the domain of the function is al real number greater than 0. It can be written as x>0 and the second option is correct.