恩，看样子 哈弗曼编码比较适合~~

网上有看过哈弗曼，但不知如何下手？

能帮写个吗？ 交流QQ: 99-616-84

16位数字变成15位数字，原集合的个数是10^16个，而目标集合是10^15个，不可能做到一一映射，只能多对一映射，那么解密时就有问题了吧。感觉理论上你说的是实现不了的。
把16位数字变成16进制数表示，倒是可以少于16位，最多好像14位吧，但这里面有ABCDEF几个字符。

这中间有个 KEY的存在，还不能压缩数字串吗？ 做一些运算之类的处理 ，难道加密成原数字串长度都不行吗？

首先声明下我是新手，所以大神勿喷，当然有什么指点的话不胜感激！

    几年前我其实考虑过类似的问题，在这里说下我的个人看法。楼主的例子估计是不行的，如果是15位以内的数字压缩为15位以内是可以的，类似著名的凯撒密码就能做到；但是16位以内变15位以内的话，前者的个数是后者的10倍，肯定做不到无损压缩。也就是4L这位兄台说的多对一映射，换句话说，加密的算法函数肯定是双射的，因为解密的时候要用到加密函数的反函数，而只有双射的函数才有反函数。

    换句话说，如果能做到任意16位压缩到15位，那么就能做到每次压缩减少1/16的空间，我多压缩几次，这不就是传说中的无限压缩么？明显的违背信息学的定律了，信息熵的威严何在？

    说到我当时思考的问题，我想的是，能否找到这样一个有n个参数的函数，对任意n+1个数值a0,a1,......an，可以找到确定的n个参数，使得这个函数在固定的n+1组自变量值对应的函数值恰好是n+1个数值a0,a1,......an。也就是说，我们用n个数字存储了n+1个数字的信息。举个简单的例子，假定二次函数符合要求，二次函数是3个参数的，那么对于任意四个数字a0,a1,a2,a3，我们都可以找到三个数值p0,p1,p2，使得这个二次函数在四个特定的自变量上（比如x分别等于0,1,2,3，这个数字根据函数的类型可以不同，但是必然是与其他参数无关的），函数值恰好是a0,a1,a2,a3。也就是说，我可以用p0,p1,p2来保存a0,a1,a2,a3这四个数字。当时记得我还跟一个老师争论了半天，当然我是知道无法做到的，只是想让老师证明一下这个不可能，然而当时老师一直没有正面论证这个问题，只是一直强调这就是无限压缩，不可能实现，所以有点不满意老师的回答。。。。。。

    额，跑题了。总之楼主说的这个加密其实应该叫压缩比较合适，像常用的压缩方式都是建立字典，然后通过替换的方式来省空间，比如“我爱北京河蟹词河蟹词上太阳升伟大领袖河蟹词指引我们向前进”，那么这是28个字，假定建立一个含有“河蟹词”的字典，并用“习”来代替，那么就成了“我爱北京习习上太阳升伟大领袖习指引我们向前进”22字，加字典26字，少了两个，这就是压缩的原理，如果以字为最小单位，这就无法继续压缩了。像霍夫曼编码貌似就比较科学，但是原理也是类似的，无限压缩也是不行的。总之全部变短是不可能的，我从一个16位的变成15位的，然后再加密变成14位，13位。。。。。。1位，然后没了。。。。。。

　　对任意组合肯定是不行的，但如果中间有重复字符是有可能变短的。所以没有通用的方式。

把16位纯数字密码当成一个十进制的数，1234567887654321将其转换为16进制可减少位数，转换后为462d53c650db1 变为13位再进行加密

有意思！
题目的难点在第三条：1) 纯数字；2) 输入小于等于16位，输出最多15位。

一个16字节数字字符串对应于8字节十六进制的数据，按第二条要求，应该是用对称加密算法。64Bits的块最为常用，有多种Block Cipher算法可选。
但是结果是十六进制的，转换成十进制，长度又不能满足要求。

理论上，低进制向高进制转换，输出长度缩短；反之则增长。比如，这里在对称算法加密后，再做Base64的编码，长度肯定满足要求，但字符集是个问题。

所以加密后需要有个压缩。上面提到了哈夫曼编码(Huffman Coding)，很多压缩算法都基于它，进行优化、形成分枝。
其基本原理，就是先扫描数据流，生成“字典”，再编码。
举个例子，这里限于“纯数字”的要求，不能使用二进制流。
例如，输入16位：1234567890123123，
可以压缩成15位：123456789009191。
编码解释：
"123"在输入中出现三次，作为“字典”里的一个“单词”。这里，字典没有单独的存储区，直接保存在输出的最前面。单词也没有长度位，约定为3位。
编码结果中直到"90"都是原始输入，没有“压缩”发生。解压缩时，遇到"9"，表明是一个压缩标志，"90"表示原始输入为"9"；"91"表示取单词，进行替换。

例子是最理想的情况，而大多数情况下，受限于15位，结果中没办法保存单词的索引位、长度位、压缩标志位等等。
所以，压缩在这么短的位数要求下根本行不通，忘掉哈夫曼吧！

是不是无解了呢？
把楼主的三条要求，归纳为我一开始提到的两条，就有解！
需要写点小程序，再验证一下。数字游戏，“不疯魔不成活”，呵呵。

最近一直在研究这人问题；

希望加密结果长度不能大于原串长度，如果结果变长了就没意义了，还不如果直接用公认的一些加密算法；

感谢，MistHill 的建议！

感谢 积极参与讨论的朋友，相信此问题最终会得到一个比较理想的结果。

群策群力，大家积极讨论……

希望有个好的讨论结果，很想看到这个结果，长期关注此帖，希望能得到解决！

这是一个很具意义的命题，大家积极参与

