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

Fermat Factoring with First Digits

Expand Messages
  • Milton Brown
    Fermat s Factoring Algorithm with the first digits of the factors known, can be done as on page 198 of Yan s book (Number Theory for Computing) with a
    Message 1 of 11 , Feb 1, 2002
    • 0 Attachment
      Fermat's Factoring Algorithm with the first digits of the
      factors known, can be done as on page 198 of Yan's book
      (Number Theory for Computing) with a different starting value of k

      k = Lower(Sqrt( n + (abc00...00)^2)) + 1

      where a, b, c are the known first digits and Lower means
      next smaller integer value.

      For his exercise 2.3.3 with n = 278153 (= 349*797)
      his k of 528 requires 45 steps, but with k = 565 requires
      only 8 steps. This is obtained with abc00...00 = 200
      where 200 = (700-300)/2.

      Milton L. Brown
      miltbrown@...



      [Non-text portions of this message have been removed]
    • Phil Carmody
      ... Anyone care to do a scan/upload so that we can see the full details? (Or transcribe) ... A where clause is usually intended to refine or clarify the
      Message 2 of 11 , Feb 1, 2002
      • 0 Attachment
        On Fri, 01 February 2002, "Milton Brown" wrote:
        > Fermat's Factoring Algorithm with the first digits of the
        > factors known, can be done as on page 198 of Yan's book
        > (Number Theory for Computing)

        Anyone care to do a scan/upload so that we can see the full details? (Or transcribe)

        > with a different starting value of k
        >
        > k = Lower(Sqrt( n + (abc00...00)^2)) + 1
        >
        > where a, b, c are the known first digits and Lower means
        > next smaller integer value.
        >
        > For his exercise 2.3.3 with n = 278153 (= 349*797)
        > his k of 528 requires 45 steps, but with k = 565 requires
        > only 8 steps. This is obtained with abc00...00 = 200
        > where 200 = (700-300)/2.

        A 'where' clause is usually intended to refine or clarify the information we are already in poseesion of.
        However, your 'where' clause explains the arbitrary selection of the number 200 in terms of an explanation which appears to have arbitrarily selected two numbers.

        I did look for a possible justification, in the loosest sense of the word, for those _two_ numbers, and all I could see was that 300 is 349 truncated, and 700 is 797 truncated.

        Does this mean that in order to help you find the factors more quickly, you need to know them, or their leading digits, in advance?

        Shall we just say that I see a dog chasing its tail here, with the current description.

        Phil

        Don't be fooled, CRC Press are _not_ the good guys.
        They've taken Wolfram's money - _don't_ give them yours.
        http://mathworld.wolfram.com/erics_commentary.html


        Find the best deals on the web at AltaVista Shopping!
        http://www.shopping.altavista.com
      • djbroadhurst
        Phil: I think that Milton was here talking about how to use leading digits, not about how to find them. In this case he was suggesting how to make the very
        Message 3 of 11 , Feb 1, 2002
        • 0 Attachment
          Phil: I think that Milton was here talking about how to
          use leading digits, not about how to find them.
          In this case he was suggesting how to make the
          very slow Fermat method slightly less slow, I guess?
          Milton seems to specialize in messages where one has to guess.
          David
        • Phil Carmody
          ... Milton s previous posts hav claimed that he can predict the leading digits. This has been called into question many times by the several people whose names
          Message 4 of 11 , Feb 1, 2002
          • 0 Attachment
            On Fri, 01 February 2002, "djbroadhurst" wrote:
            > Phil: I think that Milton was here talking about how to
            > use leading digits, not about how to find them.

            Milton's previous posts hav claimed that he can predict the leading digits. This has been called into question many times by the several people whose names all seem to begin with P. One particularly vociferous questioner has repeatedly requested a sketched algorithm, or at least some justification for the claims.

            Milton posted what appeared to be part of an algorithm, with a cite too which was appreciated. My first guess was that it was trying to be the long awaited answer to the questions. However, as you say it could not be.

            > In this case he was suggesting how to make the
            > very slow Fermat method slightly less slow, I guess?

            Haha, to be honest, if you throw a few trivial improvements into Fermat, it's not too shabby on the just-over-word-size range (where the mulmod methods start to require bignum maths vs. Fermat's adds and subs). Having said that Fermat did use some of these improvements himself, and thus didn't exactly use the technique which is presently called "Fermat's method".) Riesel demonstrates an extreme example of these trivial improvements in PNaCMfF, where the a >~12-digit number is split after one step!

            Phil

            Don't be fooled, CRC Press are _not_ the good guys.
            They've taken Wolfram's money - _don't_ give them yours.
            http://mathworld.wolfram.com/erics_commentary.html


            Find the best deals on the web at AltaVista Shopping!
            http://www.shopping.altavista.com
          • Paul Leyland
            ... To be even more fair to Fermat, it s a pretty good algorithm if you know that the composite has precisely two factors and that they differ only slightly in
            Message 5 of 11 , Feb 1, 2002
            • 0 Attachment
              > > In this case he was suggesting how to make the
              > > very slow Fermat method slightly less slow, I guess?
              >
              > Haha, to be honest, if you throw a few trivial improvements
              > into Fermat, it's not too shabby on the just-over-word-size

              To be even more fair to Fermat, it's a pretty good algorithm if you know
              that the composite has precisely two factors and that they differ only
              slightly in size.

              A case in point occurs in the 2-prime version of MPQS. Suppose a large
              prime p lies in the range B1<p<B2 and a residue after dividing by factor
              base primes (i.e all those <= B1) lies between max (B1^2, B2) and B2^2.
              A fast pseudoprimality test tells us whether it's worth attempting to
              factor the residue. In these circumstances, where B1 is typically
              2^20and B2 is, say, 2^26 Fermat's method can be quite valuable.

              I actually used Fermat for a while in PPMPQS, but we later found that
              SQFOF almost always beat it.


              Paul
            • Milton Brown
              Consider Yan s RSA example on page 318 n = 63978486879527143858831415041 if you obtain the first 7 digits of each factor as p = 1452951... and q = 4403346...
              Message 6 of 11 , Feb 2, 2002
              • 0 Attachment
                Consider Yan's RSA example on page 318
                n = 63978486879527143858831415041
                if you obtain the first 7 digits of each factor as
                p = 1452951... and
                q = 4403346... yielding
                delta/2 = 1475197...

                Spliting this value of k to 14751970...+ and 14751975...+
                between two 1 gHz machines, enables the complete
                factorization to be done on the second machine with
                y = sqrt(21762078295163316989407257600)
                to be done in 6.75 minutes.

                (The notation corresponds to Yan's Fermat Factoring p. 198)

                For anyone interested, I can provide additional documentation.
                Contact me directly.

                Milton L. Brown
                miltbrown@...

                ----- Original Message -----
                From: "Milton Brown" <miltbrown@...>
                To: <primenumbers@yahoogroups.com>
                Cc: "Milton Brown" <miltbrown@...>
                Sent: Friday, February 01, 2002 12:13 AM
                Subject: [PrimeNumbers] Fermat Factoring with First Digits


                > Fermat's Factoring Algorithm with the first digits of the
                > factors known, can be done as on page 198 of Yan's book
                > (Number Theory for Computing) with a different starting value of k
                >
                > k = Lower(Sqrt( n + (abc00...00)^2)) + 1
                >
                > where a, b, c are the known first digits and Lower means
                > next smaller integer value.
                >
                > For his exercise 2.3.3 with n = 278153 (= 349*797)
                > his k of 528 requires 45 steps, but with k = 565 requires
                > only 8 steps. This is obtained with abc00...00 = 200
                > where 200 = (700-300)/2.
                >
                > Milton L. Brown
                > miltbrown@...
                >
                >
                >
                > [Non-text portions of this message have been removed]
                >
                >
                >
                > Unsubscribe by an email to: primenumbers-unsubscribe@egroups.com
                > The Prime Pages : http://www.primepages.org
                >
                >
                >
                > Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
                >
                >
              • Milton Brown
                If you are more specific I will be glad to help. Thanks, Milton L. Brown miltbrown@earthlink.net ... From: Hugo Scolnik To: Milton Brown Sent: Sunday, February
                Message 7 of 11 , Feb 3, 2002
                • 0 Attachment
                  If you are more specific I will be glad to help.

                  Thanks,

                  Milton L. Brown
                  miltbrown@...

                  ----- Original Message -----
                  From: Hugo Scolnik
                  To: Milton Brown
                  Sent: Sunday, February 03, 2002 7:11 AM
                  Subject: Re: [PrimeNumbers] Fermat Factoring with First Digits


                  Dear Milton:

                  I am always interested in your findings but it seems I missed something crucial because your Excel files do not provide something to understand you.

                  Best

                  Hugo Scolnik

                  To ignore the facts does not change the facts



                  [Non-text portions of this message have been removed]
                • Phil Carmody
                  ... I know I m not the only one to see the textbook irony in this situation. However, it seems that it matters no matter how specific people s questions are,
                  Message 8 of 11 , Feb 3, 2002
                  • 0 Attachment
                    On Sun, 03 February 2002, "Milton Brown" wrote:
                    > If you are more specific I will be glad to help.

                    I know I'm not the only one to see the textbook irony in this situation.

                    However, it seems that it matters no matter how specific people's questions are, as you still seem utterly unable to answer them.

                    That's not strictly true. Last year, upon interested enquiry, you did give us some insight into your method. However, after you'd responded I'm sure at least four people independently warned you that the method you describe would be fruitless. Since then you've given us no evidence that your method has evolved in any way. Our conclusions are obvious...


                    Phil

                    Don't be fooled, CRC Press are _not_ the good guys.
                    They've taken Wolfram's money - _don't_ give them yours.
                    http://mathworld.wolfram.com/erics_commentary.html


                    Find the best deals on the web at AltaVista Shopping!
                    http://www.shopping.altavista.com
                  • Andy Steward
                    ... ^^^^^^^^^^^^^^^^ [snip] ... This requires knowing _how_many_digits_ are in $b and $a, not just the leading ones. (I m sure others have noticed this, but I
                    Message 9 of 11 , Feb 3, 2002
                    • 0 Attachment
                      Milton Brown wrote:

                      >The algorithm is from page 198 of Yan's book, reproduced below
                      >I just modified it to start with a different value of k based on knowing
                      >the first digits of the two factors:
                      ^^^^^^^^^^^^^^^^

                      [snip]

                      >I have implemented this, and used k <= lower(sqrt(n+(b-a)^2))+1
                      ^^^
                      >where b = b1 b2 b3 ... 000 first digits of larger factor
                      ^^^^^^^
                      >and a = a1 a2 a3 ... 000 first digits of smaller factor.
                      ^^^^^^^
                      >This is much faster, and faster with the more first digits you know.

                      This requires knowing _how_many_digits_ are in $b and $a, not just
                      the leading ones. (I'm sure others have noticed this, but I don't
                      recall anyone pointing it out.)

                      If Milton's Method provides this essential info, then why not iterate
                      it in a sequence of well-chosen bases, rather than just 10. (This
                      was abortively suggested in connection with the CRT, AFAIR.)

                      IF the previous condition holds, you could choose a base such that a
                      power of it was about in the middle of the range for one of $a or $b
                      constrained by all previous iterations and find the number of digits
                      in that base (and maybe some of the leading ones, but that would be
                      a bonus).

                      THEN you would have a factorisation algorithm that approximated a
                      binary search, i.e. O(log(N)). That would be a breakthrough ;-)
                      (You could use approximate logs to avoid too much faffing about.)

                      Why do I think that the Milton Method probably falls down here?

                      I would LOVE to be wrong.

                      Andy
                    • djbroadhurst
                      Thanks, Milton, for indicating how you might use ... So _if_ you knew the first 10 digits of the factors of RSA-576, as you claimed in
                      Message 10 of 11 , Feb 3, 2002
                      • 0 Attachment
                        Thanks, Milton, for indicating how you might use
                        (as opposed to determine) leading digits of factors:

                        > I just modified it [Fermat] to start with a different value
                        > of k based on knowing the first digits of the two factors

                        So _if_ you knew the first 10 digits
                        of the factors of RSA-576, as you claimed in

                        http://groups.yahoo.com/group/primenumbers/message/4760

                        or maybe even the first 15, as you later claimed,
                        what good would it do you?

                        Could you please tell us the number of Fermat tests
                        that you would then need to do, and also compare it with
                        the number of femtoseconds since the universe began?

                        David
                      • djbroadhurst
                        Andy: I believe that Milton is assuming that both factors of RSA-576 have equal number of decimal digits, and also claiming that he knows the first 15 of each.
                        Message 11 of 11 , Feb 3, 2002
                        • 0 Attachment
                          Andy: I believe that Milton is assuming that
                          both factors of RSA-576 have equal number of decimal
                          digits, and also claiming that he knows the first 15 of each.
                          Such info would then be base-independent
                          (yet still worth sweet-Fanny-Adams in a Fermat method)
                          David
                        Your message has been successfully submitted and would be delivered to recipients shortly.