Converting a number back to its positional values

[erotavlas]

In positional notation, say I have a number like this in base- 10

73901=7×10⁴ +3×10³ +9×10² +0×10¹ +1×10⁰
it's pretty obvious how to go back and forth from the number to positional notation.

So if someone gave me a new number like 234 I can easily know

234₁₀ = 2×10² + 3×10¹ + 4×10⁰

However say you have a number in a different base like base-42

2×42² + 5×42¹ + 13×42⁰ = 3751₄₂

Is there a general procedure for determining the positional values from the number? Say someone gave me 3751₄₂, how can I go backwards to find the exact values that the number is made of in that base?

 

[phinds]

In positional notation, say I have a number like this in base- 10

73901=7×10⁴ +3×10³ +9×10² +0×10¹ +1×10⁰
it's pretty obvious how to go back and forth from the number to positional notation.

So if someone gave me a new number like 234 I can easily know

234 = 2×10² + 3×10¹ + 4×10⁰

However say you have a number in a different base like base-42

2×42² + 5×42¹ + 13×42⁰ = 3751

Is there a general procedure for determining the positional values from the number? Say someone gave me 3751, how can I go backwards to find the exact values that the number is made of in that base?

If you are saying that someone gives you 3751 DECIMAL and you are supposed to convert it to base 42, then you just have to do the calculations. If someone gives you 3751 in base 42, then it is 3751.

 

[Mentallic]

In positional notation, say I have a number like this in base- 10

73901=7×10⁴ +3×10³ +9×10² +0×10¹ +1×10⁰
it's pretty obvious how to go back and forth from the number to positional notation.

So if someone gave me a new number like 234 I can easily know

234 = 2×10² + 3×10¹ + 4×10⁰

However say you have a number in a different base like base-42

2×42² + 5×42¹ + 13×42⁰ = 3751

Is there a general procedure for determining the positional values from the number? Say someone gave me 3751, how can I go backwards to find the exact values that the number is made of in that base?

$$3751_{10} = 25(13)_{42}$$

where the subscript is the base number, and 13 is enclosed in brackets to denote it should be a single digit. In hexadecimal (base 16) the numbers 10-15 are given the letters A-F respectively, so you could represent it as

$$3751_{10}=25D_{42}$$

granted that the reader understands D represent 13 in hexadecimal, but then you still have the problem of not being able to represent the numbers 16-41. You could of course concoct a method to do so, such as extending it to use the entire alphabet, and then letters from other alphabets etc.

As phinds said, converting from one base to another requires calculations though. It's not as clear-cut.

 

[erotavlas]

Sorry guys I forgot the subscripts on my numbers to indicate what base they are in.

I'm not interested to convert form one base to another. I'm staying in the same base (say base 42) and I want to reconstruct the positional notation that was used to get the number. Is that possible?

So without knowing the positional notation for 3751₄₂ is there a way to reconstruct it like we can for base 10 numbers?

 

[Mentallic]

Sorry guys I forgot the subscripts on my numbers to indicate what base they are in.

I'm not interested to convert form one base to another. I'm staying in the same base (say base 42) and I want to reconstruct the positional notation that was used to get the number. Is that possible?

So without knowing the positional notation for 3751₄₂ is there a way to reconstruct it like we can for base 10 numbers?

Well now that you've gone back and changed it

2×42² + 5×42¹ + 13×42⁰ = 3751₄₂

This is not a valid equality. The expression on the left side is equal to $3751_{10}$ but $3751_{10}\neq 3751_{42}$ or 3751 in any other base.

For any base b,

$$(a_na_{n-1}a_{n-2}...a_1a_0)_b = a_nb^n+a_{n-1}b^{n-1}+...+a_1b+a_0$$

Which is exactly what you did in decimal, so you have to follow the same rules for any other base, such as

$$3751_{42}=3\times 42^3 + 7\times 42^2 + 5 \times 42 + 1$$

and

$$2\times 42^2 + 5\times 42 + 13 = 25D_{42}$$

which I explained in my previous comment.

 

[erotavlas]

I think I understand now, I'll explain further what I'm trying to do, can you tell me if I'm on the right track?
I'm trying to encrypt strings of alphabetic characters using format preserving encryption.

So say my vocabulary of strings consist of only these 7 characters A,B,C,D,E,F,G, where A=0, B=1, C=2, D=3, E=4, F=5, G=6, H=7

To encrypt the word CDG I know in base 7 it is 236₇.
This equals 2x7² + 3x7¹ + 6x7⁰ = 125₁₀ (is this right so far?)

For a 3 letter word, to encrypt with a result also as a 3 letter word my total possible values for the result range from 0 to 7^N - 1 = 0 to 342 (where N is the number of characters)

Passing the base 10 representation through the Encryption function (with the range of allowed values)
I get E(125) => 221₁₀

221 is also in base 10 so in order to go back to represent that number in the original scheme (base 7) I need to convert it to base 7
so 221₁₀ = 434₇
This would equal EDE.

Does this make sense?

 

[Mark44]

I think I understand now, I'll explain further what I'm trying to do, can you tell me if I'm on the right track?
I'm trying to encrypt strings of alphabetic characters using format preserving encryption.

