1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162 |
- #!/usr/bin/ruby
- # Author: Trizen
- # Date: 15 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).
- # Another approach would be to compute the Carmichael lambda function of n and
- # then find the smallest divisor d of this value that satisfy a^d == 1 (mod n).
- func my_znorder(a, n) is cached {
- gcd(a, n) == 1 || die "#{a} and #{n} are not relatively prime"
- if (n.is_prime) {
- return (n.dec.divisors.first {|d| powmod(a, d, n) == 1 })
- }
- if (n.is_prime_power) {
- var p = n.prime_root
- var z = __FUNC__(a, p)
- while (powmod(a, z, n) != 1) {
- z *= p
- }
- return z
- }
- n.factor_map {|p,e| __FUNC__(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}"
- }
|