multiplicative_order_from_phi.sf

#!/usr/bin/ruby

# Author: Trizen
# Date: 16 November 2021
# https://github.com/trizen

# Compute the multiplicative order of `a` modulo `n`: znorder(a, n).
# This is the smallest positive integer k such that a^k == 1 (mod n).

func prime_znorder(a, p, e) is cached {

    var m = p**e
    var t = (p-1)*(p**(e-1))

    t.divisors.first_by {|q| powmod(a, q, m) == 1 }
}

func my_znorder(a, m) {

    gcd(a, m) == 1 || die "#{a} and #{m} are not relatively prime"

    m.factor_map {|p,e| prime_znorder(a, p, e) }.lcm
}

## Run some tests

assert_eq(my_znorder(37, 1000), 100)
assert_eq(my_znorder(54, 100001), 9090)

with (10**20 - 1) {|b|
    assert_eq(my_znorder(2, b), 3748806900)
    assert_eq(my_znorder(17, b), 1499522760)
}

for a in ([2, 3, 6, 10]) {
    var t = 1e7.irand
    for n in (t .. t+1e3) {
        next if (gcd(a, n) != 1)
        assert_eq(my_znorder(a, n), znorder(a, n))
    }
}

## Example

for n in (2..20) {
    var a = (20 + 1e2.irand -> next_prime)
    var z = my_znorder(a, n!)
    assert_eq(z, znorder(a, n!))
    say "znorder(#{a}, #{n}!) = #{z}"
}