medie2005 发表于 2008-4-15 17:00:07

特殊数对

找一个500位的质数p和两个正整数x、y。使:
1）: （p-1）/2是质数
2）： 4^x-9和4^y-25都能整除p。

mathe 发表于 2008-4-15 17:03:04

2是被p整除，不是整除p吧

medie2005 发表于 2008-4-15 17:05:12

2）： 4^x-9 | p，4^y-25 | p。

无心人 发表于 2008-4-15 17:05:25

应该不是难题吧

medie2005 发表于 2008-4-15 17:07:12

2）： p | 4^x-9 |，p | 4^y-25 。

medie2005 发表于 2008-4-15 17:07:29

2）： p | 4^x-9，p | 4^y-25 。

无心人 发表于 2008-4-15 17:12:52

:lol

你一天改三次主意了啊

先求出q为素数
再求p = 2q + 1素数
很容易的

然后解同余方程
这个俺不在行

mathe 发表于 2008-4-15 17:16:44

最后一步其实只要保证2是p的原根就可以了。
用随机算法就可以。
随机选择一个数q是素数的概率为$O(1/log(n))$,$p=2q+1$还是素数的概率也是$O(1/log(n))$
而2是p的原根的概率不小于$O(1/log(n))$
所以这种方法可以得到一种依概率$O(log^3(n))$的算法

medie2005 发表于 2008-12-12 13:09:25

假定我们已经找到素数p，使p,2p+1都是素数，并且2是2p+1的原根。
如何求x,y？

mathe 发表于 2008-12-12 13:17:12

这是离散对数问题，好像不是很容易
页: [1] 2
查看完整版本: 特殊数对