1 /* --------------------------------------------------------------------- 2 * 3 * -- Integer Matrix Library (IML) 4 * (C) Copyright 2004, 2006 All Rights Reserved 5 * 6 * -- IML routines -- Version 1.0.1 -- November, 2006 7 * 8 * Author : Zhuliang Chen 9 * Contributor(s) : Arne Storjohann, Cory Fletcher 10 * University of Waterloo -- School of Computer Science 11 * Waterloo, Ontario, N2L3G1 Canada 12 * 13 * --------------------------------------------------------------------- 14 * 15 * -- Copyright notice and Licensing terms: 16 * 17 * Redistribution and use in source and binary forms, with or without 18 * modification, are permitted provided that the following conditions 19 * are met: 20 * 21 * 1. Redistributions of source code must retain the above copyright 22 * notice, this list of conditions and the following disclaimer. 23 * 2. Redistributions in binary form must reproduce the above copyright 24 * notice, this list of conditions, and the following disclaimer in 25 * the documentation and/or other materials provided with the distri- 26 * bution. 27 * 3. The name of the University, the IML group, or the names of its 28 * contributors may not be used to endorse or promote products deri- 29 * ved from this software without specific written permission. 30 * 31 * -- Disclaimer: 32 * 33 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 34 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 35 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 36 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE UNIVERSITY 37 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPE- 38 * CIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 39 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, 40 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEO- 41 * RY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (IN- 42 * CLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 43 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 44 * 45 */ 46 47 48 /* 49 * 50 * certsolve.h includes routines certified solving system of linear equations 51 * with input matrix in any shape. 52 * 53 * Functions: 54 * - revseq: perform operations on the permutation vector 55 * 56 * - compressBoundLong: compute the maximum magnitude of a compressed signed 57 * long submatrix 58 * 59 * - compressBoundMP: compute the maximum magnitude of a compressed mpz_t 60 * submatrix 61 * 62 * - LVecSMatMulCmp: verify the equality of a matrix-vector product and a 63 * scalar-vector product 64 * 65 * - specialminSolveLong: compute the minimal denominator solution of a full 66 * row rank system, represented by signed long integers, and corresponding 67 * certificate vector(optional). The solution size could be reduced. 68 * 69 * - specialminSolveRNS: compute the minimal denominator solution of a full 70 * row rank system, represented in RNS, and corresponding certificate 71 * vector(optional). The solution size could be reduced. 72 * 73 * - certVerify: verify the correctness of a certificate vector for a system 74 * of linear equations 75 * 76 * - minSolnoncompressLong: compute the minimal denominator solution of a 77 * full row rank system without compression, represented by signed long 78 * integers, and the corresponding certificate vector(optional). The 79 * solution size could be reduced. 80 * 81 * - minSolnoncompressRNS: compute the minimal denominator solution of a 82 * full row rank system without compression, represented in RNS, and the 83 * corresponding certificate vector(optional). The solution size could be 84 * reduced. 85 * 86 * - specialHermite: perform unimodular transformation inplace in matrix M 87 * and return an certificate matrix Cert(optional) at the same time 88 * 89 * - mpz_init_array: allocate a mpz_t array length n dynamically and set all 90 * the entries in the array to be zero. 91 * 92 * - migcdex: compute solutions to the modulo N extended GCD problem 93 * 94 * - kernelBasis: compute a kernel basis of a full row rank matrix 95 * 96 */ 97 98 99 #ifndef CERTSOLVE_H 100 #define CERTSOLVE_H 1 101 102 #include "cblas.h" 103 #include "gmp.h" 104 #include "common.h" 105 #include "basisop.h" 106 #include "latreduce.h" 107 #include "padiclift.h" 108 #include "reconsolu.h" 109 #include "RNSop.h" 110 #include "iml.h" 111 112 #define _M(i,j) (M[((i)-1)*(k+t)+(j)-1]) 113 #define _Cert(i,j) (Cert[((i)-1)*(n+k+t)+(j)-1]) 114 #define _C(i,j) (C[((i)-1)*(n-1)+(j)-1]) 115 116 #define _P(i) (P[(i)-1]) 117 #define _Q(i) (Q[(i)-1]) 118 #define _P1(i) (P1[(i)-1]) 119 #define _Q1(i) (Q1[(i)-1]) 120 #define _c(i) (c[(i)-1]) 121 #define _tmpz(i) (tmpz[(i)-1]) 122 123 long LVecSMatMulCmp (const enum MULT_POS mulpos, const long basislen, \ 124 const long n, const long m, const FiniteField *basis, \ 125 Double **ARNS, mpz_t mp_s, mpz_t *mp_V, mpz_t *mp_b); 126 127 long * revseq (const long r, const long m, const long *A); 128 129 void compressBoundLong (const long n, const long m, const long *Pt, \ 130 const long *A, mpz_t mp_bd); 131 132 void compressBoundMP (const long n, const long m, const long *Pt, \ 133 mpz_t *mp_A, mpz_t mp_bd); 134 135 136 long specialminSolveLong (const long certflag, const long redflag, \ 137 const long nullcol, const long n, const long m, \ 138 const mpz_t mp_bdC, const long *C, mpz_t *mp_b, \ 139 mpz_t *mp_N, mpz_t mp_D, mpz_t *mp_NZ, mpz_t mp_DZ); 140 141 long LongRNSbound(void); 142 143 long specialminSolveRNS (const long certflag, const long redflag, 144 const long nullcol, const long n, const long m, \ 145 const long basislen, const mpz_t mp_bdC, \ 146 const FiniteField *basis, Double **CRNS, \ 147 mpz_t *mp_b, mpz_t *mp_N, mpz_t mp_D,\ 148 mpz_t *mp_NZ, mpz_t mp_DZ); 149 150 long certVerify (const long basislen, const long n, const long m, \ 151 const FiniteField *basis, Double **ARNS, mpz_t mp_DZ, \ 152 mpz_t *mp_NZ); 153 154 void minSolnoncompressLong (const long certflag, const long redflag, \ 155 const long n, const long k, mpz_t *mp_Bb, \ 156 const long* A, mpz_t *mp_N, mpz_t mp_D, \ 157 mpz_t *mp_NZ, mpz_t mp_DZ); 158 159 void minSolnoncompressRNS (const long certflag, const long redflag, \ 160 const long n, const long k, const long basislen, \ 161 const FiniteField *basis, mpz_t *mp_Bb, \ 162 Double **ARNS, mpz_t *mp_N, mpz_t mp_D, \ 163 mpz_t *mp_NZ, mpz_t mp_DZ); 164 165 void specialHermite (const long certflag, const long n, const long k, \ 166 const long t, mpz_t *M, mpz_t *Cert); 167 168 mpz_t * mpz_init_array (const long n); 169 170 void migcdex (const mpz_t N, const mpz_t a, mpz_t *b, const long n, \ 171 unsigned *c); 172 173 void kernelBasis (const long n, const long k, const long t, mpz_t *mp_M, mpz_t *mp_N); 174 175 #endif /* !CERTSOLV_H */ 176 177 178