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

Re: Fermat Factoring with First Digits

Expand Messages
  • 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 1 of 11 , Feb 1, 2002
      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 2 of 11 , Feb 1, 2002
        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 3 of 11 , Feb 1, 2002
          > > 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 4 of 11 , Feb 2, 2002
            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 5 of 11 , Feb 3, 2002
              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 6 of 11 , Feb 3, 2002
                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 7 of 11 , Feb 3, 2002
                  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 8 of 11 , Feb 3, 2002
                    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 9 of 11 , Feb 3, 2002
                      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.