素数问题

rill

若想求一个161位二进制的大素数该如何实现呢？

win_hate

生成 161 位的随机数，并进行素性判定，用 Rabin-miller 算法。

THEBEST

可能楼主的关键问题是这么大一个数应该如何存储？

GuitarEX

[quote]原帖由 "THEBEST"]可能楼主的关键问题是这么大一个数应该如何存储？[/quote 发表：
关注！

FH

[quote]原帖由 "win_hate"]生成 161 位的随机数，并进行素性判定，用 Rabin-miller 算法。[/quote 发表：

我想这个数应该就是全'1'吧？
这不就是2的p次方-1的类型么？161是素数，呵呵。

win_hate

2^p-1 形的素数（其中 p 本身也素），称为梅森素数，这种素数极其稀少，难得碰上的。

161 不是素数，分解为 7*23

2^161-1 =2923003274661805836407369665432566039311865085951 也不是素数，可分解为：
(47)*(127)*(1289)*(45076044553)*(14808607715315782481)*(3188767)*(178481)

FH

[quote]原帖由 "win_hate"]2^161-1 =2923003274661805836407369665432566039311865085951[/quote 发表：

版主真专业！佩服！

THEBEST

原帖由 "FH" 发表：

我想这个数应该就是全'1'吧？
这不就是2的p次方-1的类型么？161是素数，呵呵。

为什么说是全1呢?

2^p-1 形的素数（其中 p 本身也素），称为梅森素数，这种素数极其稀少，难得碰上的。

161 不是素数，分解为 7*23

2^161-1 =2923003274661805836407369665432566039311865085951 也不是素数，可分解为：
(47)*(127)*(1289)*(45076044553)*(14808607715315782481)*(3188767)*(178481)

这么大一个数你是如何分解出来的呢?请指教.谢谢.

win_hate

有专门的数学软件算这个东西。比如 Mathematica, Maple, pari, MuPAD ....

上面那个数我是用 Maple 来算的。

>; ifactor (2^161-1);
...........................................................

在分解整数问题上，Mathematica 比 Maple 快。