# Encoding Binary Numbers In Integers With Primes; Decoding Binary Numbers From Integers With Factoring

Scott Aaronson’s Quantum Computing Since Democritus has this excerpt:

When I was in junior high school, I had a friend who was really good at math, but maybe not so good at programming. He wanted to write a program using arrays, but he didn't know what an array was. So what did he do? He associated each element of the array with a unique prime number, then he multiplied them all together; then, whenever he wanted to read something out of the array, hefactoredthe product.

Here’s how this works:

Start with a binary number. This only works with binary numbers.

Here, we’ll use 1010.

## Encoding

Match up each digit in the binary number with a prime.

Here, we’ll match the binary digits starting from right-to-left, resulting in:

Prime | Binary Digit |
---|---|

2 | 0 |

3 | 1 |

5 | 0 |

7 | 1 |

Multiply the prime and its binary digit.

Here, we get:

Prime | Binary Digit | Product |
---|---|---|

2 | 0 | 0 |

3 | 1 | 3 |

5 | 0 | 0 |

7 | 1 | 7 |

Multiple the non-zero products together.

Here:

3 * 7 = 21 |

The binary digits 1010 are encoded in the number 21.

## Decoding

Factor the integer.

Here, the factors of 21 are:

Factors |

3 |

7 |

Using the same mapping table from above, note which primes are factors of the integer.

Here, the primes are in bold:

Prime | Binary Digit |
---|---|

2 | 0 |

3 |
1 |

5 | 0 |

7 |
1 |

Starting with the first row, if prime was found in the factors, it represents a one in right-most digit of the binary number. Else it’s a zero. The first row is the right most digit, the second row is the second from right and so on.

Here, the primes are absent for the right most, present for the second-from right, absent from the third-from-right, and present from the forth-from-right, resulting in 1010.