Loading ...
Sorry, an error occurred while loading the content.
 

Re: 2 questions

Expand Messages
  • Aldrich
    ... 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:
      >
      > ad Q2:
      > 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
    • Phil
      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:
        > >
        > > 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]
      • Aldrich
        ... 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.
          Just download Lazarus and put the program from my Primemine2
          posting in the source editor starting at the line 'type ='.
          Piece of cake.

          Aldrich
        Your message has been successfully submitted and would be delivered to recipients shortly.