{-| module : Data.Number.Flint.Groups.Dirichlet.FFI copyright : (c) 2022 Hartmut Monien license : GNU GPL, version 2 or above (see LICENSE) maintainer : hmonien@uni-bonn.de -} module Data.Number.Flint.Groups.Dirichlet.FFI ( -- * Dirichlet characters -- * Multiplicative group modulo /q/ DirichletGroup (..) , CDirichletGroup (..) , newDirichletGroup , withDirichletGroup , withNewDirichletGroup , dirichlet_group_init , dirichlet_subgroup_init , dirichlet_group_clear , dirichlet_group_size , dirichlet_group_num_primitive , dirichlet_group_dlog_precompute , dirichlet_group_dlog_clear -- * Character type , DirichletChar (..) , CDirichletChar (..) , newDirichletChar , withDirichletChar , withNewDirichletChar , dirichlet_char_init , dirichlet_char_clear , dirichlet_char_print , dirichlet_char_log , dirichlet_char_exp , _dirichlet_char_exp , dirichlet_char_one , dirichlet_char_first_primitive , dirichlet_char_set , dirichlet_char_next , dirichlet_char_next_primitive , dirichlet_index_char , dirichlet_char_index , dirichlet_char_eq , dirichlet_char_eq_deep -- * Character properties , dirichlet_char_is_principal , dirichlet_conductor_ui , dirichlet_conductor_char , dirichlet_parity_ui , dirichlet_parity_char , dirichlet_order_ui , dirichlet_order_char , dirichlet_char_is_real , dirichlet_char_is_primitive -- * Character evaluation , dirichlet_pairing , dirichlet_pairing_char , dirichlet_chi , dirichlet_chi_vec , dirichlet_chi_vec_order -- * Character operations , dirichlet_char_mul , dirichlet_char_pow , dirichlet_char_lift , dirichlet_char_lower ) where -- Dirichlet characters -------------------------------------------------------- import Foreign.C.Types import Foreign.C.String import Foreign.Ptr import Foreign.ForeignPtr import Foreign.Storable import Data.Number.Flint.Flint #include -- dirichlet_group_t ----------------------------------------------------------- data DirichletGroup = DirichletGroup {-# UNPACK #-} !(ForeignPtr CDirichletGroup) data CDirichletGroup = CFlint DirichletGroup newDirichletGroup n = do x <- mallocForeignPtr withForeignPtr x $ \x -> do dirichlet_group_init x (fromIntegral n) addForeignPtrFinalizer p_dirichlet_group_clear x return $ DirichletGroup x -- | Use DirichletGroup in `f`. {-# INLINE withDirichletGroup #-} withDirichletGroup (DirichletGroup p) f = do withForeignPtr p $ \fp -> (DirichletGroup p,) <$> f fp -- | Apply `f` to new DirichletGroup. {-# INLINE withNewDirichletGroup #-} withNewDirichletGroup n f = do x <- newDirichletGroup n withDirichletGroup x f instance Storable CDirichletGroup where {-# INLINE sizeOf #-} sizeOf _ = #{size dirichlet_group_t} {-# INLINE alignment #-} alignment _ = #{alignment dirichlet_group_t} peek = undefined poke = undefined -- Multiplicative group modulo /q/ --------------------------------------------- -- | /dirichlet_group_init/ /G/ /q/ -- -- Initializes /G/ to the group of Dirichlet characters mod /q/. -- -- This method computes a canonical decomposition of /G/ in terms of cyclic -- groups, which are the mod \(p^e\) subgroups for \(p^e\|q\), plus the -- specific generator described by Conrey for each subgroup. -- -- In particular /G/ contains: -- -- - the number /num/ of components -- - the generators -- - the exponent /expo/ of the group -- -- It does /not/ automatically precompute lookup tables of discrete -- logarithms or numerical roots of unity, and can therefore safely be -- called even with large /q/. -- -- For implementation reasons, the largest prime factor of /q/ must not -- exceed \(10^{16}\). This restriction could be removed in the future. The -- function returns 1 on success and 0 if a factor is too large. foreign import ccall "dirichlet.h dirichlet_group_init" dirichlet_group_init :: Ptr CDirichletGroup -> CULong -> IO CInt -- | /dirichlet_subgroup_init/ /H/ /G/ /h/ -- -- Given an already computed group /G/ mod \(q\), initialize its subgroup -- /H/ defined mod \(h\mid q\). Precomputed discrete log tables are -- inherited. foreign import ccall "dirichlet.h dirichlet_subgroup_init" dirichlet_subgroup_init :: Ptr CDirichletGroup -> Ptr CDirichletGroup -> CULong -> IO () -- | /dirichlet_group_clear/ /G/ -- -- Clears /G/. Remark this function does /not/ clear the discrete logarithm -- tables stored in /G/ (which may be shared with another group). foreign import ccall "dirichlet.h dirichlet_group_clear" dirichlet_group_clear :: Ptr CDirichletGroup -> IO () foreign import ccall "dirichlet.h &dirichlet_group_clear" p_dirichlet_group_clear :: FunPtr (Ptr CDirichletGroup -> IO ()) -- | /dirichlet_group_size/ /G/ -- -- Returns the number of elements in /G/, i.e. \(\varphi(q)\). foreign import ccall "dirichlet.h dirichlet_group_size" dirichlet_group_size :: Ptr CDirichletGroup -> IO CULong -- | /dirichlet_group_num_primitive/ /G/ -- -- Returns the number of primitive elements in /G/. foreign import ccall "dirichlet.h dirichlet_group_num_primitive" dirichlet_group_num_primitive :: Ptr CDirichletGroup -> IO CULong -- | /dirichlet_group_dlog_precompute/ /G/ /num/ -- -- Precompute decomposition and tables for discrete log computations in -- /G/, so as to minimize the complexity of /num/ calls to discrete -- logarithms. -- -- If /num/ gets very large, the entire group may be indexed. foreign import ccall "dirichlet.h dirichlet_group_dlog_precompute" dirichlet_group_dlog_precompute :: Ptr CDirichletGroup -> CULong -> IO () -- | /dirichlet_group_dlog_clear/ /G/ /num/ -- -- Clear discrete logarithm tables in /G/. When discrete logarithm tables -- are shared with subgroups, those subgroups must be cleared before -- clearing the tables. foreign import ccall "dirichlet.h dirichlet_group_dlog_clear" dirichlet_group_dlog_clear :: Ptr CDirichletGroup -> CULong -> IO () -- Character type -------------------------------------------------------------- data DirichletChar = DirichletChar {-# UNPACK #-} !(ForeignPtr CDirichletChar) data CDirichletChar = CDirichletChar CULong (Ptr CULong) newDirichletChar group = do x <- mallocForeignPtr withForeignPtr x $ \x -> do withDirichletGroup group $ \group -> do dirichlet_char_init x group addForeignPtrFinalizer p_dirichlet_char_clear x return $ DirichletChar x -- | Use DirichletChar in `f`. {-# INLINE withDirichletChar #-} withDirichletChar (DirichletChar p) f = do withForeignPtr p $ \fp -> (DirichletChar p,) <$> f fp -- | Apply `f` to new DirichletChar. {-# INLINE withNewDirichletChar #-} withNewDirichletChar group f = do x <- newDirichletChar group withDirichletChar x f instance Storable CDirichletChar where {-# INLINE sizeOf #-} sizeOf _ = #{size dirichlet_char_t} {-# INLINE alignment #-} alignment _ = #{alignment dirichlet_char_t} peek ptr = CDirichletChar <$> #{peek dirichlet_char_struct, n } ptr <*> #{peek dirichlet_char_struct, log} ptr poke ptr (CDirichletChar n log) = do #{poke dirichlet_char_struct, n } ptr n #{poke dirichlet_char_struct, log } ptr log -------------------------------------------------------------------------------- -- | /dirichlet_char_init/ /chi/ /G/ -- -- Initializes /chi/ to an element of the group /G/ and sets its value to -- the principal character. foreign import ccall "dirichlet.h dirichlet_char_init" dirichlet_char_init :: Ptr CDirichletChar -> Ptr CDirichletGroup -> IO () -- | /dirichlet_char_clear/ /chi/ -- -- Clears /chi/. foreign import ccall "dirichlet.h dirichlet_char_clear" dirichlet_char_clear :: Ptr CDirichletChar -> IO () foreign import ccall "dirichlet.h &dirichlet_char_clear" p_dirichlet_char_clear :: FunPtr (Ptr CDirichletChar -> IO ()) -- | /dirichlet_char_print/ /G/ /chi/ -- -- Prints the array of exponents representing this character. dirichlet_char_print :: Ptr CDirichletGroup -> Ptr CDirichletChar -> IO () dirichlet_char_print g c = do printCStr (dirichlet_char_get_str g) c return () foreign import ccall "dirichlet.h dirichlet_char_get_str" dirichlet_char_get_str :: Ptr CDirichletGroup -> Ptr CDirichletChar -> IO CString -- | /dirichlet_char_log/ /x/ /G/ /m/ -- -- Sets /x/ to the character of number /m/, computing its log using -- discrete logarithm in /G/. foreign import ccall "dirichlet.h dirichlet_char_log" dirichlet_char_log :: Ptr CDirichletChar -> Ptr CDirichletGroup -> CULong -> IO () -- | /dirichlet_char_exp/ /G/ /x/ -- -- Returns the number /m/ corresponding to exponents in /x/. foreign import ccall "dirichlet.h dirichlet_char_exp" dirichlet_char_exp :: Ptr CDirichletGroup -> Ptr CDirichletChar -> IO CULong -- | /_dirichlet_char_exp/ /x/ /G/ -- -- Computes and returns the number /m/ corresponding to exponents in /x/. -- This function is for internal use. foreign import ccall "dirichlet.h _dirichlet_char_exp" _dirichlet_char_exp :: Ptr CDirichletChar -> Ptr CDirichletGroup -> IO CULong -- | /dirichlet_char_one/ /x/ /G/ -- -- Sets /x/ to the principal character in /G/, having /log/ -- \([0,\dots 0]\). foreign import ccall "dirichlet.h dirichlet_char_one" dirichlet_char_one :: Ptr CDirichletChar -> Ptr CDirichletGroup -> IO () -- | /dirichlet_char_first_primitive/ /x/ /G/ -- -- Sets /x/ to the first primitive character of /G/, having /log/ -- \([1,\dots 1]\), or \([0, 1, \dots 1]\) if \(8\mid q\). foreign import ccall "dirichlet.h dirichlet_char_first_primitive" dirichlet_char_first_primitive :: Ptr CDirichletChar -> Ptr CDirichletGroup -> IO () -- | /dirichlet_char_set/ /x/ /G/ /y/ -- -- Sets /x/ to the element /y/. foreign import ccall "dirichlet.h dirichlet_char_set" dirichlet_char_set :: Ptr CDirichletChar -> Ptr CDirichletGroup -> Ptr CDirichletChar -> IO () -- | /dirichlet_char_next/ /x/ /G/ -- -- Sets /x/ to the next character in /G/ according to lexicographic -- ordering of /log/. -- -- The return value is the index of the last updated exponent of /x/, or -- /-1/ if the last element has been reached. -- -- This function allows to iterate on all elements of /G/ looping on their -- /log/. Note that it produces elements in seemingly random /number/ -- order. -- -- The following template can be used for such a loop: -- -- > dirichlet_char_one(chi, G); -- > do { -- > /* use character chi */ -- > } while (dirichlet_char_next(chi, G) >= 0); foreign import ccall "dirichlet.h dirichlet_char_next" dirichlet_char_next :: Ptr CDirichletChar -> Ptr CDirichletGroup -> IO CInt -- | /dirichlet_char_next_primitive/ /x/ /G/ -- -- Same as @dirichlet_char_next@, but jumps to the next primitive character -- of /G/. foreign import ccall "dirichlet.h dirichlet_char_next_primitive" dirichlet_char_next_primitive :: Ptr CDirichletChar -> Ptr CDirichletGroup -> IO CInt -- | /dirichlet_index_char/ /G/ /x/ -- -- Returns the lexicographic index of the /log/ of /x/ as an integer in -- \(0\dots \varphi(q)\). foreign import ccall "dirichlet.h dirichlet_index_char" dirichlet_index_char :: Ptr CDirichletGroup -> Ptr CDirichletChar -> IO CULong -- | /dirichlet_char_index/ /x/ /G/ /j/ -- -- Sets /x/ to the character whose /log/ has lexicographic index /j/. foreign import ccall "dirichlet.h dirichlet_char_index" dirichlet_char_index :: Ptr CDirichletChar -> Ptr CDirichletGroup -> CULong -> IO () foreign import ccall "dirichlet.h dirichlet_char_eq" dirichlet_char_eq :: Ptr CDirichletChar -> Ptr CDirichletChar -> IO CInt -- | /dirichlet_char_eq_deep/ /G/ /x/ /y/ -- -- Return 1 if /x/ equals /y/. -- -- The second version checks every byte of the representation and is -- intended for testing only. foreign import ccall "dirichlet.h dirichlet_char_eq_deep" dirichlet_char_eq_deep :: Ptr CDirichletGroup -> Ptr CDirichletChar -> Ptr CDirichletChar -> IO CInt -- Character properties -------------------------------------------------------- -- As a consequence of the Conrey numbering, all these numbers are -- available at the level of /number/ and /char/ object. Both case require -- no discrete log computation. -- -- | /dirichlet_char_is_principal/ /G/ /chi/ -- -- Returns 1 if /chi/ is the principal character mod /q/. foreign import ccall "dirichlet.h dirichlet_char_is_principal" dirichlet_char_is_principal :: Ptr CDirichletGroup -> Ptr CDirichletChar -> IO CInt foreign import ccall "dirichlet.h dirichlet_conductor_ui" dirichlet_conductor_ui :: Ptr CDirichletGroup -> CULong -> IO CULong -- | /dirichlet_conductor_char/ /G/ /x/ -- -- Returns the /conductor/ of \(\chi_q(a,\cdot)\), that is the smallest -- \(r\) dividing \(q\) such \(\chi_q(a,\cdot)\) can be obtained as a -- character mod \(r\). foreign import ccall "dirichlet.h dirichlet_conductor_char" dirichlet_conductor_char :: Ptr CDirichletGroup -> Ptr CDirichletChar -> IO CULong foreign import ccall "dirichlet.h dirichlet_parity_ui" dirichlet_parity_ui :: Ptr CDirichletGroup -> CULong -> IO CInt -- | /dirichlet_parity_char/ /G/ /x/ -- -- Returns the /parity/ \(\lambda\) in \(\{0,1\}\) of \(\chi_q(a,\cdot)\), -- such that \(\chi_q(a,-1)=(-1)^\lambda\). foreign import ccall "dirichlet.h dirichlet_parity_char" dirichlet_parity_char :: Ptr CDirichletGroup -> Ptr CDirichletChar -> IO CInt foreign import ccall "dirichlet.h dirichlet_order_ui" dirichlet_order_ui :: Ptr CDirichletGroup -> CULong -> IO CULong -- | /dirichlet_order_char/ /G/ /x/ -- -- Returns the order of \(\chi_q(a,\cdot)\) which is the order of -- \(a\bmod q\). foreign import ccall "dirichlet.h dirichlet_order_char" dirichlet_order_char :: Ptr CDirichletGroup -> Ptr CDirichletChar -> IO CULong -- | /dirichlet_char_is_real/ /G/ /chi/ -- -- Returns 1 if /chi/ is a real character (iff it has order \(\leq 2\)). foreign import ccall "dirichlet.h dirichlet_char_is_real" dirichlet_char_is_real :: Ptr CDirichletGroup -> Ptr CDirichletChar -> IO CInt -- | /dirichlet_char_is_primitive/ /G/ /chi/ -- -- Returns 1 if /chi/ is primitive (iff its conductor is exactly /q/). foreign import ccall "dirichlet.h dirichlet_char_is_primitive" dirichlet_char_is_primitive :: Ptr CDirichletGroup -> Ptr CDirichletChar -> IO CInt -- Character evaluation -------------------------------------------------------- -- Dirichlet characters take value in a finite cyclic group of roots of -- unity plus zero. -- -- Evaluation functions return a /ulong/, this number corresponds to the -- power of a primitive root of unity, the special value -- /DIRICHLET_CHI_NULL/ encoding the zero value. -- foreign import ccall "dirichlet.h dirichlet_pairing" dirichlet_pairing :: Ptr CDirichletGroup -> CULong -> CULong -> IO CULong -- | /dirichlet_pairing_char/ /G/ /chi/ /psi/ -- -- Compute the value of the Dirichlet pairing on numbers /m/ and /n/, as -- exponent modulo /G->expo/. -- -- The /char/ variant takes as input two characters, so that no discrete -- logarithm is computed. -- -- The returned value is the numerator of the actual value exponent mod the -- group exponent /G->expo/. foreign import ccall "dirichlet.h dirichlet_pairing_char" dirichlet_pairing_char :: Ptr CDirichletGroup -> Ptr CDirichletChar -> Ptr CDirichletChar -> IO CULong -- | /dirichlet_chi/ /G/ /chi/ /n/ -- -- Compute the value \(\chi(n)\) as the exponent modulo /G->expo/. foreign import ccall "dirichlet.h dirichlet_chi" dirichlet_chi :: Ptr CDirichletGroup -> Ptr CDirichletChar -> CULong -> IO CULong -- | /dirichlet_chi_vec/ /v/ /G/ /chi/ /nv/ -- -- Compute the list of exponent values /v[k]/ for \(0\leq k < nv\), as -- exponents modulo /G->expo/. foreign import ccall "dirichlet.h dirichlet_chi_vec" dirichlet_chi_vec :: Ptr CULong -> Ptr CDirichletGroup -> Ptr CDirichletChar -> CLong -> IO () -- | /dirichlet_chi_vec_order/ /v/ /G/ /chi/ /order/ /nv/ -- -- Compute the list of exponent values /v[k]/ for \(0\leq k < nv\), as -- exponents modulo /order/, which is assumed to be a multiple of the order -- of /chi/. foreign import ccall "dirichlet.h dirichlet_chi_vec_order" dirichlet_chi_vec_order :: Ptr CULong -> Ptr CDirichletGroup -> Ptr CDirichletChar -> CULong -> CLong -> IO () -- Character operations -------------------------------------------------------- -- | /dirichlet_char_mul/ /chi12/ /G/ /chi1/ /chi2/ -- -- Multiply two characters of the same group /G/. foreign import ccall "dirichlet.h dirichlet_char_mul" dirichlet_char_mul :: Ptr CDirichletChar -> Ptr CDirichletGroup -> Ptr CDirichletChar -> Ptr CDirichletChar -> IO () -- | /dirichlet_char_pow/ /c/ /G/ /a/ /n/ -- -- Take the power of a character. foreign import ccall "dirichlet.h dirichlet_char_pow" dirichlet_char_pow :: Ptr CDirichletChar -> Ptr CDirichletGroup -> Ptr CDirichletChar -> CULong -> IO () -- | /dirichlet_char_lift/ /chi_G/ /G/ /chi_H/ /H/ -- -- If /H/ is a subgroup of /G/, computes the character in /G/ corresponding -- to /chi_H/ in /H/. foreign import ccall "dirichlet.h dirichlet_char_lift" dirichlet_char_lift :: Ptr CDirichletChar -> Ptr CDirichletGroup -> Ptr CDirichletChar -> Ptr CDirichletGroup -> IO () -- | /dirichlet_char_lower/ /chi_H/ /H/ /chi_G/ /G/ -- -- If /chi_G/ is a character of /G/ which factors through /H/, sets /chi_H/ -- to the corresponding restriction in /H/. -- -- This requires \(c(\chi_G)\mid q_H\mid q_G\), where \(c(\chi_G)\) is the -- conductor of \(\chi_G\) and \(q_G, q_H\) are the moduli of G and H. foreign import ccall "dirichlet.h dirichlet_char_lower" dirichlet_char_lower :: Ptr CDirichletChar -> Ptr CDirichletGroup -> Ptr CDirichletChar -> Ptr CDirichletGroup -> IO ()