Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Say I have m integers:

$i_{0}, i_{1}, ..., i_{x}, ..., i_{m} where -L < i_{x} < M$ where L and M are known integers

is it possible to come up with a function that uses Primes that maps

$f(i_{0}, i_{1}, ..., i_{x}, ..., i_{m}) \mapsto k$

where it is always possible to do in a computationally cheap way to do:

$f^{-1} (k) \mapsto <i_{0}, i_{1}, ...., i_{m}>$

I'm trying to find an analogous method to the following:

say I have two numbers i0 and i1 that are between 0 and 9 inclusive I can map these using the following function:

$f(i_{0}, i_{1}) \mapsto k$ can be written as $10 * i_{0} + i_{1}$

where $f^{-1}$ is easy (I won't write this out as I think it's pretty clear that it can be done)

share|improve this question
1  
I don't understand what your asking, can you fix your latex please also –  Ethan Feb 8 '13 at 2:29
    
Hmmmm, sorry about that, my latex is rather week but I'll try –  user1172468 Feb 8 '13 at 2:30
1  
What do you want the function to map to? What is $k$? –  Ethan Feb 8 '13 at 2:31
    
I want the function to take n integers, say 5, 6 and 21 and give me one number, say X. The caveat being that there should be simple reverse function that will take X and give me 5, 6, 21 –  user1172468 Feb 8 '13 at 2:33
1  
I think you could alter your question so that someone more experienced could help you, id change it to somthing along the lines: "Techniques in cryptography based on the factoring problem", and then you could delete most of the latex and ask for an alternate method to the RSA algorithm for encrypting information, based on the presumed difficulty of factoring integers. –  Ethan Feb 8 '13 at 3:02

1 Answer 1

up vote 1 down vote accepted

Here is a possible way to implement $f$: Add $L-1$ to each integer. Then, treat the result as the expansion of a number in base $M+L-1$ and find the value of the result. This is $k$, the value of $f$.

To reverse the process, take $k$ and expand it in base $M+L-1$. Then, take each digit and subtract $L-1$. To express this in formulae:

$$f(i_0,\dots,i_m)=\sum_{0\le j\le m} (M+L-1)^{m-j} (i_j+L-1)$$ and $$ f^{-1}(k)=(i_0,\dots,i_m), \ \ \text{where}$$ $$ i_j=-(L-1)+\left(\lfloor\frac{k}{(M+L-1)^{m-j} }\rfloor \mod (M+L-1)\right).$$

This has nothing to do with prime numbers but is a simple way to find an invertible $f$. If you like, you can use a larger base than $M+L-1$, for example, the smallest power of $2$ that is at least as large as $M+L-1$. This may make the function easier to compute.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.