看雪成员万岁，解决这个问题！

我能想到的只有压缩了

非常不幸，我的结论过于武断，在开始写代码之前，就发现了这个错误：解密出问题了！。
就象4楼和6楼两位兄弟提到的，解密时出现一对多的情况。

加密和解密是一一对应的，或者说映射的。
就这个十进制的命题来说，可理解为：输出为15位数据集，不管你输入是多少位，也只能对应15位输入数据集，而现在明文数据集是16位，完整地包含了整个与密文数据集对应的输入数据集。
一对多成为必然，这是基本常识。所以楼主的命题恐怕无法实现！

下面分享一下我失败的教训，我认为也是有意义的，可以避免以后类似愚蠢的错误。

首先意识到，不能用对称加密算法，其结果长度无法控制。
我们知道，选取适当RSA的模N可以精准地控制输出的位数。
这个思路已经隐藏着错误，只是我还没意识到，依然继续着。如果谁能在这一时刻指出我的错误，那么他对RSA就有深刻的理解。

我从15位输出的最大值15个9开始，向下作分解(factoring)。这个最大值不能当作RSA的N来用，因为它不是两个质数的乘积。也不能向上分解，输出结果位数会超过15位。
找到离最大值最近的分解结果：

[FONT="Courier"]P:      5
Q:      199999999999997
N:      999999999999985
E:      65537
D:      705506812945345[/FONT]

在P和Q出来后，随便指定一个E，再计算D。E的选择对我们的实验结果没有影响。
然后用大数计算器作简单的验证。
先测试加密，完全没有问题，所有的16位输入必定是不超过15位的输出。
再测试解密，出问题了！怎么回不去呢？！

我们来看看RSA算法的公式，非常简单，比那些复杂的对称算法更容易理解。

[FONT="Courier"]加密：
   PT ^ E MOD N
解密：
   CT ^ D MOD N
这里：PT - PlainText 明文；CT - CipherText 密文[/FONT]

很简单，是吧！
我忘记了最后是一个对N的取模运算！所以输出可以控制在15位之内。

下面是加密计算记录：

[FONT="Courier"]Encrypting
==========
Plaintext               Ciphertext
---------               ----------
0                       0
1                       1
2                       232688612375957
3                       153875846496713
15                      754708694258465         <- ***
149                     451197539489329         <- ***
999999999999983         767311387624028
999999999999984         999999999999984

999999999999985         0                       N*1+0
999999999999986         1                       N*1+1
999999999999987         232688612375957         N*1+2
999999999999988         153875846496713
999999999999989         181304566607584
999999999999990         286328491331895
999999999999991         449231078721781
999999999999992         572836376551517
999999999999993         623394115778033
999999999999994         337601761830569
999999999999995         878876095224315
999999999999996         997814104863221
999999999999997         91685321778322
999999999999998         212292800531143
999999999999999         682231106350444
1000000000000000        754708694258465         N*1+15
1000000000000001        356296434408516
1000000000000002        348411433004192
...
1999999999999985        754708694258465         N*2+15
2000000000000119        451197539489329         N*2+149
...
2999999999999970        754708694258465         N*3+15
3999999999999955        754708694258465         N*4+15
4999999999999940        754708694258465         N*5+15
5999999999999925        754708694258465         N*6+15
6999999999999910        754708694258465         N*7+15
7999999999999895        754708694258465         N*8+15
8999999999999880        754708694258465         N*9+15
9999999999999865        754708694258465         N*10+15
...
9999999999999999        451197539489329         N*10+149[/FONT]

显然，输入在大于等于N后，输出开始重复了。对比一下数据集的关系：

[FONT="Courier"]16位明文数据集:        0 ~ 9999999999999999
子集 A:                0 ~  999999999999984
     B:  999999999999985 ~ 1999999999999969     N*1
     C: 1999999999999970 ~ 2999999999999954     N*2
     D: 2999999999999955 ~ 3999999999999939     N*3
     E: 3999999999999940 ~ 4999999999999924     N*4
     F: 4999999999999925 ~ 5999999999999909     N*5
     G: 5999999999999910 ~ 6999999999999894     N*6
     H: 6999999999999895 ~ 7999999999999879     N*7
     I: 7999999999999880 ~ 8999999999999864     N*8
     J: 8999999999999865 ~ 9999999999999849     N*9
     K: 9999999999999850 ~ 9999999999999999     N*10

15位密文数据集:        0 ~  999999999999999[/FONT]

也就是说15位内的密文可完整对应于16位输入中的A~J子集，部分对应K子集。大致是一对十的关系，凭常识也可以理解。
除非在解密时，特别指定要还原的子集A~J中的一个，否则解密不能完成。

实际上，在输入超过N后，应进行“分组加密”，即将输入分成n个N块，最后一个不足N位的块做必要的PADDING，再进行n次RSA加密；解密时就可以保证一一对应。
这种情况下十进制的密文可能将远远长于15位，大部分会是15的倍数。
十六进制时，我通常会意识到这点；十进制时怎么就糊涂了呢，惭愧惭愧。

所以，在这个命题中，无论是加密算法还是压缩算法，都会遇到一对多的问题，应该是无解。欢迎讨论、指正。

教训是，数字游戏中，没有扎实的基础知识，瞎折腾是不可取的，应设置一个“止损点”，力所能及，适可而止。
君不见，一个大数分解另无数英雄尽折腰。与诸君共勉！

PS：php中要使用RSA算法，将 php.ini 文件里 "Dynamic Extensions" 节的 extension=php_gmp.dll 启用就可以了。

此类问题毫无意义！

一位字符可以255种，把数字从10进制转换为255进制，然后在把普通的加密算法应用于255进制数就好了，当然这样能节省的空间还是有限的

挺有意思 不错...学习到了！