1 /* Test mpz_gcd_ui. 2 3 Copyright 2003 Free Software Foundation, Inc. 4 5 This file is part of the GNU MP Library test suite. 6 7 The GNU MP Library test suite is free software; you can redistribute it 8 and/or modify it under the terms of the GNU General Public License as 9 published by the Free Software Foundation; either version 3 of the License, 10 or (at your option) any later version. 11 12 The GNU MP Library test suite is distributed in the hope that it will be 13 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General 15 Public License for more details. 16 17 You should have received a copy of the GNU General Public License along with 18 the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ 19 20 #include <stdio.h> 21 #include <stdlib.h> 22 23 #include "gmp-impl.h" 24 #include "tests.h" 25 26 /* Check mpz_gcd_ui doesn't try to return a value out of range. 27 This was wrong in gmp 4.1.2 with a long long limb. */ 28 static void 29 check_ui_range (void) 30 { 31 unsigned long got; 32 mpz_t x; 33 int i; 34 35 mpz_init_set_ui (x, ULONG_MAX); 36 37 for (i = 0; i < 20; i++) 38 { 39 mpz_mul_2exp (x, x, 1L); 40 got = mpz_gcd_ui (NULL, x, 0L); 41 if (got != 0) 42 { 43 printf ("mpz_gcd_ui (ULONG_MAX*2^%d, 0)\n", i); 44 printf (" return %#lx\n", got); 45 printf (" should be 0\n"); 46 abort (); 47 } 48 } 49 50 mpz_clear (x); 51 } 52 53 static void 54 check_ui_factors (void) 55 { 56 #define NUM_FACTORS 9 57 static const char* factors[NUM_FACTORS] = { 58 "641", "274177", "3", "5", "17", "257", "65537", 59 "59649589127497217", "1238926361552897" }; 60 unsigned long got; 61 mpz_t x, b, d, f, g; 62 int i, j; 63 gmp_randstate_ptr rands; 64 65 if (GMP_NUMB_BITS < 5 || GMP_NUMB_BITS == 8 66 || GMP_NUMB_BITS == 16 || GMP_NUMB_BITS > 511) 67 { 68 printf ("No usable factors for 2^%i+1.\n", GMP_NUMB_BITS); 69 return; 70 } 71 72 mpz_init (x); 73 mpz_init (d); 74 mpz_init (f); 75 mpz_init (g); 76 77 mpz_setbit (x, GMP_NUMB_BITS); 78 mpz_add_ui (x, x, 1); 79 80 for (i = 0; i < NUM_FACTORS; ++i) 81 { 82 mpz_set_str (f, factors[i], 10); 83 if (mpz_divisible_p (x, f)) 84 { 85 mpz_mul_2exp (f, f, 1); 86 /* d is an odd multiple of the factor f, exactly filling a limb. */ 87 mpz_sub (d, x, f); 88 /* f = 2^GMP_NUMB_BITS mod d. */ 89 mpz_sub_ui (f, f, 1); 90 break; 91 } 92 } 93 94 mpz_gcd (g, f, d); 95 if (mpz_even_p (d) || mpz_cmp (d, f) <= 0 || mpz_cmp_ui (g, 1) != 0) 96 { 97 printf ("No usable factor found.\n"); 98 abort (); 99 } 100 101 rands = RANDS; 102 mpz_mul_ui (x, d, gmp_urandomm_ui (rands, 30000) + 1); 103 104 mpz_init (b); 105 mpz_setbit (b, GMP_NUMB_BITS - 1); 106 for (j = 0; j < 4; ++j) 107 { 108 mpz_add (x, x, b); 109 110 for (i = 1; i >= -1; --i) 111 { 112 if (mpz_fits_ulong_p (d) 113 && ((got = mpz_gcd_ui (NULL, x, mpz_get_ui (d))) 114 != (i != 0 ? 1 : mpz_get_ui (d)))) 115 { 116 printf ("mpz_gcd_ui (f, kV+%i*2^%i, V): error (j = %i)\n", i, GMP_NUMB_BITS - 1, j); 117 printf (" return %#lx\n", got); 118 printf (" should be %#lx\n", (i != 0 ? 1 : mpz_get_ui (d))); 119 abort (); 120 } 121 122 mpz_gcd (g, x, d); 123 if ((mpz_cmp_ui (g, 1) == 0) != (i != 0)) 124 { 125 printf ("mpz_gcd (f, kV+%i*2^%i, V): error (j = %i)\n", i, GMP_NUMB_BITS - 1, j); 126 printf (" should%s be one.\n",(i != 0 ? "" : " not")); 127 abort (); 128 } 129 130 mpz_sub (x, x, b); 131 } 132 /* Back to the original x. */ 133 mpz_addmul_ui (x, b, 2); 134 mpz_mul (b, b, f); 135 mpz_mod (b, b, d); 136 } 137 138 mpz_clear (g); 139 mpz_clear (x); 140 mpz_clear (f); 141 mpz_clear (d); 142 mpz_clear (b); 143 } 144 145 146 int 147 main (void) 148 { 149 tests_start (); 150 151 check_ui_range (); 152 check_ui_factors (); 153 154 tests_end (); 155 exit (0); 156 } 157