(50G) Discrete Log Modulo a Prime - Printable Version +- HP Forums (https://www.hpmuseum.org/forum) +-- Forum: HP Software Libraries (/forum-10.html) +--- Forum: General Software Library (/forum-13.html) +--- Thread: (50G) Discrete Log Modulo a Prime (/thread-7925.html) (50G) Discrete Log Modulo a Prime - Gerald H - 03-12-2017 07:59 AM 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 ;```