[SOLVED] Re: 一个数学问题

Subject: [SOLVED] Re: 一个数学问题
From: Zhang Erning (zhangern@china-channel.com)
Date: 8/8/2005 3:18 PM
To: tech@35.cn

hi,

多谢各位的回复。

是的，这个其实就是破解RSA的问题。只是当RSA的key很大的时候，破解需要的时 间是不可接受的。

我这个问题，A,B是常量，而且算是很小的。(可能提问的时候提示不够)

根据RSA的算法的说明
当 x^B mod A = c 时，应该有
x = c^r mod B

问题就是算出r

r*B mod ((p-1)(q-1)) = 1
其中p,q是两个质数，p*q == A

问题就成了找p,q的，这也就是RSA里最直接的破解思路。因为A足够小。
A=179399505810976971998364784462504058921

通过Quadratic Sieve算出
p=9939430972488238699
q=18049273274048008379

B=65537
然后 modular inverse 算出
r=89126272330128007543578052027888001981

不停的google后，终于解决了。

[其实我是想写一个软件的序列号生成器，搞定了]

Zhang Erning

Hi,

有个数学问题，有数学比较好的帮我看看，或者问问，谢谢。

对下面的方程，A,B是常量, 给定一个c，求x。其中A,B,c,x都是正整数
x^B mod A = c
(x^B表示x的B次方，mod是模。)

A, B, c, x 都是个很大的整数，其中常亮
A=179399505810976971998364784462504058921
B=65537

其中一个解的例子是

c=316442568644203243198389073 时
x=162056862300807702758723198119182049115

这个c是通过x算出来的，我想知道，给定c能否算出x

另外，c是有特征的，c为12个bytes的integer。其中前10个bytes固定的。
比如 c = 0x 31 05 00 00 00 00 00 00 00 00 xx xx
对于给定的c，就后面两个bytes不同。

这个问题目前也可能没有好办法。就是不能在可接受的O()里通过c逆算出x。

Zhang Erning