Multiplicative order: Difference between revisions
Content added Content deleted
(Added EchoLisp) |
(→{{header|Ruby}}: corrected require (deprecated 'mathn'), add output) |
||
| Line 858: | Line 858: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
<lang ruby>require ' |
<lang ruby>require 'prime' |
||
require 'mathn' # for prime_division |
|||
def powerMod(b, p, m) |
def powerMod(b, p, m) |
||
p.to_s(2).each_char.inject(1) do |result, bit| |
|||
result = 1 |
|||
bits = p.to_s(2) |
|||
for bit in bits.split('') |
|||
result = (result * result) % m |
result = (result * result) % m |
||
bit=='1' ? (result * b) % m : result |
|||
result = (result * b) % m |
|||
end |
|||
end |
end |
||
result |
|||
end |
end |
||
| Line 878: | Line 872: | ||
r = 1 |
r = 1 |
||
for q, e in t.prime_division |
for q, e in t.prime_division |
||
x = powerMod(a, t / q |
x = powerMod(a, t / q**e, pk) |
||
while x != 1 |
while x != 1 |
||
r *= q |
r *= q |
||
| Line 888: | Line 882: | ||
def multOrder(a, m) |
def multOrder(a, m) |
||
m.prime_division.inject(1) |
m.prime_division.inject(1) do |result, f| |
||
result.lcm(multOrder_(a, *f)) |
result.lcm(multOrder_(a, *f)) |
||
end |
|||
end |
end |
||
puts multOrder(37, 1000) |
puts multOrder(37, 1000) |
||
b = 10**20-1 |
b = 10**20-1 |
||
puts multOrder(2, b) |
puts multOrder(2, b) |
||
puts multOrder(17,b) |
puts multOrder(17,b) |
||
b = 100001 |
b = 100001 |
||
puts multOrder(54,b) |
puts multOrder(54,b) |
||
| Line 905: | Line 899: | ||
puts 'Everything checks.' |
puts 'Everything checks.' |
||
end</lang> |
end</lang> |
||
{{out}} |
|||
<pre> |
|||
100 |
|||
3748806900 |
|||
1499522760 |
|||
9090 |
|||
1 |
|||
Everything checks. |
|||
</pre> |
|||
=={{header|Seed7}}== |
=={{header|Seed7}}== |
||