Post Reply 
(50g) Fibonnaci Pseudoprime Test & Prime Test
02-17-2019, 05:47 PM (This post was last modified: 02-18-2019 06:13 AM by Gerald H.)
Post: #1
(50g) Fibonnaci Pseudoprime Test & Prime Test
Edited as per next posting 2019-02-18.

Designating the members of Fibonnaci sequence

0,1,1,2,3,5......

as

f(0), f(1), f(2), f(3), f(4), f(5).......

and setting for integer N

g(N) := 1 if N = +/-1 mod 5
g(N) := -1 if N = +/-2 mod 5
g(N) := 0 if N = 0 mod 5

then if integer N is prime

f(N - g(N)) = 0 mod N.

The programme below runs the above test speedily.

Caveat: Some composite numbers, Fibonnaci pseudoprimes, pass the test, the programme erroneously returning 1, indicating primality, rather than 0.

However no number of the form

N = +/-2 mod 5

which passes the above test & is a base 2 pseudoprime has been shown to be composite (as of 2019-02-17, ref Crandall & Pomerance, Prime Numbers).



Size: 320.

CkSum: # ECD0h

Code:
::
  CK1&Dispatch
  # FF
  ::
    ::
      FPTR2 ^ZABS
      FPTR2 ^DupZIsTwo?
      casedrptru
      FPTR2 ^DupZIsEven?
      casedrpfls
      DUP
      ZINT 5
      Z=
      casedrptru
      DUP
      ZINT 5
      FPTR2 ^QMod
      FPTR2 ^ZABS
      FPTR2 ^DupQIsZero?
      case2drpfls
      FPTR2 ^ZIsOne?
      ITE
      ZINT -1
      ZINT 1
      OVER
      FPTR2 ^QAdd
      SWAP
      ::
        SWAPDUP
        ZINT 2
        Z<
        case
        SWAPDROP
        FPTR2 ^Z>ZH
        ZINT -2
        ZINT 0
        ZINT 1
        4PICK
        FPTR2 ^ZBits
        SWAPDROP#1-_
        ZERO_DO
        FPTR2 ^ZSQ_
        5PICK
        FPTR2 ^ZMod
        SWAP
        FPTR2 ^ZSQ_
        5PICK
        FPTR2 ^ZMod
        2DUP
        FPTR2 ^RSUBext
        DUP
        FPTR2 ^RADDext
        3PICK
        FPTR2 ^RADDext
        3UNROLL
        FPTR2 ^RADDext
        SWAPROT
        FPTR2 ^RADDext
        3PICK
        ISTOP-INDEX
        #1-
        FPTR2 ^ZBit?
        SWAPDROP
        ITE
        ::
          DUPUNROT
          FPTR2 ^QAdd
          ZINT -2
        ;
        ZINT 2
        3UNROLL
        LOOP
        4UNROLL3DROP
        SWAP
        FPTR2 ^Mod
      ;
      FPTR2 ^QIsZero?
    ;
    COERCEFLAG
  ;
;
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
(50g) Fibonnaci Pseudoprime Test & Prime Test - Gerald H - 02-17-2019 05:47 PM



User(s) browsing this thread: 1 Guest(s)