## Re: 2 questions

Expand Messages
• ... This is part of the information contained in the above reference: If flag = 0, checks whether x is a Baillie-Pomerance-Selfridge-Wagstaff pseudo prime
Message 1 of 27 , Apr 9, 2011
--- In primenumbers@yahoogroups.com, Maximilian Hasler <maximilian.hasler@...> wrote:
>
> Did you try
>
> > ?? ispseudoprime
>
> You should get something equivalent to
> http://pari.math.u-bordeaux.fr/dochtml/html/Arithmetic_functions.html#ispseudoprime
>

This is part of the information contained in the above reference:

"If flag = 0, checks whether x is a Baillie-Pomerance-Selfridge-Wagstaff pseudo prime (strong Rabin-Miller pseudo prime for base 2, followed by strong Lucas test for the sequence (P,-1), P smallest positive integer such that P^2 - 4 is not a square mod x)".

I am curious as to the nuts and bolts of applying these techniques.
Are there pages of abstract complexities that need to be computed
to get a result, or does the whole thing boil down to a few lines
of code?

Thanks a million, Max.

Aldrich
• I discussed the Baillie-Wagstaff primality checker at my blog . Here s the latest
Message 2 of 27 , Apr 12, 2011
I discussed the Baillie-Wagstaff primality checker at my blog
<http://programmingpraxis.com/2010/01/26/primality-checking-revisited/>
. Here's the latest version of source code, in Scheme, which differs
slightly from the original entry; it's more than "a few lines" of code,
but not too long:
(define (prime? n) (letrec ( (expm (lambda (b e m) (let ((times
(lambda (x y) (modulo (* x y) m)))) (cond ((zero? e) 1) ((even?
e) (expm (times b b) (/ e 2) m)) (else (times b (expm (times b b)
(/ (- e 1) 2) m))))))) (digits (lambda (n) (let loop ((n n) (ds
'())) (if (zero? n) ds (loop (quotient n 2) (cons (modulo n 2)
ds)))))) (isqrt (lambda (n) (let loop ((x n) (y (quotient (+ n
1) 2))) (if (<= 0 (- y x) 1) x (loop y (quotient (+ y (quotient n
y)) 2)))))) (square? (lambda (n) (let ((n2 (isqrt n))) (= n (* n2
n2))))) (jacobi (lambda (a n) (let loop ((a a) (n n))
(cond ((= a 0) 0) ((= a 1) 1) ((= a 2) (case (modulo n 8)
((1 7) 1) ((3 5) -1))) ((even? a) (* (loop 2 n) (loop (/ a
2) n))) ((< n a) (loop (modulo a n) n)) ((and
(= (modulo a 4) 3) (= (modulo n 4) 3)) (- (loop n a)))
(else (loop n a)))))) (inverse (lambda (x m) (let loop ((a 1) (b
0) (g x) (u 0) (v 1) (w m)) (if (zero? w) (modulo a m)
(let ((q (quotient g w))) (loop u v w (- a (* q u)) (- b (* q
v)) (- g (* q w)))))))) (strong-pseudo-prime? (lambda (n a) (let
loop ((r 0) (s (- n 1))) (if (even? s) (loop (+ r 1) (/ s 2))
(if (= (expm a s n) 1) #t (let loop ((r r) (s s))
(cond ((zero? r) #f) ((= (expm a s n) (- n 1)) #t) (else
(loop (- r 1) (* s 2)))))))))) (chain (lambda (m f g u v) (let
loop ((ms (digits m)) (u u) (v v)) (cond ((null? ms) (values u
v)) ((zero? (car ms)) (loop (cdr ms) (f u) (g u v)))
(else (loop (cdr ms) (g u v) (f v))))))) (lucas-pseudo-prime? (lambda
(n) (let loop ((a 11) (b 7)) (let ((d (- (* a a) (* 4 b))))
(cond ((square? d) (loop (+ a 2) (+ b 1))) ((not (= (gcd
n (* 2 a b d)) 1)) (loop (+ a 2) (+ b 2))) (else (let*
((x1 (modulo (- (* a a (inverse b n)) 2) n))
(m (quotient (- n (jacobi d n)) 2)) (f
(lambda (u) (modulo (- (* u u) 2) n))) (g
(lambda (u v) (modulo (- (* u v) x1) n))))
(let-values (((xm xm1) (chain m f g 2 x1)))
(zero? (modulo (- (* x1 xm) (* 2 xm1)) n))))))))))) (if (not
(integer? n)) (error 'prime? "must be integer") (if (< n 2) #f (if
(even? n) (= n 2) (if (zero? (modulo n 3)) (= n 3) (and
(strong-pseudo-prime? n 2) (strong-pseudo-prime? n 3)
(lucas-pseudo-prime? n))))))))

