batchgcd.h (1382B)
1 #ifndef _BATCHGCD_H_ 2 #define _BATCHGCD_H_ 3 4 /** 5 * Standard batch GCD (product-tree-remainder-tree) 6 * 7 * This function computes the GCDs between v[i] and the product of all 8 * the v[j] for i != j, for a list of integers v of size n. This 9 * implements the so called Batch GCD algorithm (by Bernstein et al.) 10 * see 11 * 12 * https://facthacks.cr.yp.to/batchgcd.html 13 * 14 * for more information. The result should be r[i] such that 15 * 16 * r[i] = gcd(v[i], v[0]*v[2]*...*v[i-1]*v[i+1]*...v[n-1]). 17 * 18 * @param r the vector in which we put the resulting gcds 19 * @param v the list of integers to compute gcds of 20 * @param n the length of the vector v 21 */ 22 void batch_gcd(fmpz *r, const fmpz *v, slong n); 23 24 /** 25 * Pelofske GCD 26 * 27 * This function computes the batch GCD, using Pelofske's algorithm. 28 * This is an alternative algorithm that is reported to be faster than 29 * standard Batch GCD (it is not, however). See 30 * 31 * https://eprint.iacr.org/2024/699 32 * 33 * for more details. There is a writiteup comparison at 34 * 35 * https://krutimyltan2.github.io/20240528_bernstein_vs_pelofske.txt 36 * 37 * as well. Do not use this, stick to batch_gcd() instead for 38 * performance. 39 * 40 * @param r the vector in which we put the resulting gcds 41 * @param v the list of integers to compute gcds of 42 * @param n the length of the vector v 43 */ 44 void pelofske_gcd(fmpz *r, const fmpz *v, slong n); 45 46 #endif