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

Fermat factorization

Expand Messages
  • kad
    Hi, Can any one tell me Whats the exact logic lie behind the worst time complexity of fermat factorization method? In order to factorize N = pq any semiprime
    Message 1 of 4 , Nov 11, 2012
    • 0 Attachment
      Hi,
      Can any one tell me Whats the exact logic lie behind the worst time complexity of fermat factorization method?


      In order to factorize N = pq any semiprime in order to do fermat factorization we have to search 'a' > sqrt(N) so that a^2 - N = b^2. Then factorization of N = (a - b)(a + b). My question is when worst running time complexity will occur and whats the reason for worst running time.
    • Kermit Rose
      On 11/11/2012 9:58 AM, kad ... Suppose N = 3 y, where y is prime. Then if a^2 - N = b^2, then a = (y + 3)/2 and b = (y-3)/2. Thus in this worst case, you
      Message 2 of 4 , Nov 11, 2012
      • 0 Attachment
        On 11/11/2012 9:58 AM,

        "kad"

        wrote:
        > 1. Fermat factorization
        > Posted by: "kad"yourskadhir@... yourskadhir
        > Date: Sun Nov 11, 2012 12:48 am ((PST))
        >
        > Hi,
        > Can any one tell me Whats the exact logic lie behind the worst time complexity of fermat factorization method?
        >
        >
        > In order to factorize N = pq any semiprime in order to do fermat factorization we have to search 'a' > sqrt(N) so that a^2 - N = b^2. Then factorization of N = (a - b)(a + b). My question is when worst running time complexity will occur and whats the reason for worst running time.

        Suppose N = 3 y, where y is prime.

        Then if a^2 - N = b^2,

        then a = (y + 3)/2 and b = (y-3)/2.

        Thus in this worst case, you will need to advance "a" to (N/3 + 3)/2
        before finding the Fermat factors.


        Kermit Rose




        [Non-text portions of this message have been removed]
      • ronhallam@lineone.net
        Hi The absolute limit to which the fermat factorization would have to go to find a solution at the worst would be when the number, N, is prime and no tests
        Message 3 of 4 , Nov 12, 2012
        • 0 Attachment
          Hi
          The absolute limit to which the fermat factorization would have
          to go to find a solution at the worst would be when the number, N, is
          prime and no tests have been carried out: the maximum value would be
          given by (N + 1 - (2s))/2, where s= flr(sqrt(N)).

          if some trial division has been carried out to say D, the maximum
          limit can be reduced to:

          (((s - D)^2 + (N - (s*s))/D)/2



          The number of operations can be reduced by looking at (N + 1 - (2s))
          mod 4, if the result is 0 then only even values need be looked at, and
          if the result is 2 then only odd numbers need be looked at.



          example N = 13199 s = 114

          (13199 + 1 - (2*114)) = 12972

          12972 mod 4 = 0

          the numbers that need to be looked at are (114 + 2aa) aa =
          1, 2, 3, ... upto (12972/2)/2.



          example N = 1803601 s = 1342

          (1803601 + 1 - (2*1342) = 1800918

          1800918 mod 4 = 2

          the numbers that need to be looked at are (1342 + (2aa -1)) aa =
          1, 2, 3 .... upto (1800918/2)/2



          For large numbers the amount of processing would still be
          considerable and then one would need to look at a sieve for the values
          of a.





          Ron





          >----Original Message----

          >"kad"

          >

          >wrote:

          >> 1. Fermat factorization

          >> Posted by: "kad"yourskadhir@... yourskadhir

          >> Date: Sun Nov 11, 2012 12:48 am ((PST))

          >>

          >> Hi,

          >> Can any one tell me Whats the exact logic lie behind the worst time
          complexity of fermat factorization method?

          >>

          >>

          >> In order to factorize N = pq any semiprime in order to do fermat
          factorization we have to search 'a' > sqrt(N) so that a^2 - N = b^2.
          Then factorization of N = (a - b)(a + b). My question is when worst
          running time complexity will occur and whats the reason for worst
          running time.

          >

          >Suppose N = 3 y, where y is prime.

          >

          >Then if a^2 - N = b^2,

          >

          >then a = (y + 3)/2 and b = (y-3)/2.

          >

          >Thus in this worst case, you will need to advance "a" to (N/3 + 3)
          /2

          >before finding the Fermat factors.

          >

          >

          >Kermit Rose
        • ronhallam@lineone.net
          Dear all He has also sent a message directly to me. He clearly does not understand some very basic concepts: 1) If you think that you have found an error, look
          Message 4 of 4 , Nov 25, 2012
          • 0 Attachment
            Dear all
            He has also sent a message directly to me.

            He clearly does not understand some very basic concepts:
            1) If you think that you have found an error, look for the error
            in your own work and if you cannot spot the error put the work away
            for sometime (3 months is good) then go back to it.

            2) If a message has been posted to a group and no one has found an
            error, the likelihood is that the error is in your own work; usually
            true 999 times out of a thousand.

            3) if the formula work on small numbers, try the same formula on
            medium size numbers and than on large numbers; and not just one of
            each, it would not be that first time that spurious results can result
            from special factors relating to the number(s).

            4) Do not use results, ie the difference, which can only be found
            after the complete factorization has been completed.



            Ron







            >----Original Message----

            >From: yourskadhir@...

            >Date: 23/11/2012 13:24

            >To: "ronhallam@..."<ronhallam@...>

            >Subj: Re: [PrimeNumbers] Re: Fermat factorization

            >

            >The logic that factors with least difference will factored easily and
            large

            >difference will factored hardly is wrong. Please follow the link which
            i

            >found about Fermat factorization.

            >http://kadinumberprops.blogspot.in/2012/11/fermats-factorization-running-time.html

            >

            >On Mon, Nov 12, 2012 at 5:08 PM, ronhallam@... <
            >ronhallam@...> wrote:
            >
            >> **
            >>
            >>
            >> Hi
            >> The absolute limit to which the fermat factorization would have
            >> to go to find a solution at the worst would be when the number,
            N, is

            >> prime and no tests have been carried out: the maximum value would
            be

            >> given by (N + 1 - (2s))/2, where s= flr(sqrt(N)).

            >>

            >> if some trial division has been carried out to say D, the maximum

            >> limit can be reduced to:

            >>

            >> (((s - D)^2 + (N - (s*s))/D)/2

            >>

            >> The number of operations can be reduced by looking at (N + 1 -
            (2s))

            >> mod 4, if the result is 0 then only even values need be looked at,
            and

            >> if the result is 2 then only odd numbers need be looked at.

            >>

            >> example N = 13199 s = 114

            >>

            >> (13199 + 1 - (2*114)) = 12972

            >>

            >> 12972 mod 4 = 0

            >>

            >> the numbers that need to be looked at are (114 + 2aa) aa =

            >> 1, 2, 3, ... upto (12972/2)/2.

            >>

            >> example N = 1803601 s = 1342

            >>

            >> (1803601 + 1 - (2*1342) = 1800918

            >>

            >> 1800918 mod 4 = 2

            >>

            >> the numbers that need to be looked at are (1342 + (2aa -1)) aa =

            >> 1, 2, 3 .... upto (1800918/2)/2

            >>

            >> For large numbers the amount of processing would still be

            >> considerable and then one would need to look at a sieve for the
            values

            >> of a.

            >>

            >> Ron

            >>

            >>

            >> >----Original Message----

            >>

            >> >"kad"

            >>

            >> >

            >>

            >> >wrote:

            >>

            >> >> 1. Fermat factorization

            >>

            >> >> Posted by: "kad"yourskadhir@... yourskadhir

            >>

            >> >> Date: Sun Nov 11, 2012 12:48 am ((PST))

            >>

            >> >>

            >>

            >> >> Hi,

            >>

            >> >> Can any one tell me Whats the exact logic lie behind the worst
            time

            >> complexity of fermat factorization method?

            >>

            >> >>

            >>

            >> >>

            >>

            >> >> In order to factorize N = pq any semiprime in order to do fermat

            >> factorization we have to search 'a' > sqrt(N) so that a^2 - N =
            b^2.

            >> Then factorization of N = (a - b)(a + b). My question is when worst

            >> running time complexity will occur and whats the reason for worst

            >> running time.

            >>

            >> >

            >>

            >> >Suppose N = 3 y, where y is prime.

            >>

            >> >

            >>

            >> >Then if a^2 - N = b^2,

            >>

            >> >

            >>

            >> >then a = (y + 3)/2 and b = (y-3)/2.

            >>

            >> >

            >>

            >> >Thus in this worst case, you will need to advance "a" to (N/3 + 3)

            >> /2

            >>

            >> >before finding the Fermat factors.

            >>

            >> >

            >>

            >> >

            >>

            >> >Kermit Rose

            >>

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