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