Mittwoch, 30. September 2015
An heuristic argument why factoring is difficult
Let n=pq be the prime decomposition of n and let n=2e.
Let us suppose that p=q=√n.
Let pn be the probability to have a number 1≤x≤n
with 1<gcd(x,n)<n and as such to also have a non-trivial factor of n.
Then we have
pn=1−ϕ(n)n=1−∏p|n(1−1p)=1−(1−1p)(1−1q)
=1−(1−1√n)2=1−(1−1√2e)2
Suppose there exists a factoring-algorithm which runs in polynomial time f(e) and
which draws a number x at every step and computes gcd(x,n).
Let X be the number of numbers x with 1<x<n and 1<gcd(x,n)<n which the algorithm
finds after f(e) steps. Then by definition of the algorithm we must have
1=P(X≥1)
But on the other hand we have
P(X≥1)=1−P(X=0)=1−(1−pn)f(e)
=1−(1−1√2e)2⋅f(e)
The last equality is by definition of the algorithm valid for every e.
But for e→∞ we have
1=P(X≥1)=1−(1−1√2e)2⋅f(e)→e→∞0
hence for e→∞ we have the contradiction 1=0.
Abonnieren
Kommentare zum Post (Atom)
Keine Kommentare:
Kommentar veröffentlichen