Factorization of N=pq are partially in P

簡単な証明

Hypothesis

　N=pq　 p and q are large prime respectively.

R=q/p q > p R is very close to an small integer or a simple rational number.

N=pq can be factorized in time polynomial

Proof

point[p, q] is on y=N/x

y=N/x and y=Rx cross at point[p, q]

N is n digit

upper 2 digits N2 round off the 3rd digit

upper 4 digits N4 round off the 5th digit

y=N2/x and y=Rx cross at point[p2,q2]

y=N4/x and y=Rx cross at point[p4, p4]

We only know N.

Let line up candidates point[p2,q2] and point[p4,q4]

N2 < 99 i=1..10 j=1..10

R2=i/j

f2=N2/R2 - j^2

dn2=abs(N2-R2*j^2)

N4 < 9999 i=1..99 j=1.. sqrt(N4)

R4=i/j

f4=N4/R4 - j^2

dn4=abs(N4-R4*j^2)

Point[j, i] that have small f2 and dn2 can be nominated as candidate for point[p2, q2]

Point[j, i] that have small f3 and dn4 can be nominated as candidate for point[p4, q4]

Find cross point[px, qx] of y=R2x and y=N/x , y=R4x and y=N/x

Find the nearest prime pn for px and the nearest prime qn for qx

pn*qn=N bingo!

Number of candidates are finit.

You can factorized N=pq in time polynomial.

Q.E.D.　?