Modular inverse: Difference between revisions

</pre>

=={{header|RPL}}==

Using complex numbers allows to ‘parallelize’ calculations and keeps the stack depth low: never more than 4 levels despite the simultaneous use of 6 variables: r, r’, u, u’, q - and b for the final touch.

{{works with|Halcyon Calc|4.2.7}}

{| class="wikitable"

! RPL code

! Comment

|-

|

≪

DUP ROT 1 R→C ROT 0 R→C

'''WHILE''' DUP RE '''REPEAT'''

OVER RE OVER RE / FLOOR

OVER * NEG ROT +

'''END'''

DROP C→R ROT MOD

SWAP 1 == SWAP 0 IFTE

≫ ‘'''MODINV'''’ STO

|

'''MODINV''' ''( a b -- x )'' with ax = 1 mod b

3: b 2: (r,u)←(a,1) 1:(r',u')←(b,0)

While r' ≠ 0

q ← r // r'

(r - q*r', u - q*u')

Forget (r',u') and calculate u mod b

Test r and return zero if a and b are not co-prime

|}

{{in}}

<pre>

123 456 MODINV

42 2017 MODINV

</pre>

{{out}}

<pre>

2: 1969

1: 0