+- 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
;