FLINT Fast Library for Number Theory Version 2.3.0 1 July 2012 William Hart∗, Fredrik Johansson†, Sebastian Pancratz‡ ∗ Supported by EPSRC Grant EP/G004870/1 † Supported by Austrian Science Foundation (FWF) Grant Y464-N18 ‡ Supported by European Research Council Grant 204083 Contents 1 Introduction 1 2 Building and using FLINT 3 3 Test code 5 4 Reporting bugs 7 5 Contributors 9 6 Tuning FLINT 11 7 Example programs 13 8 FLINT macros 15 9 fmpz 17 9.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 9.2 Simple example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 9.3 Memory management . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 9.4 Random generation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 9.5 Conversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 9.6 Input and output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 9.7 Basic properties and manipulation . . . . . . . . . . . . . . . . . . . . . 22 9.8 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 9.9 Basic arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 9.10 Greatest common divisor . . . . . . . . . . . . . . . . . . . . . . . . . . 28 9.11 Modular arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 9.12 Bit packing and unpacking . . . . . . . . . . . . . . . . . . . . . . . . . 29 9.13 Logic Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 9.14 Chinese remaindering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 10 fmpz vec 33 10.1 Memory management . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 10.2 Randomisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 10.3 Bit sizes and norms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 10.4 Input and output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 10.5 Conversions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 10.6 Assignment and basic manipulation . . . . . . . . . . . . . . . . . . . . 35 10.7 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 10.8 Sorting. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 10.9 Addition and subtraction . . . . . . . . . . . . . . . . . . . . . . . . . . 36 10.10 Scalar multiplication and division . . . . . . . . . . . . . . . . . . . . . . 36 10.11 Sums and products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 10.12 Reduction mod p . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 Contents iii 10.13 Gaussian content . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 11 fmpz factor 39 11.1 Factoring integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 12 fmpz mat 41 12.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 12.2 Simple example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 12.3 Memory management . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 12.4 Basic assignment and manipulation . . . . . . . . . . . . . . . . . . . . . 42 12.5 Random matrix generation . . . . . . . . . . . . . . . . . . . . . . . . . 42 12.6 Input and output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 12.7 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 12.8 Transpose . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 12.9 Modular reduction and reconstruction . . . . . . . . . . . . . . . . . . . 45 12.10 Addition and subtraction . . . . . . . . . . . . . . . . . . . . . . . . . . 46 12.11 Matrix-scalar arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 12.12 Matrix multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 12.13 Inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 12.14 Trace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 12.15 Determinant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 12.16 Rank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 12.17 Nonsingular solving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 12.18 Row reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 12.19 Nullspace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 12.20 Echelon form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 13 fmpz poly 53 13.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 13.2 Simple example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 13.3 Definition of the fmpz poly t type . . . . . . . . . . . . . . . . . . . . . 54 13.4 Memory management . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 13.5 Polynomial parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 13.6 Assignment and basic manipulation . . . . . . . . . . . . . . . . . . . . 55 13.7 Randomisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 13.8 Getting and setting coefficients . . . . . . . . . . . . . . . . . . . . . . . 57 13.9 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 13.10 Addition and subtraction . . . . . . . . . . . . . . . . . . . . . . . . . . 58 13.11 Scalar multiplication and division . . . . . . . . . . . . . . . . . . . . . . 59 13.12 Bit packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 13.13 Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 13.14 Squaring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 13.15 Powering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 13.16 Shifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 13.17 Bit sizes and norms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 13.18 Greatest common divisor . . . . . . . . . . . . . . . . . . . . . . . . . . 68 13.19 Gaussian content . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 13.20 Euclidean division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 13.21 Divisibility testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 13.22 Power series division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 13.23 Pseudo division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 13.24 Derivative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 13.25 Evaluation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 13.26 Newton basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 iv Contents 13.27 Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 13.28 Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 13.29 Taylor shift . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 13.30 Power series composition. . . . . . . . . . . . . . . . . . . . . . . . . . . 81 13.31 Power series reversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 13.32 Square root . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 13.33 Signature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 13.34 Hensel lifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 13.35 Input and output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 13.36 Modular reduction and reconstruction . . . . . . . . . . . . . . . . . . . 89 13.37 Products. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 13.38 Newton basis conversion . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 14 fmpz poly factor 93 14.1 Memory management . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 14.2 Manipulating factors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 14.3 Input and output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 14.4 Factoring algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 15 fmpq 97 15.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 15.2 Memory management . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 15.3 Canonicalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 15.4 Basic assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 15.5 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 15.6 Conversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 15.7 Input and output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 15.8 Random number generation . . . . . . . . . . . . . . . . . . . . . . . . . 101 15.9 Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 15.10 Modular reduction and rational reconstruction . . . . . . . . . . . . . . 103 15.11 Rational enumeration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 15.12 Continued fractions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 15.13 Summation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 16 fmpq mat 107 16.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 16.2 Memory management . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 16.3 Entry access. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 16.4 Basic assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 16.5 Addition, scalar multiplication . . . . . . . . . . . . . . . . . . . . . . . 108 16.6 Input and output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 16.7 Random matrix generation . . . . . . . . . . . . . . . . . . . . . . . . . 109 16.8 Special matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 16.9 Basic comparison and properties . . . . . . . . . . . . . . . . . . . . . . 109 16.10 Integer matrix conversion . . . . . . . . . . . . . . . . . . . . . . . . . . 109 16.11 Modular reduction and rational reconstruction . . . . . . . . . . . . . . 110 16.12 Matrix multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 16.13 Trace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 16.14 Determinant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 16.15 Nonsingular solving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 16.16 Inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 16.17 Echelon form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 17 fmpq poly 113 17.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 Contents v 17.2 Memory management . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 17.3 Polynomial parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 17.4 Accessing the numerator and denominator . . . . . . . . . . . . . . . . . 115 17.5 Random testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 17.6 Assignment, swap, negation . . . . . . . . . . . . . . . . . . . . . . . . . 116 17.7 Getting and setting coefficients . . . . . . . . . . . . . . . . . . . . . . . 117 17.8 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 17.9 Addition and subtraction . . . . . . . . . . . . . . . . . . . . . . . . . . 119 17.10 Scalar multiplication and division . . . . . . . . . . . . . . . . . . . . . . 119 17.11 Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 17.12 Powering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 17.13 Shifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 17.14 Euclidean division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 17.15 Power series division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 17.16 Greatest common divisor . . . . . . . . . . . . . . . . . . . . . . . . . . 124 17.17 Derivative and integral . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 17.18 Square roots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 17.19 Transcendental functions. . . . . . . . . . . . . . . . . . . . . . . . . . . 126 17.20 Evaluation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 17.21 Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 17.22 Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 17.23 Power series composition. . . . . . . . . . . . . . . . . . . . . . . . . . . 130 17.24 Power series reversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 17.25 Gaussian content . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 17.26 Square-free . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 17.27 Input and output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 18 fmpz poly q 137 18.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 18.2 Simple example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 18.3 Memory management . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 18.4 Randomisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 18.5 Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 18.6 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 18.7 Addition and subtraction . . . . . . . . . . . . . . . . . . . . . . . . . . 139 18.8 Scalar multiplication and division . . . . . . . . . . . . . . . . . . . . . . 140 18.9 Multiplication and division . . . . . . . . . . . . . . . . . . . . . . . . . 140 18.10 Powering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 18.11 Derivative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 18.12 Evaluation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 18.13 Input and output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 19 fmpz poly mat 143 19.1 Simple example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 19.2 Memory management . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 19.3 Basic properties. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 19.4 Basic assignment and manipulation . . . . . . . . . . . . . . . . . . . . . 144 19.5 Input and output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 19.6 Random matrix generation . . . . . . . . . . . . . . . . . . . . . . . . . 145 19.7 Special matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 19.8 Basic comparison and properties . . . . . . . . . . . . . . . . . . . . . . 145 19.9 Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 19.10 Evaluation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 19.11 Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 vi Contents 19.12 Row reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 19.13 Trace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 19.14 Determinant and rank . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 19.15 Inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 19.16 Nullspace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 19.17 Solving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 20 nmod vec 151 20.1 Memory management . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 20.2 Modular reduction and arithmetic . . . . . . . . . . . . . . . . . . . . . 151 20.3 Random functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 20.4 Basic manipulation and comparison . . . . . . . . . . . . . . . . . . . . 152 20.5 Arithmetic operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 20.6 Dot products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 21 nmod poly 155 21.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 21.2 Simple example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 21.3 Definition of the nmod poly t type . . . . . . . . . . . . . . . . . . . . . 156 21.4 Memory management . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 21.5 Polynomial properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 21.6 Assignment and basic manipulation . . . . . . . . . . . . . . . . . . . . 157 21.7 Randomisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 21.8 Getting and setting coefficients . . . . . . . . . . . . . . . . . . . . . . . 158 21.9 Input and output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 21.10 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 21.11 Shifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 21.12 Addition and subtraction . . . . . . . . . . . . . . . . . . . . . . . . . . 159 21.13 Scalar multiplication and division . . . . . . . . . . . . . . . . . . . . . . 160 21.14 Bit packing and unpacking . . . . . . . . . . . . . . . . . . . . . . . . . 160 21.15 Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 21.16 Powering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 21.17 Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 21.18 Derivative and integral . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 21.19 Evaluation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 21.20 Multipoint evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 21.21 Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 21.22 Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 21.23 Taylor shift . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 21.24 Modular composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 21.25 Greatest common divisor . . . . . . . . . . . . . . . . . . . . . . . . . . 173 21.26 Power series composition. . . . . . . . . . . . . . . . . . . . . . . . . . . 176 21.27 Power series reversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 21.28 Square roots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 21.29 Transcendental functions. . . . . . . . . . . . . . . . . . . . . . . . . . . 180 21.30 Products. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 21.31 Subproduct trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 21.32 Inflation and deflation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 21.33 Factorisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 22 nmod mat 187 22.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 22.2 Memory management . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 22.3 Basic properties and manipulation . . . . . . . . . . . . . . . . . . . . . 188 Contents vii 22.4 Printing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 22.5 Random matrix generation . . . . . . . . . . . . . . . . . . . . . . . . . 188 22.6 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 22.7 Transpose . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 22.8 Addition and subtraction . . . . . . . . . . . . . . . . . . . . . . . . . . 189 22.9 Matrix-scalar arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 22.10 Matrix multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 22.11 Trace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 22.12 Determinant and rank . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 22.13 Inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 22.14 Triangular solving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 22.15 Nonsingular square solving . . . . . . . . . . . . . . . . . . . . . . . . . 192 22.16 LU decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 22.17 Reduced row echelon form . . . . . . . . . . . . . . . . . . . . . . . . . . 192 22.18 Nullspace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 23 nmod poly mat 195 23.1 Memory management . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 23.2 Basic properties. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 23.3 Basic assignment and manipulation . . . . . . . . . . . . . . . . . . . . . 196 23.4 Input and output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 23.5 Random matrix generation . . . . . . . . . . . . . . . . . . . . . . . . . 196 23.6 Special matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 23.7 Basic comparison and properties . . . . . . . . . . . . . . . . . . . . . . 197 23.8 Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 23.9 Evaluation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 23.10 Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 23.11 Row reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 23.12 Trace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 23.13 Determinant and rank . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 23.14 Inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 23.15 Nullspace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 23.16 Solving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 24 fmpz mod poly 203 24.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 24.2 Simple example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 24.3 Definition of the fmpz mod poly t type . . . . . . . . . . . . . . . . . . 204 24.4 Memory management . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204 24.5 Randomisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 24.6 Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 24.7 Assignment and swap . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 24.8 Conversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 24.9 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 24.10 Getting and setting coefficients . . . . . . . . . . . . . . . . . . . . . . . 206 24.11 Shifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 24.12 Addition and subtraction . . . . . . . . . . . . . . . . . . . . . . . . . . 207 24.13 Scalar multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 24.14 Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 24.15 Powering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 24.16 Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 24.17 Power series inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 24.18 Greatest common divisor . . . . . . . . . . . . . . . . . . . . . . . . . . 211 24.19 Derivative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 viii Contents 24.20 Evaluation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 24.21 Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 24.22 Radix conversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 24.23 Input and output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 25 padic 219 25.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 25.2 Data structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 25.3 Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 25.4 Memory management . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 25.5 Randomisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 25.6 Assignments and conversions . . . . . . . . . . . . . . . . . . . . . . . . 221 25.7 Arithmetic operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 25.8 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 25.9 Special functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 25.10 Input and output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 26 arith 231 26.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 26.2 Primorials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 26.3 Harmonic numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 26.4 Stirling numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 26.5 Bell numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 26.6 Bernoulli numbers and polynomials . . . . . . . . . . . . . . . . . . . . . 234 26.7 Euler numbers and polynomials . . . . . . . . . . . . . . . . . . . . . . . 236 26.8 Legendre polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 26.9 Multiplicative functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 26.10 Cyclotomic polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . 238 26.11 Swinnerton-Dyer polynomials . . . . . . . . . . . . . . . . . . . . . . . . 239 26.12 Landau’s function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 26.13 Dedekind sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240 26.14 Number of partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 26.15 Sums of squares. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 26.16 MPFR extras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 27 ulong extras 245 27.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 27.2 Simple example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 27.3 Random functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246 27.4 Basic arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247 27.5 Miscellaneous . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247 27.6 Basic arithmetic with precomputed inverses . . . . . . . . . . . . . . . . 247 27.7 Greatest common divisor . . . . . . . . . . . . . . . . . . . . . . . . . . 249 27.8 Jacobi and Kronecker symbols . . . . . . . . . . . . . . . . . . . . . . . 250 27.9 Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250 27.10 Prime number generation and counting . . . . . . . . . . . . . . . . . . 252 27.11 Primality testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 27.12 Square root and perfect power testing . . . . . . . . . . . . . . . . . . . 255 27.13 Factorisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256 27.14 Arithmetic functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 27.15 Factorials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 28 long extras 261 28.1 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 28.2 Random functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 Contents ix 29 fft 263 29.1 Split/combine FFT coefficients . . . . . . . . . . . . . . . . . . . . . . . 263 29.2 Test helper functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264 29.3 Arithmetic modulo a generalised Fermat number . . . . . . . . . . . . . 264 29.4 Generic butterflies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264 29.5 Radix 2 transforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265 29.6 Matrix Fourier Transforms. . . . . . . . . . . . . . . . . . . . . . . . . . 268 29.7 Negacyclic multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . 270 29.8 Integer multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271 29.9 Convolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272 30 qsieve 273 30.1 Quadratic sieve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273 31 longlong.h 275 31.1 Auxiliary asm macros . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275 32 mpn extras 277 32.1 Macros. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 32.2 Utility functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 32.3 Divisibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 32.4 Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 32.5 GCD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 32.6 Special numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 33 profiler 279 33.1 Timer based on the cycle counter . . . . . . . . . . . . . . . . . . . . . . 279 33.2 Framework for repeatedly sampling a single target . . . . . . . . . . . . 280 34 interfaces 281 34.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 34.2 NTL Interface. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 References 283