37 lines
871 B
Plaintext
37 lines
871 B
Plaintext
# Integer division:
|
|
# If $j is 0, then an error condition is raised;
|
|
# otherwise, assuming infinite-precision integer arithmetic,
|
|
# if the input and $j are integers, then the result will be an integer.
|
|
def idivide($j):
|
|
. as $i
|
|
| ($i % $j) as $mod
|
|
| ($i - $mod) / $j ;
|
|
|
|
# the multiplicative inverse of . modulo $n
|
|
def modInv($n):
|
|
if $n == 1 then 1
|
|
else . as $this
|
|
| { r : $n,
|
|
t : 0,
|
|
newR: length, # abs
|
|
newT: 1}
|
|
| until(.newR == 0;
|
|
.newR as $newR
|
|
| (.r | idivide($newR)) as $q
|
|
| {r : $newR,
|
|
t : .newT,
|
|
newT: (.t - $q * .newT),
|
|
newR: (.r - $q * $newR) } )
|
|
|
|
| if (.r|length) != 1 then "\($this) and \($n) are not co-prime." | error
|
|
else .t
|
|
| if . < 0 then . + $n
|
|
elif $this < 0 then - .
|
|
else .
|
|
end
|
|
end
|
|
end ;
|
|
|
|
# Example:
|
|
42 | modInv(2017)
|