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

Time complexity

Expand Messages
  • kad
    In order to factorize a given N with n number of bits. The GNFS had a time complexity O(N) = exp( ((64/9)^(1/3) + 1)(ln n)^(1/3)(ln ln n)^(2/3) ) And i had
    Message 1 of 1 , Aug 9, 2012
    View Source
    • 0 Attachment
      In order to factorize a given 'N' with 'n' number of bits. The GNFS had a time complexity

      O(N) = exp( ((64/9)^(1/3) + 1)(ln n)^(1/3)(ln ln n)^(2/3) )

      And i had a method which complexity as follows

      K = ceiling( sqrt( ( (ceiling( sqrt(N)))^2 - N )))

      Then O(N) = k +1 if k is even
      = (k -1)/2 + 1 if k is odd.

      Then which complexity is best. Mine or GNFS.

      For eg. N = 67, ceiling(sqrt(N)) = 9
      Then k = ceiling( sqrt ( 9^2 - N ))
      = ceiling( sqrt (81 - 64))
      = ceiling( sqrt ( 17 )) = 5

      Then O(N) = (5 - 1)/2 = 2
    Your message has been successfully submitted and would be delivered to recipients shortly.