So say my vocabulary of strings consist of only these 7 characters A,B,C,D,E,F,G, where A=0, B=1, C=2, D=3, E=4, F=5, G=6, H=7

To encrypt the word CDG I know in base 7 it is 236₇.
This equals 2x7² + 3x7¹ + 6x7⁰ = 125₁₀ (is this right so far?)

No. In base-7, there are 7 digits: 0, 1, 2, 3, 4, 5, and 6.

7₁₀ would be 10₇.

Since you have 8 symbols (0, 1, 2, ..., 6, 7) base-8 would be appropriate.

For a 3 letter word, to encrypt with a result also as a 3 letter word my total possible values for the result range from 0 to 7^N - 1 = 0 to 342 (where N is the number of characters)

Passing the base 10 representation through the Encryption function (with the range of allowed values)
I get E(125) => 221₁₀

221 is also in base 10 so in order to go back to represent that number in the original scheme (base 7) I need to convert it to base 7
so 221₁₀ = 434₇
This would equal EDE.

Does this make sense?

 

[erotavlas]

No. In base-7, there are 7 digits: 0, 1, 2, 3, 4, 5, and 6.

7₁₀ would be 10₇.

Since you have 8 symbols (0, 1, 2, ..., 6, 7) base-8 would be appropriate.

Yes that's correct, sorry. I'll edit my post to remove the extra character H from the sequence. (Or if someone can do it for me since it seems the edit option is no longer present)

So did I do the calculation correctly?

 

[Mentallic]

I'll edit my post to remove the extra character H from the sequence. (Or if someone can do it for me since it seems the edit option is no longer present)

Well considering you're the student here, making mistakes and leaving them as they are is fine. It also helps with the flow of conversation to leave it. If someone in the future decided to read through the entire thread because they're having the same problem, then answers that are quoting something that isn't there any more would get confusing.

I think I understand now, I'll explain further what I'm trying to do, can you tell me if I'm on the right track?
I'm trying to encrypt strings of alphabetic characters using format preserving encryption.

So say my vocabulary of strings consist of only these 7 characters A,B,C,D,E,F,G, where A=0, B=1, C=2, D=3, E=4, F=5, G=6, H=7

To encrypt the word CDG I know in base 7 it is 236₇.
This equals 2x7² + 3x7¹ + 6x7⁰ = 125₁₀ (is this right so far?)

Remove the letter H=7 and you're all good.

Passing the base 10 representation through the Encryption function (with the range of allowed values)
I get E(125) => 221₁₀

I lost you here. Where did 221 come from?

 

[erotavlas]

Well considering you're the student here, making mistakes and leaving them as they are is fine. It also helps with the flow of conversation to leave it. If someone in the future decided to read through the entire thread because they're having the same problem, then answers that are quoting something that isn't there any more would get confusing.Remove the letter H=7 and you're all good.
I lost you here. Where did 221 come from?

Since I don't have my encryption function developed yet, I just made that number up, so 221 is just a hypothetical result of the encryption in the range between 0 and 7^N - 1

 

[jbriggs444]

Will the encryption function operate on numbers or on strings of decimal digits?

Edit: Removed commentary.

The usual algorithm for converting a number to a string of digits in a particular radix is a loop. Divide by the radix and take the remainder. That is the low order digit of the result. Retain the quotient and repeat.

So if you have the number 221 and you wish to convert it to base 7, you would take 221/7 which is 31 with a remainder of 4. The low digit is 4.

Now take 31/7 which is 4 with a remainder of 3. The next lowest digit is 3.

Now take 4/7 which is 0 with a remainder of 4. The high order digit is 4.

221₁₀ = 434₇

Check to verify: 4x7² + 3x7¹ + 4 = 196 + 21 + 4 = 221

 

[erotavlas]

Will the encryption function operate on numbers or on strings of decimal digits?

It will operate on numbers only not alphabetics, where the number represents the entire string (not individual characters within it - I'm not sure if that answers your question.

Thank you for describing how to get the number as it is represented in positional notation. That was the final step.

 

[Mark44]

This seems pretty straightforward to me. You have an alphabet of, say 7 letters, A, B, C, D, E, F, G.

1. For a given message of these 7 letters, there's a one-to-one map between a string of letters and a number in base-7. For example, the string CAB would be 201₇
2. Encrypt the number string. Presumably each digit 0...7 will be transformed to another digit in this same set. For example, 201₇ might go to 312₇, with the encoding being n -> (n + 1) mod 7. Here 0 -> 1, 1 -> 2, ... and 6 -> 0 (i.e., wraps around). The encrypted word would be DBC. As long as the encryption scheme works on a single digit at a time, it is a one-to-one operation, hence it is invertible, which is what you want so that you can decrypt an encrypted message.
3. To decrypt a word perform the reverse operation as was done to encrypt the word. In my example, we subtract 1 (modulo 7) from the digit. So 0 -> 6, 1 -> 0, 2 -> 1, 3 -> 2, and so on. In my example, 312₇ -> 201.
4. From the number string, write the letters, which in this case would be CAB.

This system will work as long as you are working in a base the same size as the number of letters in your alphabet.

 

[jbriggs444]

Why go through all that rigamarole? The base 7 is not contributing anything to that scheme. It is still a [very] simple substitution cipher.