特殊数对

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

你一天改三次主意了啊先求出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

这是离散对数问题，好像不是很容易

账号		自动登录	找回密码
密码			欢迎注册

[求助] 特殊数对