Loading [MathJax]/jax/output/HTML-CSS/jax.js

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 1xn 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=1p|n(11p)=1(11p)(11q) =1(11n)2=1(112e)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(X1) But on the other hand we have P(X1)=1P(X=0)=1(1pn)f(e) =1(112e)2f(e) The last equality is by definition of the algorithm valid for every e. But for e we have 1=P(X1)=1(112e)2f(e)e0 hence for e we have the contradiction 1=0.

Keine Kommentare:

Kommentar veröffentlichen