Go Back > Great Internet Mersenne Prime Search > Math

Thread Tools
Old 2009-05-16, 18:27   #1
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 If this test fails, declare composite and halt. If this test success, is probably prime. Proceed to step 2.
2. In the sequence 5,, 9,, 13, ..., find the first number for which the Jacobi symbol Then perform a Lucas pseudoprime test with discriminant on If this test fails, declare composite. It if succeeds, 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

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.