1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How to prove?

  1. Feb 24, 2005 #1
    For a positive natural number n, we use
    [tex]
    |n|= \log_{2}n
    [/tex]
    as the measure of the size of n (which is the number of bits in n's binary representation). however, in most cases the size of n can be written as log n without giving an explicit base (the omitting case is the natural base e). Show that for any base b>1,
    [tex]
    \log_{b}n
    [/tex]
    provides a correct size measure for n, i.e., the statement "a polynomial in the size of n" remains invariant for any base b>1.


    This was a problem in my homework for cryptography...

    I understand the first part of the problem, which basically means that for any base, b:

    [tex]
    \log_{b}n=|k| => b^{[k]+1} > n
    [/tex]
    where [k] equals the floor of k.

    but beyond that, I really have no idea...

    thanks for any help

    matt
     
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you help with the solution or looking for help too?
Draft saved Draft deleted