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

Re: [PrimeNumbers] Re: Fermat Factoring with First Digits

Expand Messages
  • 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 1 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 2 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 3 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 4 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 5 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 6 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 7 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 8 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.