(50G) Discrete Log Modulo a Prime

[Gerald H]

For input P a prime, B a primitive root of P & N an integer the programme finds the discrete logarithm of N for base B modulo P.

For info on discrete logarithms please see

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

For a programme to test primitiveness see

http://www.hpmuseum.org/forum/thread-7924.html

eg

For input

10007
666
1953

the programme returns

9868

meaning

666 ^ 9868 = 1953 mod 10007.

Code:


::
  CK3
  FPTR2 ^CK3Z
  SWAPROT
  FPTR2 ^ZAbs
  DUPDUP
  ::
    FPTR2 ^ISPRIME
    %0<>
    ?SEMI
    # DE1E
    ERROROUT
  ;
  4ROLL
  OVER
  FPTR2 ^QMod
  4UNROLL
  ZINT 1099509530599
  Z>
  caseSIZEERR
  DUP
  FPTR2 ^ZSQRT
  FPTR2 ^DROPZ1
  FPTR2 ^RADDext
  DUP
  FPTR2 ^Z2BIN
  '
  NULLLAM
  BINT5
  NDUPN
  DOBIND
  4GETLAM
  2GETLAM
  3GETLAM
  FPTR2 ^ModPow
  3GETLAM
  FPTR2 ^QMod
  DUP
  1GETLAM
  ONE_DO
  2DUP
  FPTR2 ^RMULText
  3GETLAM
  FPTR2 ^QMod
  SWAPLOOP
  DROP
  1GETLAM
  {}N
  4GETLAM
  3GETLAM
  FPTR 6 3CA
  5GETLAM
  1GETLAM
  ZERO_DO
  DUP
  4PICK
  FPTR2 ^ListPos
  ::
    DUP#0=csedrp
    ::
      OVER
      FPTR2 ^RMULText
      3GETLAM
    ;
    4UNROLL3DROP
    FPTR2 ^#>Z
    2GETLAM
    FPTR2 ^RMULText
    INDEX@
    FPTR2 ^#>Z
    FPTR2 ^RADDext
    3GETLAM
    Z1_
    FPTR2 ^RSUBext
    ExitAtLOOP
  ;
  FPTR2 ^QMod
  LOOP
  3GETLAM
  Z1_
  FPTR2 ^RSUBext
  FPTR2 ^Mod
  ABND
;