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 $ 开始。