1.. _fmpz-mod:
2
3**fmpz_mod.h** -- arithmetic modulo integers
4===============================================================================
5
6Description.
7
8Types, macros and constants
9-------------------------------------------------------------------------------
10
11.. type:: fmpz_mod_ctx_struct
12
13.. type:: fmpz_mod_ctx_t
14
15    The context object for arithmetic modulo integers.
16
17
18Context object
19--------------------------------------------------------------------------------
20
21
22.. function:: void fmpz_mod_ctx_init(fmpz_mod_ctx_t ctx, const fmpz_t n)
23
24    Initialise ``ctx`` for arithmetic modulo ``n``, which is expected to be positive.
25
26.. function:: void fmpz_mod_ctx_clear(fmpz_mod_ctx_t ctx)
27
28    Free any memory used by ``ctx``.
29
30.. function:: void fmpz_mod_ctx_set_modulus(fmpz_mod_ctx_t ctx, const fmpz_t n)
31
32    Reconfigure ``ctx`` for arithmetic modulo ``n``.
33
34Arithmetic
35--------------------------------------------------------------------------------
36
37Unless specified otherwise all functions here expect their relevant arguments to be in the canonical range `[0,n)`.
38Comparison of elements against each other or against zero can be accomplished with func::fmpz_equal or func::fmpz_is_zero without a context.
39
40.. function:: int fmpz_mod_is_canonical(const fmpz_t a, const fmpz_mod_ctx_t ctx)
41
42    Return ``1`` if `a` is in the canonical range `[0,n)` and ``0`` otherwise.
43
44.. function:: int fmpz_mod_is_one(const fmpz_t a, const fmpz_mod_ctx_t ctx)
45
46    Return ``1`` if `a` is `1` modulo `n` and return ``0`` otherwise.
47
48.. function:: void fmpz_mod_add(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx)
49
50    Set `a` to `b+c` modulo `n`.
51
52.. function:: void fmpz_mod_add_fmpz(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx);
53              void fmpz_mod_add_ui(fmpz_t a, const fmpz_t b, ulong c, const fmpz_mod_ctx_t ctx);
54              void fmpz_mod_add_si(fmpz_t a, const fmpz_t b, slong c, const fmpz_mod_ctx_t ctx);
55
56    Set `a` to `b+c` modulo `n` where only `b` is assumed to be canonical.
57
58.. function:: void fmpz_mod_sub(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx)
59
60    Set `a` to `b-c` modulo `n`.
61
62.. function:: void fmpz_mod_sub_fmpz(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx);
63              void fmpz_mod_sub_ui(fmpz_t a, const fmpz_t b, ulong c, const fmpz_mod_ctx_t ctx);
64              void fmpz_mod_sub_si(fmpz_t a, const fmpz_t b, slong c, const fmpz_mod_ctx_t ctx);
65
66    Set `a` to `b-c` modulo `n` where only `b` is assumed to be canonical.
67
68.. function:: void fmpz_mod_fmpz_sub(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx);
69              void fmpz_mod_ui_sub(fmpz_t a, ulong b, const fmpz_t c, const fmpz_mod_ctx_t ctx);
70              void fmpz_mod_si_sub(fmpz_t a, slong b, const fmpz_t c, const fmpz_mod_ctx_t ctx);
71
72    Set `a` to `b-c` modulo `n` where only `c` is assumed to be canonical.
73
74.. function:: void fmpz_mod_neg(fmpz_t a, const fmpz_t b, const fmpz_mod_ctx_t ctx)
75
76    Set `a` to `-b` modulo `n`.
77
78.. function:: void fmpz_mod_mul(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx)
79
80    Set `a` to `b*c` modulo `n`.
81
82.. function:: void fmpz_mod_inv(fmpz_t a, const fmpz_t b, const fmpz_mod_ctx_t ctx)
83
84    Set `a` to `b^{-1}` modulo `n`.
85    This function expects that `b` is invertible modulo `n` and throws if this not the case.
86    Invertibility maybe tested with func:`fmpz_mod_pow_fmpz` or func:`fmpz_mod_divides`.
87
88.. function:: int fmpz_mod_divides(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx)
89
90    If `a*c = b \mod n` has a solution for `a` return `1` and set `a` to such a solution. Otherwise return `0` and leave `a` undefined.
91
92.. function:: void fmpz_mod_pow_ui(fmpz_t a, const fmpz_t b, ulong e, const fmpz_mod_ctx_t ctx)
93
94    Set `a` to `b^e` modulo `n`.
95
96.. function:: int fmpz_mod_pow_fmpz(fmpz_t a, const fmpz_t b, const fmpz_t e, const fmpz_mod_ctx_t ctx)
97
98    Try to set `a` to `b^e` modulo `n`.
99    If `e < 0` and `b` is not invertible modulo `n`, the return is `0`. Otherwise, the return is `1`.
100
101
102Discrete Logarithms via Pohlig-Hellman
103--------------------------------------------------------------------------------
104
105.. function:: void fmpz_mod_discrete_log_pohlig_hellman_init(fmpz_mod_discrete_log_pohlig_hellman_t L)
106
107    Initialize ``L``. Upon initialization ``L`` is not ready for computation.
108
109.. function:: void fmpz_mod_discrete_log_pohlig_hellman_clear(fmpz_mod_discrete_log_pohlig_hellman_t L)
110
111    Free any space used by ``L``.
112
113.. function:: double fmpz_mod_discrete_log_pohlig_hellman_precompute_prime(fmpz_mod_discrete_log_pohlig_hellman_t L, const fmpz_t p)
114
115    Configure ``L`` for discrete logarithms modulo ``p`` to an internally chosen base. It is assumed that ``p`` is prime.
116    The return is an estimate on the number of multiplications needed for one run.
117
118.. function:: const fmpz * fmpz_mod_discrete_log_pohlig_hellman_primitive_root(const fmpz_mod_discrete_log_pohlig_hellman_t L)
119
120    Return the internally stored base.
121
122.. function:: void fmpz_mod_discrete_log_pohlig_hellman_run(fmpz_t x, const fmpz_mod_discrete_log_pohlig_hellman_t L, const fmpz_t y)
123
124    Set ``x`` to the logarithm of ``y`` with respect to the internally stored base. ``y`` is expected to be reduced modulo the ``p``.
125    The function is undefined if the logarithm does not exist.
126
127
128.. function:: int fmpz_next_smooth_prime(fmpz_t a, const fmpz_t b)
129
130    Either return `1` and set `a` to a smooth prime strictly greater than `b`, or return `0` and set `a` to `0`.
131    The smooth primes returned by this function currently have no prime factor of `a-1` greater than `23`, but this should not be relied upon.
132
133