mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-05-16, 18:27   #1
flouran
 
flouran's Avatar
 
Dec 2008

72×17 Posts
Default Baillie-PSW Primality Test

Mathworld states that the BPSW test adheres to the following steps:
1. Perform a base-2 strong pseudoprime test on http://mathworld.wolfram.com/images/...st/Inline1.gif. If this test fails, declare http://mathworld.wolfram.com/images/...st/Inline2.gif composite and halt. If this test success, http://mathworld.wolfram.com/images/...st/Inline3.gif is probably prime. Proceed to step 2.
2. In the sequence 5, http://mathworld.wolfram.com/images/...st/Inline4.gif, 9, http://mathworld.wolfram.com/images/...st/Inline5.gif, 13, ..., find the first number http://mathworld.wolfram.com/images/...st/Inline6.gif for which the Jacobi symbol http://mathworld.wolfram.com/images/...st/Inline7.gif. Then perform a Lucas pseudoprime test with discriminant http://mathworld.wolfram.com/images/...st/Inline8.gif on http://mathworld.wolfram.com/images/...st/Inline9.gif. If this test fails, declare http://mathworld.wolfram.com/images/...t/Inline10.gif composite. It if succeeds, http://mathworld.wolfram.com/images/...t/Inline11.gif is very probably prime.

Note: Sorry for the many links in the latter statement. Just go to the mathworld link I provided and view it there....

I know that step 1 takes \tilde{O}(\log^2 n) time, but how long does step 2 take (I am guessing \tilde{O}(\log^2 n) time)? Also, how long does an Extra Strong Lucas Pseudoprime Test take (is there even one?), if it replaces the Lucas pseudoprime test in step 2?

Last fiddled with by flouran on 2009-05-16 at 18:27
flouran is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Modifying the Lucas Lehmer Primality Test into a fast test of nothing Trilo Miscellaneous Math 25 2018-03-11 23:20
there is another way to test the primality of a no shawn Miscellaneous Math 5 2007-07-17 17:55
N-1 primality test Citrix Math 3 2005-09-19 15:06
AKS Primality Test Guilherme Math 2 2004-11-26 05:29
A primality test for Fermat numbers faster than P├ępin's test ? T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 19:29.

Mon Sep 21 19:29:08 UTC 2020 up 11 days, 16:40, 1 user, load averages: 2.71, 2.64, 2.24

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.