Anonymous user
Multiplicative order: Difference between revisions
Added Ada code
m (least common multiple becomes a hyperlink. I will create the page soon.) |
(Added Ada code) |
||
Line 37:
This can be done using<tt> O((lg p)<sup>3</sup>) </tt>steps.
The total cost is dominated by<tt> O(k(lg p)<sup>3</sup>)</tt> ,<tt> </tt>which is<tt> O(k(lg p)<sup>4</sup>/(lg lg p))</tt> .
=={{header|Ada}}==
Instead of assuming a library call to factorize the modulus, we assume the caller of our Find_Order function has already factorized it. The Multiplicative_Order package is specified as follows ("multiplicative_order.ads").
<lang Ada>package Multiplicative_Order is
type Positive_Array is array (Positive range <>) of Positive;
function Find_Order(Element, Modulus: Positive) return Positive;
-- naive algorithm
-- returns the smallest I such that (Element**I) mod Modulus = 1
function Find_Order(Element: Positive;
Coprime_Factors: Positive_Array) return Positive;
-- faster algorithm for the same task
-- computes the order of all Coprime_Factors(I)
-- and returns their least common multiple
-- this gives the same result as Find_Order(Element, Modulus)
-- with Modulus being the product of all the Coprime_Factors(I)
--
-- preconditions: (1) 1 = GCD(Coprime_Factors(I), Coprime_Factors(J))
-- for all pairs I, I with I /= J
-- (2) 1 < Coprime_Factors(I) for all I
end Multiplicative_Order;</lang>
Here is the implementation ("multiplicative_order.adb"):
<lang Ada>package body Multiplicative_Order is
function Find_Order(Element, Modulus: Positive) return Positive is
function Power(Exp, Pow, M: Positive) return Positive is
-- computes Exp**Pow mod M;
-- note that Ada's native integer exponentiation "**" may overflow on
-- computing Exp**Pow before ever computing the "mod M" part
Result: Positive := 1;
E: Positive := Exp;
P: Natural := Pow;
begin
while P > 0 loop
if P mod 2 = 1 then
Result := (Result * E) mod M;
end if;
E := (E * E) mod M;
P := P / 2;
end loop;
return Result;
end Power;
begin -- Find_Order(Element, Modulus)
for I in 1 .. Modulus loop
if Power(Element, I, Modulus) = 1 then
return Positive(I);
end if;
end loop;
raise Program_Error with
Positive'Image(Element) &" is not coprime to" &Positive'Image(Modulus);
end Find_Order;
function Find_Order(Element: Positive;
Coprime_Factors: Positive_Array) return Positive is
function GCD (A, B : Positive) return Integer is
M : Natural := A;
N : Natural := B;
T : Natural;
begin
while N /= 0 loop
T := M;
M := N;
N ;:= T mod N;
end loop;
return M;
end GCD; -- from http://rosettacode.org/wiki/Least_common_multiple#Ada
function LCM (A, B : Natural) return Integer is
begin
if A = 0 or B = 0 then
return 0;
end if;
return abs (A * B) / Gcd (A, B);
end LCM; -- from http://rosettacode.org/wiki/Least_common_multiple#Ada
Result : Positive := 1;
begin -- Find_Order(Element, Coprime_Factors)
for I in Coprime_Factors'Range loop
Result := LCM(Result, Find_Order(Element, Coprime_Factors(I)));
end loop;
return Result;
end Find_Order;
end Multiplicative_Order;</lang>
This is a sample program using the Multiplicative_Order package:
<lang Ada>with Ada.Text_IO, Multiplicative_Order;
procedure Main is
package IIO is new Ada.Text_IO.Integer_IO(Integer);
use Multiplicative_Order;
begin
IIO.Put(Find_Order(3,10));
IIO.Put(Find_Order(37,1000));
IIO.Put(Find_Order(37,10_000));
IIO.Put(Find_Order(37, 3343));
IIO.Put(Find_Order(37, 3344));
-- IIO.Put(Find_Order( 2,1000));
--would raise Program_Error, because there is no I with 2**I=1 mod 1000
Ada.Text_IO.New_Line;
IIO.Put(Find_Order(3, (2,5))); -- 3 * 5 = 10
IIO.Put(Find_Order(37, (8, 125))); -- 8 * 125 = 1000
IIO.Put(Find_Order(37, (16, 625))); -- 16 * 625 = 10_000
IIO.Put(Find_Order(37, (1 => 3343))); -- 1-element-array: 3343 is a prime
IIO.Put(Find_Order(37, (11, 19, 16))); -- 11 * 19 * 16 = 3344
-- the following gives a wrong result, because 8 and 2 are not coprime
IIO.Put(Find_Order(37, (11, 19, 8, 2)));
end Main;</lang>
The output from the sample program:
<pre>
4 100 500 1114 20
4 100 500 1114 20 10
</pre>
=={{header|ALGOL 68}}==
{{trans|python}}
| |||