123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051 |
- #!/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}"
- }
|