1 // This file is part of the FXT library.
2 // Copyright (C) 2010, 2011, 2012 Joerg Arndt
3 // License: GNU General Public License version 3 or later,
4 // see the file COPYING.txt in the main directory.
5
6 #include "mod/factor.h"
7 #include "mod/primes.h"
8 #include "mod/numtheory.h"
9
10 #include "aux0/gcd.h"
11 #include "fxttypes.h"
12
13
14
15 //#define MO_DEBUG // define for debug
16 #ifdef MO_DEBUG
17 #warning '******** MO_DEBUG'
18 #include "jjassert.h"
19 #endif
20
21
22 umod_t
maxorder_mod(const factorization & modfact)23 maxorder_mod(const factorization &modfact)
24 // Return the maximal order in the group of units (Z/mZ)*
25 // modfact must be the factorization of m.
26 //
27 // If m = 2^e0 * \prod_i{p_i^{e_i}} i=1...k
28 // Then maxorder = lcm(f0,f1,f2,...,fk)
29 // where f0 = 2^e0 if e0 \in {0,1,2}, else (2^e0)/2
30 // and fi = euler_phi(p_i^{e_i}) = (p_i-1) * p_i^{e_i-1}
31 {
32 ulong k = 0;
33 umod_t m = 1;
34 if ( 2 == modfact.prime(0) )
35 {
36 ulong e = modfact.exponent(0);
37 m = ( 1ULL << (e-1) );
38 if ( modfact.exponent(0) >= 3 ) m >>= 1;
39 k++;
40 }
41
42 while ( k < modfact.nprimes() )
43 {
44 umod_t f = euler_phi(modfact.prime(k), modfact.exponent(k));
45 m = lcm(m, f);
46 k++;
47 }
48
49 return m;
50 }
51 // -------------------------
52
53
54 umod_t
maxorder_element_mod(const factorization & modfact,const factorization & phifact)55 maxorder_element_mod(const factorization &modfact,
56 const factorization &phifact)
57 // Return element of maximal order modulo m.
58 // modfact must be the factorization of m,
59 // phifact must be the factorization of euler_phi(m)
60 {
61 umod_t m = modfact.product();
62 if ( m==2 ) return 1;
63
64 umod_t mo = maxorder_mod(modfact);
65 for (umod_t x=2; x<m; ++x)
66 {
67 umod_t xo = order_mod(x, m, phifact);
68 if ( mo == xo ) return x;
69 }
70
71 #ifdef MO_DEBUG
72 // cannot happen, maxorder element is found before:
73 cout << " m=" << m << " mo=" << mo << endl;
74 cout << " m=" << modfact.product() << " == " << modfact << endl;
75 cout << " phi=" << phifact.product() << " == " << phifact << endl;
76
77 jjassert( modfact.check() );
78 jjassert( phifact.check() );
79
80 jjassert( 0 ); // maxorder_element() failed.
81 #endif
82 return 0;
83 }
84 // -------------------------
85