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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
|
.. _nmod:
**nmod.h** -- integers mod n (word-size n)
===============================================================================
Modular reduction and arithmetic
--------------------------------------------------------------------------------
.. function:: void nmod_init(nmod_t * mod, ulong n)
Initialises the given ``nmod_t`` structure for reduction modulo `n`
with a precomputed inverse.
.. macro:: NMOD_BITS(mod)
Macro giving the number of bits in ``mod.n``.
.. macro:: NMOD_CAN_USE_SHOUP(mod)
Macro returning whether Shoup's algorithm can be used for
preconditioned multiplication mod ``mod.n``.
.. macro:: NMOD_RED2(r, a_hi, a_lo, mod)
Macro to set `r` to `a` reduced modulo ``mod.n``, where `a`
consists of two limbs ``(a_hi, a_lo)``. The ``mod`` parameter
must be a valid ``nmod_t`` structure. It is assumed that ``a_hi``
is already reduced modulo ``mod.n``.
.. macro:: NMOD_RED(r, a, mod)
Macro to set `r` to `a` reduced modulo ``mod.n``. The ``mod``
parameter must be a valid ``nmod_t`` structure.
.. macro:: NMOD2_RED2(r, a_hi, a_lo, mod)
Macro to set `r` to `a` reduced modulo ``mod.n``, where `a`
consists of two limbs ``(a_hi, a_lo)``. The ``mod`` parameter
must be a valid ``nmod_t`` structure. No assumptions are made
about ``a_hi``.
.. macro:: NMOD_RED3(r, a_hi, a_me, a_lo, mod)
Macro to set `r` to `a` reduced modulo ``mod.n``, where `a`
consists of three limbs ``(a_hi, a_me, a_lo)``. The ``mod``
parameter must be a valid ``nmod_t`` structure. It is assumed
that ``a_hi`` is already reduced modulo ``mod.n``.
.. macro:: NMOD_MUL_PRENORM(res, a, b, mod)
Macro to set `r` to `ab` modulo ``mod.n``. The
``mod`` parameter must be a valid ``nmod_t`` structure. It is
assumed that `a`, `b` are already reduced modulo ``mod.n``
and that either `a` or `b` is prenormalised by left-shifting
by ``mod.norm``.
.. macro:: NMOD_MUL_FULLWORD(res, a, b, mod)
Macro to set `r` to `ab` modulo ``mod.n``. The
``mod`` parameter must be a valid ``nmod_t`` structure. It is
assumed that `a`, `b` are already reduced modulo ``mod.n``
and that ``mod.n`` is exactly ``FLINT_BITS`` bits large.
.. macro:: NMOD_ADDMUL(r, a, b, mod)
Macro to set `r` to `r + ab` reduced modulo ``mod.n``. The
``mod`` parameter must be a valid ``nmod_t`` structure. It is
assumed that `r`, `a`, `b` are already reduced modulo ``mod.n``.
.. function:: ulong _nmod_add(ulong a, ulong b, nmod_t mod)
Returns `a + b` modulo ``mod.n``. It is assumed that ``mod`` is
no more than ``FLINT_BITS - 1`` bits. It is assumed that `a` and `b`
are already reduced modulo ``mod.n``.
.. function:: ulong nmod_add(ulong a, ulong b, nmod_t mod)
Returns `a + b` modulo ``mod.n``. No assumptions are made about
``mod.n``. It is assumed that `a` and `b` are already reduced
modulo ``mod.n``.
.. function:: ulong _nmod_sub(ulong a, ulong b, nmod_t mod)
Returns `a - b` modulo ``mod.n``. It is assumed that ``mod``
is no more than ``FLINT_BITS - 1`` bits. It is assumed that
`a` and `b` are already reduced modulo ``mod.n``.
.. function:: ulong nmod_sub(ulong a, ulong b, nmod_t mod)
Returns `a - b` modulo ``mod.n``. No assumptions are made about
``mod.n``. It is assumed that `a` and `b` are already reduced
modulo ``mod.n``.
.. function:: ulong nmod_neg(ulong a, nmod_t mod)
Returns `-a` modulo ``mod.n``. It is assumed that `a` is already
reduced modulo ``mod.n``, but no assumptions are made about the
latter.
.. function:: ulong nmod_mul(ulong a, ulong b, nmod_t mod)
Returns `ab` modulo ``mod.n``. No assumptions are made about
``mod.n``. It is assumed that `a` and `b` are already reduced
modulo ``mod.n``.
.. function:: ulong _nmod_mul_fullword(ulong a, ulong b, nmod_t mod)
Returns `ab` modulo ``mod.n``. Requires that ``mod.n`` is exactly
``FLINT_BITS`` large. It is assumed that `a` and `b` are already
reduced modulo ``mod.n``.
.. function:: ulong nmod_inv(ulong a, nmod_t mod)
Returns `a^{-1}` modulo ``mod.n``. The inverse is assumed to exist.
.. function:: ulong nmod_div(ulong a, ulong b, nmod_t mod)
Returns `ab^{-1}` modulo ``mod.n``. The inverse of `b` is assumed to
exist. It is assumed that `a` is already reduced modulo ``mod.n``.
.. function:: int nmod_divides(ulong * a, ulong b, ulong c, nmod_t mod)
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:: ulong nmod_pow_ui(ulong a, ulong e, nmod_t mod)
Returns `a^e` modulo ``mod.n``. No assumptions are made about
``mod.n``. It is assumed that `a` is already reduced
modulo ``mod.n``.
.. function:: ulong nmod_pow_fmpz(ulong a, const fmpz_t e, nmod_t mod)
Returns `a^e` modulo ``mod.n``. No assumptions are made about
``mod.n``. It is assumed that `a` is already reduced
modulo ``mod.n`` and that `e` is not negative.
Discrete Logarithms via Pohlig-Hellman
--------------------------------------------------------------------------------
.. function:: void nmod_discrete_log_pohlig_hellman_init(nmod_discrete_log_pohlig_hellman_t L)
Initialize ``L``. Upon initialization ``L`` is not ready for computation.
.. function:: void nmod_discrete_log_pohlig_hellman_clear(nmod_discrete_log_pohlig_hellman_t L)
Free any space used by ``L``.
.. function:: double nmod_discrete_log_pohlig_hellman_precompute_prime(nmod_discrete_log_pohlig_hellman_t L, ulong 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:: ulong nmod_discrete_log_pohlig_hellman_primitive_root(const nmod_discrete_log_pohlig_hellman_t L)
Return the internally stored base.
.. function:: ulong nmod_discrete_log_pohlig_hellman_run(const nmod_discrete_log_pohlig_hellman_t L, ulong y)
Return 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.
|
