For a positive natural number n, we use(adsbygoogle = window.adsbygoogle || []).push({});

[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

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: How to prove?

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**