find 4-tuples (e, r, p, s)

mathabc

问题：找满足如下条件的自然数组 (e,r,p,s)：
(1) $p$是奇素数, $p-1$ 能被 9 整除，$s=\frac{p-1}{9}$；
(2) $r$ 与 $s$ 互素，即 $(r,s)=1$；
(3) $2^s$ 模 $p$ 余 1，即$ 2^s\equiv 1 (\text{mod} p) $；
(4) $2r+es$ 与 9 互素，即 $(2r+es,9)=1$；
(5) 当 $x$ 从 1 以步长 1 递增到 $p-1$ 时，$x^r(1+x^(es))$ 模 $p$ 的余数的集合刚好有 $p-1$ 个数。

$e=1,r=1$时我找到了三组：
(1, 1, 35803, 3978)
(1, 1, 86257, 9584)
(1, 1, 152623, 16958)
当$e=1$时，$r>1$的情形一组都没有找到.

winxos

原帖由 mathabc 于 2009-4-19 19:23 发表
问题：找满足如下条件的自然数组 (e,r,p,s)：
(1) p是奇素数, p-1 能被 9 整除，s=\frac{p-1}{9}；
(2) r 与 s 互素，即 (r,s)=1；
(3) 2^s 模 p 余 1，即 2^s\equiv 1 (\text{mod} p) ；
(4) 2r+es 与 9 互素， ...

帖子的名字好像以前论坛里见大侠们讨论过。
我不懂。不过看你三组前面都是1 1，感觉有点简化题目了。

mathe

这个应该不难,总可以选择s=p-1,
于是最后一步变成$2*x^r(mod p)$这好遍历p的同余类,于是(r,p-1)=1就可以了

mathe

刚才没有注意到你这里s是指定为${p-1}/9$的,关键在于最后一个条件.
所以可以取e=9使得最后一个条件得以简化

mathabc

mathe果真洞悉天机。
我忘了还有一个条件$ (9,e) = 1 $，这个条件忘了写上.
写程序不难，似乎计算量大的惊人.

[ 本帖最后由 mathabc 于 2009-4-20 13:55 编辑 ]

mathabc

原帖由 winxos 于 2009-4-19 20:12 发表

帖子的名字好像以前论坛里见大侠们讨论过。
我不懂。不过看你三组前面都是1 1，感觉有点简化题目了。

也没有简化题目，从最简单的算起，于是就从$ e=1, r=1 $ 开始。