--- In primenumbers@yahoogroups.com, "Aldrich" <aldrich617@...> wrote:
>
>
>
>
>
>
>
>
> --- In primenumbers@yahoogroups.com, Maximilian Hasler
maximilian.hasler@ wrote:
> >
> > Did you try
> >
> > > ?? ispseudoprime
> >
> > You should get something equivalent to
> >
http://pari.math.u-bordeaux.fr/dochtml/html/Arithmetic_functions.html#is\
pseudoprime
> >
>
> This is part of the information contained in the above reference:
>
> "If flag = 0, checks whether x is a
Baillie-Pomerance-Selfridge-Wagstaff pseudo prime (strong Rabin-Miller
pseudo prime for base 2, followed by strong Lucas test for the sequence
(P,-1), P smallest positive integer such that P^2 - 4 is not a square
mod x)".
>
> I am curious as to the nuts and bolts of applying these techniques.
> Are there pages of abstract complexities that need to be computed
> to get a result, or does the whole thing boil down to a few lines
> of code?
>
> Thanks a million, Max.
>
> Aldrich
>

[Non-text portions of this message have been removed]
• ... Well, its certainly a lot more calculation than simply recording a 1 or 2 as each prime candidate in a long chain appears. PARI can check primality of
Message 3 of 27 , Apr 22, 2011
--- In primenumbers@yahoogroups.com, "Phil" <philiplouisbewig@...> wrote:
>
> I discussed the Baillie-Wagstaff primality checker at my blog
> <http://programmingpraxis.com/2010/01/26/primality-checking-revisited/>
> . Here's the latest version of source code, in Scheme, which differs
> slightly from the original entry; it's more than "a few lines" of code,
> but not too long:
> (define (prime? n) (letrec ( (expm (lambda (b e m) (let ((times
> (lambda (x y) (modulo (* x y) m)))) (cond ((zero? e) 1) ((even?
> e) (expm (times b b) (/ e 2) m)) (else (times b (expm (times b b)
> (/ (- e 1) 2) m))))))) (digits (lambda (n) (let loop ((n n) (ds
> '())) (if (zero? n) ds (loop (quotient n 2) (cons (modulo n 2)
> ds)))))) (isqrt (lambda (n) (let loop ((x n) (y (quotient (+ n
> 1) 2))) (if (<= 0 (- y x) 1) x (loop y (quotient (+ y (quotient n
> y)) 2)))))) (square? (lambda (n) (let ((n2 (isqrt n))) (= n (* n2
> n2))))) (jacobi (lambda (a n) (let loop ((a a) (n n))
> (cond ((= a 0) 0) ((= a 1) 1) ((= a 2) (case (modulo n 8)
> ((1 7) 1) ((3 5) -1))) ((even? a) (* (loop 2 n) (loop (/ a
> 2) n))) ((< n a) (loop (modulo a n) n)) ((and
> (= (modulo a 4) 3) (= (modulo n 4) 3)) (- (loop n a)))
> (else (loop n a)))))) (inverse (lambda (x m) (let loop ((a 1) (b
> 0) (g x) (u 0) (v 1) (w m)) (if (zero? w) (modulo a m)
> (let ((q (quotient g w))) (loop u v w (- a (* q u)) (- b (* q
> v)) (- g (* q w)))))))) (strong-pseudo-prime? (lambda (n a) (let
> loop ((r 0) (s (- n 1))) (if (even? s) (loop (+ r 1) (/ s 2))
> (if (= (expm a s n) 1) #t (let loop ((r r) (s s))
> (cond ((zero? r) #f) ((= (expm a s n) (- n 1)) #t) (else
> (loop (- r 1) (* s 2)))))))))) (chain (lambda (m f g u v) (let
> loop ((ms (digits m)) (u u) (v v)) (cond ((null? ms) (values u
> v)) ((zero? (car ms)) (loop (cdr ms) (f u) (g u v)))
> (else (loop (cdr ms) (g u v) (f v))))))) (lucas-pseudo-prime? (lambda
> (n) (let loop ((a 11) (b 7)) (let ((d (- (* a a) (* 4 b))))
> (cond ((square? d) (loop (+ a 2) (+ b 1))) ((not (= (gcd
> n (* 2 a b d)) 1)) (loop (+ a 2) (+ b 2))) (else (let*
> ((x1 (modulo (- (* a a (inverse b n)) 2) n))
> (m (quotient (- n (jacobi d n)) 2)) (f
> (lambda (u) (modulo (- (* u u) 2) n))) (g
> (lambda (u v) (modulo (- (* u v) x1) n))))
> (let-values (((xm xm1) (chain m f g 2 x1)))
> (zero? (modulo (- (* x1 xm) (* 2 xm1)) n))))))))))) (if (not
> (integer? n)) (error 'prime? "must be integer") (if (< n 2) #f (if
> (even? n) (= n 2) (if (zero? (modulo n 3)) (= n 3) (and
> (strong-pseudo-prime? n 2) (strong-pseudo-prime? n 3)
> (lucas-pseudo-prime? n))))))))
>
>

Well, its certainly a lot more calculation than simply recording
a '1' or '2' as each prime candidate in a long chain appears.
PARI can check primality of 19-20 digit integers at a rate of
about 8000/sec, according to Maximillian, so I would expect
Praxis to be a bit slower. My primitive pm2 hit 11500/sec when
I put it into a Lazarus FreePascal compiler on a Pentium4, so I
feel it has potential. I would have to seriously upgrade my
programming skills to see how far the idea can really go
however. Somebody please shoot it down - my brain hurts!
Its pretty easy to check out even if Pascal is not your bag.