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

How to specify the digit of factor?

Expand Messages
  • siwei_mu
    Hi, all, I refer to a guide called: Beginners Guide to NFS factoring using GGNFS and MSIEVE (http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html) AND
    Message 1 of 2 , May 4, 2011
    • 0 Attachment
      Hi, all,

      I refer to a guide called:
      Beginners Guide to NFS factoring using GGNFS and MSIEVE
      (http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html)
      AND
      MSIEVE and GGNFS in Combination using PYTHON (factmsieve.py)
      (http://gladman.plushost.co.uk/oldsite/computing/factoring.php)
      and successfully factorize several numbers.

      Now I have a project£º

      Given a number, like:
      1010646509523626909471007838658716275297171202169082755460653497731277859829955377460426014100492764686887

      And after calculation, the two prime factors should be :
      r1=23998563736897718596683178098390962435026361950437211 (pp53)
      r2=42112791440504457422110905563891953193367924242081317 (pp53)

      which means the given number can be factorize into two same digit prime. And I am always given numbers like this. What I need to do is only factorize them into two same digit prime.

      Do I have any approach or command to do it quickly?

      Thank you for your attention!
    • Jason Papadopoulos
      ... When the number is large enough, there is no method known for factoring integers that - takes advantage of the factors having the same number of bits - is
      Message 2 of 2 , May 5, 2011
      • 0 Attachment
        > which means the given number can be factorize into two same digit prime.
        > And I am always given numbers like this. What I need to do is only
        > factorize them into two same digit prime.
        >
        > Do I have any approach or command to do it quickly?

        When the number is large enough, there is no method known for factoring
        integers that

        - takes advantage of the factors having the same number of bits
        - is faster than the number field sieve

        If the factors are extremely close together (i.e. not only the same
        size but many of the top bits of each factor are identical), then
        possibly a variant of Fermat's or Lehman's method can find them more
        quickly, but such numbers make terrible RSA keys for this reason and
        a good RSA key will never have this form.

        Otherwise, NFS is unfortunately the best we can do.

        jasonp
      Your message has been successfully submitted and would be delivered to recipients shortly.