Loading ...
Sorry, an error occurred while loading the content.

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

Expand Messages
  • Peter Kosinar
    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
    • 0 Attachment
      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.

      Since your number doesn't seem to admit the factorization
      described above, I believe it doesn't satisfy his inequality.
      Or maybe I overlooked something?

      Peter

      --
      [Name] Peter Kosinar [Quote] 2B | ~2B = exp(i*PI) [ICQ] 134813278
    Your message has been successfully submitted and would be delivered to recipients shortly.