- ad Q2:

Did you try

> ?? ispseudoprime

You should get something equivalent to

http://pari.math.u-bordeaux.fr/dochtml/html/Arithmetic_functions.html#ispseudoprime

Maximilian

On Wed, Apr 6, 2011 at 10:42 PM, James Merickel <merk7777777@...> wrote:

> Hello, fellow primenumbers group members. I have a couple of questions, one specific one on a certain class of numbers and one on software.

> (...)

> The second question concerns PARI/GP's ispseudoprime( ) function. As far as all I have done experimentally shows, it seems I could possibly run tests using this until 'the cows come home' without getting a false positive. Does anybody have info on the heuristic probability by size of such and know if one has ever been found? Does anyone know exactly which pseudoprime tests exactly go into the function? Does it seem reasonable to submit the counts by n for the first question to OEIS with a caveat this function was employed, or should it be considered overly optimistic on the function and simply withheld aside from values that have sustained stronger attack?

>

> James G. Merickel

> - --- In primenumbers@yahoogroups.com, Maximilian Hasler <maximilian.hasler@...> wrote:
>

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

> ad Q2:

> Did you try

>

> > ?? ispseudoprime

>

> You should get something equivalent to

> http://pari.math.u-bordeaux.fr/dochtml/html/Arithmetic_functions.html#ispseudoprime

>

"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

<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:

> >

> > ad Q2:

> > 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] - --- In primenumbers@yahoogroups.com, "Phil" <philiplouisbewig@...> wrote:
>

Well, its certainly a lot more calculation than simply recording

> 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))))))))

>

>

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.

Just download Lazarus and put the program from my Primemine2

posting in the source editor starting at the line 'type ='.

Piece of cake.

Aldrich