mersenneforum.org > Math Baillie-PSW Primality Test
 Register FAQ Search Today's Posts Mark Forums Read

 2009-05-16, 18:27 #1 flouran     Dec 2008 72×17 Posts 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

 Similar Threads Thread Thread Starter Forum Replies Last Post Trilo Miscellaneous Math 25 2018-03-11 23:20 shawn Miscellaneous Math 5 2007-07-17 17:55 Citrix Math 3 2005-09-19 15:06 Guilherme Math 2 2004-11-26 05:29 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