Browse Groups

• ## Re: [PrimeNumbers] some composite can be broken down into key factors

(3)
• NextPrevious
• Jane, ... One French lawyer taught us that if a number N has two factors P and Q, which are not too far from each other, we only need to calculate A =
Message 1 of 3 , Mar 25, 2011
View Source
Jane,

Jane asked for a demonstration when ric.judor wrote:
> > i can find a factor of any composit numbers that satisfy n =p*q
> > ,p>q , p-q < sqrt (p)
>
> Oh good. Perhaps you'd like to factor this one for us:
> 2203353588507632689540389884099234780425798106022737554148425561277092513841358286596173426627853446495163308636257511927689252306411

One French lawyer taught us that if a number N has two factors
P and Q, which are not too far from each other, we only need
to calculate A = ceil(sqrt(N)) and get the factors immediately
as P = A + sqrt(A^2 - N) and Q = A - sqrt(A^2 - N). The "not
too far from each other" condition basically asks for the
difference of (P-Q) to be bounded (if I recall correctly) by
sqrt(8)N^(1/4).

Now, I claim that Ric's condition of (p-q) < sqrt(p) is
actually stronger than this. If it wasn't so, we'd have
sqrt(p) >= sqrt(8)N^(1/4), which implies p >= 64*q. Then,
however p - q >= (63/64)p > sqrt(p), a contradiction.