Q

素数的莱曼测试

cryptography

2011-12-02 41 views -6 likes

-6

我在我的大学学习密码学，我需要编写一个测试数字作为素数的应用程序。素数的莱曼测试

我必须使用莱曼测试，但我什么都不知道。请描述算法或给我一个例子（Java，C＃，C++等）。感谢您的帮助。

2011-12-02 user1023177

+0

http://www.willwork.org/ics623/Week9.html – Asaph

+2

不，对不起。这是一个编程问答网站，而不是本科的家庭作业完成服务。 – Widor

+1

你的意思是“Lukas-Lehmer”测试，我猜？为什么不从维基百科开始http://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test？ –

A

回答

1

让我们打电话给PP您的潜力总理。

（1）选择一个随机数a小于PP。（2）计算^（p-1）/ 2 mod PP。（3）如果a（PP-1）/ 2/= 1或-1（mod PP），则PP不是素数。（4）如果a（PP-1）/ 2 = 1或-1（mod PP），那么PP不是素数的概率小于50％。

2011-12-02 14:23:36 Kheldar

+0

那么如何使用最后的公式1 - 1/2^k？我需要找出一个数字是或不是素数的总体概率。请帮忙。 –

相关问题