Anonymous user
Multiplicative order: Difference between revisions
m
added whitespace before the TOC (table of contents), added a ;Task: (bold) header, elided the use of "wrt" abbreviation in the algorithm description.
(→{{header|Ruby}}: corrected require (deprecated 'mathn'), add output) |
m (added whitespace before the TOC (table of contents), added a ;Task: (bold) header, elided the use of "wrt" abbreviation in the algorithm description.) |
||
Line 1:
{{task|Discrete math}}
The '''multiplicative order''' of ''a'' relative to ''m'' is the least positive integer ''n'' such that ''a^n'' is 1 (modulo ''m'').
For example, the multiplicative order of 37 relative to 1000 is 100 because 37^100 is 1 (modulo 1000), and no number smaller than 100 would do.▼
;Example:
▲
One possible algorithm that is efficient also for large numbers is the following: By the [[wp:Chinese_Remainder_Theorem|Chinese Remainder Theorem]], it's enough to calculate the multiplicative order for each prime exponent ''p^k'' of ''m'', and
combine the results with the ''[[least common multiple]]'' operation.
Now the order of ''a'' wrt. to ''p^k'' must divide ''Φ(p^k)''. Call this number ''t'', and determine it's factors ''q^e''. Since each multiple of the order will also yield 1 when used as exponent for ''a'', it's enough to find the least d such that ''(q^d)*(t/(q^e))'' yields 1 when used as exponent. ▼
▲Now the order of ''a''
;Task:
Implement a routine to calculate the multiplicative order along these lines. You may assume that routines to determine the factorization into prime powers are available in some library.
Line 16 ⟶ 24:
<p>Suppose you are given a prime<tt> p </tt>and a complete factorization
of<tt> p-1</tt>
element<tt> a </tt>in<tt> (Z/(p))<sup>*</sup> </tt>using<tt> O((lg p)<sup>4</sup>/(lg lg p)) </tt>bit
operations.</p>
Line 24 ⟶ 32:
<p>Let the prime factorization of<tt> p-1 </tt> be<tt> q1<sup>e1</sup>q2<sup>e2</sup>...qk<sup>ek</sup></tt> .<tt> </tt>We use the following observation:
if<tt> x^((p-1)/qi<sup>fi</sup>) = 1 (mod p)</tt> ,<tt> </tt>
and<tt> fi=ei </tt>or<tt> x^((p-1)/qi<sup>fi+1</sup>) != 1 (mod p)</tt> ,<tt> </tt>then<tt> qi<sup>ei-fi</sup>||ord<sub>p</sub> x</tt>. (This follows by combining Exercises 5.1 and 2.10.
Hence it suffices to find, for each<tt> i</tt> ,<tt> </tt>the exponent<tt> fi </tt> such that the condition above holds.</p>
Line 36 ⟶ 43:
Finally, for each<tt> i</tt> ,<tt> </tt>repeatedly raise<tt> xi </tt>to the<tt> qi</tt>-th power<tt> (mod p) </tt>(as many as<tt> ei-1 </tt> times), checking to see when 1 is obtained.
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((lg p)<sup>4</sup>/(lg lg p))</tt>
<br><br>
=={{header|Ada}}==
| |||