3471ebd1 |
1 | %%% -*-latex-*- |
2 | |
3 | \section{High-level multiprecision integer represention} |
4 | \label{sec:mp} |
5 | |
6 | The high-level interface to multiprecision integers is exported by the header |
7 | file \hdr{<catacomb/mp.h>}. |
8 | |
9 | |
10 | \subsection{The \code{mp} structure} |
11 | \label{sec:mp-struct} |
12 | |
13 | At the high level, a multiprecision integer is represented as an object of |
14 | type \code{mp}. Most of the time, programs use pointers to \code{mp} objects |
15 | which have been dynamically allocated. (See \code{mp_build}, |
16 | page~\pageref{fn:mp-build}, for the exception to this rule.) |
17 | |
18 | The \code{mp} type is a structure. Some of the members are considered |
19 | internal to the implementation. However, the following may be used by client |
20 | programs: |
21 | \begin{description} |
22 | \def\makelabel#1{\code{#1}\hfil} |
23 | \item[mpw *v, *vl] The base and limit of the multiprecision |
24 | integer array. |
25 | \item[unsigned f] Various flags describing the current state of the integer. |
26 | \end{description} |
27 | Other members are used for keeping track of how much memory has been |
28 | allocated to the number and for managing the reference counting system. |
29 | These members should not be accessed directly by application code. None of |
30 | the structure members should be modified directly. |
31 | |
32 | The following flags are defined: |
33 | \begin{description*} |
34 | \let\makelabel\code |
35 | \item[MP_NEG] The integer is negative. |
36 | \item[MP_BURN] Clear the integer's storage after use. |
37 | \item[MP_CONST] The integer may not be altered or freed. |
38 | \item[MP_UNDEF] The integer currently has no interesting value. |
39 | \item[MP_DESTROYED] The integer has been destroyed. |
40 | \end{description*} |
41 | |
42 | The \code{MP_BURN} flag is inherited by the results of calculations. Thus, |
43 | setting the flag on a value causes it and all other values calculated from it |
44 | to be destroyed after use.\footnote{% |
45 | There are currently a small number of places where the \code{MP_BURN} flag |
46 | may be lost from a result. These usually result from performing complex |
47 | calculations with degenerate arguments (e.g., computing a GCD with zero). |
48 | Fixing this is not a high priority.} % |
49 | |
50 | The \code{MP_DESTROYED} flag is used by \code{mp_destroy} |
51 | (page~\pageref{fn:mp-destroy}) to trap attempts to destroy the same integer |
52 | more than once, which can otherwise lead to confusing bugs. |
53 | |
54 | |
55 | \subsubsection{The \code{MP_LEN} macro} |
56 | \label{fn:MP-LEN} |
57 | |
58 | \fsec{Synopsis} |
59 | |
60 | \begin{listinglist} |
61 | |#include <catacomb/mp.h>| \\ |
62 | |ptrdiff_t MP_LEN(const mp *|$m$|);| |
63 | \end{listinglist} |
64 | |
65 | \fsec{Returns} |
66 | |
674cd11e |
67 | The number of words used in the representation of the integer~$m$. Note that |
68 | the argument~$m$ may be evaluated multiple times by this macro. |
3471ebd1 |
69 | |
70 | |
71 | \subsubsection{The \code{mp_burn} function} |
72 | \label{fn:mp-burn} |
73 | |
74 | \fsec{Synopsis} |
75 | |
76 | \begin{listinglist} |
77 | |#include <catacomb/mp.h>| \\ |
78 | |void mp_burn(mp *|$m$|);| |
79 | \end{listinglist} |
80 | |
81 | \fsec{Description} |
82 | |
674cd11e |
83 | Sets the \code{MP_BURN} flag on the integer~$m$. Whenever memory associated |
84 | with~$m$, or results derived from it, is deallocated, it is overwritten with |
3471ebd1 |
85 | zeros to prevent traces being found in swap files or core dumps. |
86 | |
87 | |
88 | \subsection{Multiprecision integer constants} |
89 | \label{sec:mp-const} |
90 | |
91 | There are a few commonly-used multiprecision integer constants provided. All |
92 | are declared in \hdr{<catacomb/mp.h>}: |
93 | |
94 | \begin{tabular}[C] |
95 | {| >{\ttfamily}l | Mr @{\extracolsep{0pt plus 10000fill}\hskip\tabcolsep} |
96 | | c @{\extracolsep{0pt}} | >{\ttfamily}l | Mr |} \hlx{c{1,2,4,5}v} |
97 | \multicolumn{1}{|c|}{\textbf{Constant}} & |
98 | \multicolumn{1}{c|}{\textbf{Value}} & \qquad & |
99 | \multicolumn{1}{c|}{\textbf{Constant}} & |
100 | \multicolumn{1}{c|}{\textbf{Value}} \\ \hlx{vc{1,2,4,5}v} |
101 | MP_ZERO & 0 && MP_FOUR & 4 \\ |
102 | MP_ONE & 1 && MP_FIVE & 5 \\ |
103 | MP_TWO & 2 && MP_TEN & 10 \\ |
104 | MP_THREE & 3 && MP_MONE & -1 \\ \hlx{vc{1,2,4,5}} |
105 | \end{tabular} |
106 | \goodbreak |
107 | |
108 | All of the multiprecision constants are actually pointers to the real |
109 | values. All have the \code{MP_CONST} flag set, so they cannot be modified or |
110 | destroyed. |
111 | |
112 | |
113 | \subsection{Creation and destruction} |
114 | \label{sec:mp-create} |
115 | |
116 | Multiprecision integers are reference counted; i.e., each \code{mp} remembers |
117 | how many references there are to it, and is destroyed only when the last |
118 | reference disappears. |
119 | |
120 | New multiprecision integers are created using the functions \code{mp_create} |
121 | (page~\pageref{fn:mp-create}) or \code{mp_build} |
122 | (page~\pageref{fn:mp-build}). A newly created integer has one reference. |
123 | Additional references are returned by the function \code{mp_copy} |
124 | (page~\pageref{fn:mp-copy}). A reference may be removed from an integer by |
125 | calling \code{mp_drop} (page~\pageref{fn:mp-drop}). |
126 | |
127 | It isn't usually a good idea to modify an integer to which there are multiple |
128 | references: the owners of the other references will usually react badly if |
129 | their number has changed. A modifiable copy may be made of an integer using |
130 | the \code{mp_split} function (page~\pageref{fn:mp-split}). If there are no |
131 | other references, the integer is returned unchanged; otherwise a real copy is |
132 | made and returned, and the number of references to the original is |
133 | decremented by one. |
134 | |
135 | Most of the arithmetic functions allow the caller to state a preferred |
136 | location for the result. This may either be an existing integer or a |
137 | completely new one, requested by the special value \code{MP_NEW}. This |
138 | behaviour is provided by the \code{mp_modify} function |
139 | (page~\pageref{fn:mp-modify}). |
140 | |
141 | Note that functions may not actually use the location requested, although if |
142 | it decides not to overwrite the requested destination, a reference to it is |
143 | removed. |
144 | |
145 | |
146 | \subsubsection{The \code{mp_create} function} |
147 | \label{fn:mp-create} |
148 | |
149 | \fsec{Synopsis} |
150 | |
151 | \begin{listinglist} |
152 | |#include <catacomb/mp.h>| \\ |
153 | |mp *mp_create(size_t |$\sz$|);| |
154 | \end{listinglist} |
155 | |
156 | \fsec{Description} |
157 | |
158 | Allocates a new multiprecision integer, with at least $\sz$ words of storage |
159 | available for its representation. The flag \code{MP_UNDEF} is set initially; |
160 | the other flags are cleared. The integer's array limit pointer \code{vl} is |
161 | set to be $\sz$ higher than the base pointer \code{v}. |
162 | |
163 | \fsec{Returns} |
164 | |
165 | A pointer to a newly allocated multiprecision integer. |
166 | |
167 | \subsubsection{The \code{mp_destroy} function} |
168 | \label{fn:mp-destroy} |
169 | |
170 | \fsec{Synopsis} |
171 | |
172 | \begin{listinglist} |
173 | |#include <catacomb/mp.h>| \\ |
174 | |void mp_destroy(mp *|$m$|);| |
175 | \end{listinglist} |
176 | |
177 | \fsec{Description} |
178 | |
674cd11e |
179 | Destroys the multiprecision integer~$m$. All resouces allocated to the |
3471ebd1 |
180 | integer are freed. It's most unusual for this to be the function you want: |
181 | most of the time \code{mp_drop} (page~\pageref{fn:mp-drop}) is much more |
182 | useful. |
183 | |
184 | If compiled with debugging support, the \code{mp_destroy} function will abort |
185 | if requested to destroy an integer whose \code{MP_CONST} or |
186 | \code{MP_DESTROYED} flags are set. |
187 | |
188 | \subsubsection{The \code{mp_build} function} |
189 | \label{fn:mp-build} |
190 | |
191 | \fsec{Synopsis} |
192 | |
193 | \begin{listinglist} |
194 | |#include <catacomb/mp.h>| \\ |
195 | |void mp_build(mp *|$m$|, mpw *|$v$|, mpw *|$\vl$|);| |
196 | \end{listinglist} |
197 | |
198 | \fsec{Description} |
199 | |
200 | Creates a constant multiprecision integer from an array of \code{mpw} words. |
201 | Storage for the \code{mp} object and the array is provided by the user -- |
202 | \code{mp_build} allocates no memory. Conversely, it's safe to dispose of the |
203 | \code{mp} block and \code{mpw} array at any time, as long as there are no |
204 | live references to them. |
205 | |
206 | The \code{mp_build} function is particularly useful for constructing small |
207 | multiprecision integers, and for addressing parts of other integers. For |
208 | example, if $x$ is a multiprecision integer, then |
209 | \begin{listing} |
210 | mp_build(&m, x->v + 5, x->vl); |
211 | \end{listing} |
212 | sets $m$ equal to $\lfloor x / 2^{5 \cdot \code{MPW_BITS}} \rfloor$ without |
213 | copying any data.\footnote{% |
214 | This technique is used in the implementation of Barrett reduction |
215 | (page~\pageref{sec:mp-barrett}), for example. See the source file |
216 | \code{mpbarrett.c} for details.} % |
217 | |
218 | \subsubsection{The \code{mp_copy} function and \code{MP_COPY} macro} |
219 | \label{fn:mp-copy} |
220 | |
221 | \fsec{Synopsis} |
222 | |
223 | \begin{listinglist} |
224 | |#include <catacomb/mp.h>| \\ |
225 | |mp *mp_copy(mp *|$m$|);| \\ |
226 | |mp *MP_COPY(mp *|$m$|);| |
227 | \end{listinglist} |
228 | |
229 | \fsec{Description} |
230 | |
674cd11e |
231 | The function \code{mp_copy} adds a reference to the multiprecision |
232 | integer~$m$. The integer will not be destroyed until all references to it |
233 | have been dropped. |
3471ebd1 |
234 | |
235 | The macro \code{MP_COPY} performs exactly the same action as the |
236 | \code{mp_copy} function, except that it uses inline code rather than a |
237 | function call. It's probably smaller and faster than the function call too. |
238 | |
239 | \fsec{Returns} |
240 | |
241 | The address of the new reference. This will usually be the same as the |
674cd11e |
242 | original argument~$m$. |
3471ebd1 |
243 | |
244 | \subsubsection{The \code{mp_drop} function and \code{MP_DROP} macro} |
245 | \label{fn:mp-drop} |
246 | |
247 | \fsec{Synopsis} |
248 | |
249 | \begin{listinglist} |
250 | |#include <catacomb/mp.h>| \\ |
251 | |void mp_drop(mp *|$m$|);| \\ |
252 | |void MP_DROP(mp *|$m$|);| |
253 | \end{listinglist} |
254 | |
255 | \fsec{Description} |
256 | |
257 | The function \code{mp_drop} removes (`drops') a reference to the |
674cd11e |
258 | multiprecision integer~$m$. If there are no more references to the integer, |
3471ebd1 |
259 | it is destroyed, as if by \code{mp_destroy} (page~\pageref{fn:mp-destroy}). |
260 | |
261 | The macro \code{MP_DROP} performs exactly the same action as the |
262 | \code{mp_drop} function, except that it uses inline code rather than a |
263 | function call, so it's slightly faster but uses a little more code. |
264 | |
265 | \subsubsection{The \code{mp_split} function and \code{MP_SPLIT} macro} |
266 | \label{fn:mp-split} |
267 | |
268 | \fsec{Synopsis} |
269 | |
270 | \begin{listinglist} |
271 | |#include <catacomb/mp.h>| \\ |
272 | |mp *mp_split(mp *|$m$|);| \\ |
273 | |void MP_SPLIT(mp *|$m$|);| |
274 | \end{listinglist} |
275 | |
276 | \fsec{Description} |
277 | |
674cd11e |
278 | If the integer~$m$ has only one reference, the \code{mp_split} function |
3471ebd1 |
279 | returns $m$ unchanged; otherwise, a copy is made and returned, and the |
280 | reference count of $m$ is decremented. Thus, either way, \code{mp_split} |
281 | returns a pointer to an integer with the same value as $m$ and a single |
282 | refernce. Thus, the result of \code{mp_split} is therefore safe to modify. |
283 | |
284 | The macro \code{MP_SPLIT} performs the same action as the \code{mp_split} |
285 | function except that it uses inline code rather than a function call, and it |
286 | modifies its argument in place rather than returning the new reference. The |
674cd11e |
287 | macro \code{MP_SPLIT} may evaluate its argument~$m$ multiple times. |
3471ebd1 |
288 | |
289 | \fsec{Returns} |
290 | |
291 | The function \code{mp_split} returns a pointer to a copy of its argument $m$ |
292 | which is safe to modify. |
293 | |
294 | \subsubsection{The \code{mp_modify} function and \code{MP_MODIFY} macro} |
295 | \label{fn:mp-modify} |
296 | |
297 | \fsec{Synopsis} |
298 | |
299 | \begin{listinglist} |
300 | |#include <catacomb/mp.h>| \\ |
301 | |mp *mp_modify(mp *|$m$|, size_t |$\sz$|);| \\ |
302 | |void MP_MODIFY(mp *|$m$|, size_t |$\sz$|);| |
303 | \end{listinglist} |
304 | |
305 | \fsec{Description} |
306 | |
307 | The function \code{mp_modify} returns a pointer to a suitable destination $d$ |
308 | for a result given a suggested destination $m$ and a required size $\sz$. |
309 | The actual behaviour is complicated: |
310 | |
311 | \begin{itemize} |
312 | \item If $m$ is equal to \code{MP_NEW}, or the \code{MP_CONST} flag is set on |
674cd11e |
313 | $m$, then allocate a new integer~$d$ of size $\sz$ by calling |
3471ebd1 |
314 | \code{mp_create} (page~\pageref{fn:mp-create}). |
315 | \item Otherwise, if $m$ has more than one reference, a reference is removed |
316 | asif by \code{mp_drop} (page~\pageref{fn:mp-drop}) and a new integer $d$ of |
317 | size $\sz$ is allocated as if by \code{mp_create}. |
674cd11e |
318 | \item Otherwise, the integer~$m$ is extended to $\sz$ words, as if by calling |
319 | \code{mp_ensure} (page~\pageref{fn:mp-ensure}), and $d$ is set equal |
320 | to~$m$. |
3471ebd1 |
321 | \end{itemize} |
322 | |
323 | The resulting integer $d$ is returned from the function. |
324 | |
325 | The upshot of all of this is that $d$ has exactly one reference, space for |
674cd11e |
326 | $\sz$~words of data, and no particular value set. Any other references to |
327 | the original integer~$m$ (whether counted or not) continue to refer to the |
328 | same value. The total number of references to $d$ and~$m$ after |
3471ebd1 |
329 | \code{mp_modify} returns is equal to the initial number of references to $m$ |
330 | before the call. |
331 | |
332 | The macro \code{MP_MODIFY} does the same job using inline code; it sets $m$ |
674cd11e |
333 | to the new integer~$d$ when it's finished. The macro expands to a fairly |
3471ebd1 |
334 | large chunk of code. |
335 | |
336 | \fsec{Returns} |
337 | |
674cd11e |
338 | The function \code{mp_modify} returns the destination integer~$d$ as |
3471ebd1 |
339 | described above. |
340 | |
341 | |
342 | \subsection{Resizing multiprecision integers} |
343 | \label{sec:mp-resize} |
344 | |
345 | There are a collection of useful functions and macros for changing the size |
346 | of a multiprecision integer. |
347 | |
348 | \subsubsection{The \code{mp_resize} function and \code{MP_RESIZE} macro} |
349 | \label{fn:mp-resize} |
350 | |
351 | \fsec{Synopsis} |
352 | |
353 | \begin{listinglist} |
354 | |#include <catacomb/mp.h>| \\ |
355 | |void mp_resize(mp *|$m$|, size_t |$\sz$|);| \\ |
356 | |void MP_RESIZE(mp *|$m$|, size_t |$\sz$|);| |
357 | \end{listinglist} |
358 | |
359 | \fsec{Description} |
360 | |
361 | The function \code{mp_resize} resizes the array used to hold the value of the |
674cd11e |
362 | integer~$m$ such that it has space for $\sz$ words. No check is made to see |
3471ebd1 |
363 | whether $m$'s array is already the correct size. The integer's array limit |
674cd11e |
364 | pointer \code{vl} is set to point $\sz$~words higher than the base pointer |
3471ebd1 |
365 | \code{v}. |
366 | |
367 | The macro \code{MP_RESIZE} performs exactly the same action as the |
368 | \code{mp_resize} function, except that it uses inline code rather than a |
369 | function call. It's slightly faster but uses quite a lot more code than the |
370 | plain function call. |
371 | |
372 | \subsubsection{The \code{mp_ensure} function and \code{MP_ENSURE} macro} |
373 | \label{fn:mp-ensure} |
374 | |
375 | \fsec{Synopsis} |
376 | |
377 | \begin{listinglist} |
378 | |#include <catacomb/mp.h>| \\ |
379 | |void mp_ensure(mp *|$m$|, size_t |$\sz$|);| \\ |
380 | |void MP_ENSURE(mp *|$m$|, size_t |$\sz$|);| |
381 | \end{listinglist} |
382 | |
383 | \fsec{Description} |
384 | |
385 | The function \code{mp_ensure} resizes the integer $m$ (as if by calling |
386 | \code{mp_resize}) if its array is currently smaller than $\sz$ words; if not, |
387 | the array is left alone. The integer's array limit pointer \code{vl} is set |
388 | to point $\sz$ words higher than the base pointer \code{v}. |
389 | |
390 | The macro \code{MP_ENSURE} performs exactly the same action as the |
391 | \code{mp_ensure} function, except that it uses inline code rather than a |
392 | function call. It's slightly faster but uses considerably more code. |
393 | |
394 | \subsubsection{The \code{mp_shrink} function and \code{MP_SHRINK} macro} |
395 | \label{fn:mp-shrink} |
396 | |
397 | \fsec{Synopsis} |
398 | |
399 | \begin{listinglist} |
400 | |#include <catacomb/mp.h>| \\ |
401 | |void mp_shrink(mp *|$m$|);| \\ |
402 | |void MP_SHRINK(mp *|$m$|);| |
403 | \end{listinglist} |
404 | |
405 | \fsec{Description} |
406 | |
407 | The function \code{mp_shrink} shrinks the representation of the integer $m$. |
408 | It lowers the integer's array limit pointer so that the most significant word |
409 | in the representation is nonzero. This improves the efficiency of arithmetic |
410 | operations on $m$. |
411 | |
412 | Note that shrinking an integer doesn't release any memory. Use |
413 | \code{mp_minimize} (below) for that. |
414 | |
415 | The macro \code{MP_SHRINK} performs exactly the same operation as |
416 | \code{mp_shrink} using inline code rather than a function call. |
417 | |
418 | \subsubsection{The \code{mp_minimize} function} |
419 | \label{fn:mp-minimize} |
420 | |
421 | \fsec{Synopsis} |
422 | |
423 | \begin{listinglist} |
424 | |#include <catacomb/mp.h>| \\ |
425 | |void mp_minimize(mp *|$m$|);| |
426 | \end{listinglist} |
427 | |
428 | \fsec{Description} |
429 | |
674cd11e |
430 | Minimizes the amount of memory used by the represenation of the integer~$m$. |
3471ebd1 |
431 | This isn't usually useful unless $m$ is going to remain constant for a long |
432 | time, or has become extremely large for some reason. |
433 | |
434 | |
435 | \subsection{Bit-scanning} |
436 | \label{sec:mp-scan} |
437 | |
438 | \subsection{Loading and storing} |
439 | \label{sec:mp-io} |
440 | |
441 | \subsection{Simple arithmetic} |
442 | \label{sec:mp-arith} |
443 | |
444 | \subsection{More advanced algorithms} |
445 | \label{sec:mp-adv} |
446 | |
674cd11e |
447 | \subsubsection{The \code{mp_gcd} function} |
448 | \label{fn:mp-gcd} |
449 | |
450 | \fsec{Synopsis} |
451 | |
452 | \begin{listinglist} |
453 | |#include <catacomb/mp.h>| \\ |
454 | |void mp_gcd(mp **|$g$|, mp **|$a$|, mp **|$b$|, mp *|$x$|, mp *|$y$|);| |
455 | \end{listinglist} |
456 | |
457 | \fsec{Description} |
458 | |
459 | The function \code{mp_gcd} implements an `extended GCD' algorithm. Given |
460 | integers $x$ and~$y$, it computes integers $g$, $a$, and~$b$ such that $g = |
461 | \gcd(x, y)$ is the greatest common divisor of $x$ and $y$, and $ax + by = g$. |
462 | |
463 | If the arguments $g$, $a$ or~$b$ are null pointers, the appropriate result is |
464 | discarded; otherwise, the current value of $|*|g$, $|*|a$ or $|*|b$ is used |
465 | as a suggested destination for the result, and replaced by the actual result. |
466 | |
467 | If both $a$ and~$b$ are null, the results $a$ and $b$ are not computed. |
468 | Hence \code{mp_gcd} can efficiently perform a simple greatest-common-divisor |
469 | computation. |
470 | |
471 | A major use for \code{mp_gcd} is the calculation of modular inverses. If |
472 | $\gcd(x, n) = 1$ then \code{mp_gcd} computes integers $a$ and~$b$ such that |
473 | $ax + bn = 1$, i.e., $ax \equiv 1 \pmod n$, so $a$ is the inverse of $x$, |
474 | written $a \equiv x^{-1} \pmod n$. |
475 | |
476 | In order to better support this usage, \code{mp_gcd} implements a \emph{sign |
477 | preference} system. If only $a$ is requested, it will either be zero or |
478 | have the same sign as~$y$; otherwise, $b$ will be zero or have the same sign |
479 | as~$x$. Thus, $x^{-1} \bmod n$ may be conveniently computed using the code |
480 | \begin{listing} |
481 | mp *xinv = MP_NEW; |
482 | mp_gcd(0, 0, &xinv, n, x); |
483 | \end{listing} |
484 | (It's conventional to ensure that $x > y$, even though it doesn't actually |
485 | make any difference.) |
486 | |
487 | The function \code{mp_gcd} works correctly for all integers $x$ and $y$. The |
488 | following properties of the results are guaranteed: |
489 | \begin{itemize} |
490 | \unverb\| |
491 | \item $\gcd(x, y) = \gcd(y, x)$ for all integers $x$ and~$y$. |
492 | \item $\gcd(x, 0) = \gcd(0, x) = x$ for all integers~$x$. |
493 | \item $|a| < |y|$, unless $y = 0$; similarly, $|b| < |x|$ if $x \ne 0$. |
494 | \item If $x = y = 0$, then $a = b = 0$. Otherwise, if $x = 0$, then $a = 0$ |
495 | and $b = 1$; similarly, if $y = 0$, then $a = 1$ and $b = 0$. |
496 | \end{itemize} |
497 | |
498 | \subsubsection{The \code{mp_jacobi} function} |
499 | \label{fn:mp-jacobi} |
500 | |
501 | \fsec{Synopsis} |
502 | |
503 | \begin{listinglist} |
504 | |#include <catacomb/mp.h>| \\ |
505 | |int mp_jacobi(mp *|$a$|, mp *|$n$|);| |
506 | \end{listinglist} |
507 | |
508 | \fsec{Returns} |
509 | |
510 | The value of the Jacobi symbol $\jacobi{a}{n}$.\footnote{% |
511 | Schneier writes the Jacobi symbol as $J(a, n)$. The notation |
512 | $(\!\frac{a}{n}\!)$ seems more usual.} % |
513 | The Jacobi symbol $\jacobi{a}{n}$ is defined for all integers~$a$ and odd |
514 | integers~$n$ in terms of the Legendre symbol $\jacobi{a}{p}$ for prime~$p$, |
515 | which is: |
516 | \[ |
517 | \jacobi{a}{p} = \begin{cases} |
518 | 0 & if $a$ is a multiple of $p$ \\ |
519 | -1 & if $a$ is a quadratic nonresidue mod $p$ \\ |
520 | 1 & if $a$ is a quadratic residue mod $p$ |
521 | \end{cases} |
522 | \] |
523 | (An integer $x$ is a quadratic residue mod $n$ if and only if there exists an |
524 | integer $y$ such that $y^2 \equiv x \pmod n$. Note that $\jacobi{a}{p} |
525 | \equiv a^{(p - 1)/2} \pmod p$.) |
526 | |
527 | The Jacobi symbol is defined as follows: let $p_0^{e_0} p_1^{e_1} \ldots |
528 | p_k^{e_k} = n$ be the prime factors of $n$. Then |
529 | \[ |
530 | \jacobi{a}{n} = \jacobi{a}{p_0}^{e_0} \jacobi{a}{p_1}^{e_1} \cdots |
531 | \jacobi{a}{p_k}^{e_k} |
532 | \] |
533 | Fortunately, the Jacobi symbol can be computed efficiently without factoring |
534 | $n$ or performing modular exponentiations. |
535 | |
536 | The Jacobi symbol is used in the Solovay-Strassen primality test (not |
537 | implemented in Catacomb -- the Rabin-Miller test is better), and in some |
538 | subliminal channels in digital signature algorithms. |
539 | |
540 | The RSA public-key encryption algorithm leaks the Jacobi symbol of its |
541 | plaintext. |
542 | |
3471ebd1 |
543 | %%% Local Variables: |
544 | %%% mode: latex |
545 | %%% TeX-master: "catacomb" |
546 | %%% End: |