(50G) Primitive Root Modulo a Prime

[Gerald H]

For input P a prime & N an integer the programme tests whether N is a primitive root for P, returning 1 for yes, 0 for no.

For info on primitive roots please see

https://en.wikipedia.org/wiki/Primitive_root_modulo_n

eg

For input

10007
666

the programme returns

1.

indicating that 666 is a primitive root of 10007.

Code:


::
  CK2&Dispatch
  # FFFF
  ::
    SWAP
    FPTR2 ^ZABS
    FPTR2 ^DupZIsTwo?
    casedrop
    ::
      FPTR2 ^ZIsOne?
      COERCEFLAG
    ;
    DUP
    ::
      FPTR2 ^ISPRIME
      %0<>
      ?SEMI
      # DE1E
      ERROROUT
    ;
    DUP
    Z1_
    FPTR2 ^QSub
    DUP
    FPTR2 ^MZSQFF
    NULL{}
    SWAP
    #2/
    DUPUNROT
    ZERO_DO
    2SWAP
    DROP
    >TCOMP
    LOOP
    SWAPROT
    FPTR2 ^2LAMBIND
    ROT
    ::
      DUP
      FPTR2 ^ZSQRT
      SWAPDROP
      caseFALSE
      3PICK
      FPTR2 ^ZMod
      FPTR2 ^DupQIsZero?
      caseFALSE
      TRUE
      4UNROLL
      2GETLAM
      #1+_ONE_DO
      DUP
      1GETLAM
      4PICK
      INDEX@
      NTHCOMPDROP
      FPTR2 ^ZQUOText
      5PICK
      FPTR2 ^ModPow
      4PICK
      FPTR2 ^QMod
      FPTR2 ^ZIsOne?
      IT
      ::
        4ROLLDROP
        FALSE
        4UNROLL
        ExitAtLOOP
      ;
      LOOP
      4ROLL
    ;
    ABND
    4UNROLL3DROP
    COERCEFLAG
  ;
;