1 // -*- C++ -*- 2 //============================================================================================== 3 // 4 // This file is part of LiDIA --- a library for computational number theory 5 // 6 // Copyright (c) 1994--2003 the LiDIA Group. All rights reserved. 7 // 8 // See http://www.informatik.tu-darmstadt.de/TI/LiDIA/ 9 // 10 //---------------------------------------------------------------------------------------------- 11 // 12 // 13 // File : prime_proof_ecpp_is_good_order.cc 14 // Author : Jochen Hechler (JH) 15 // Changes : See CVS log 16 // 17 //============================================================================================== 18 19 #include <iostream> 20 #include "LiDIA/path.h" 21 #include "LiDIA/prime_proof.h" 22 #include "LiDIA/bigint.h" 23 #include "LiDIA/bigfloat.h" 24 #include "LiDIA/base_vector.h" 25 #include "LiDIA/factorization.h" 26 #include "LiDIA/LiDIA.h" 27 #include "LiDIA/error.h" 28 29 30 31 #ifdef LIDIA_NAMESPACE 32 namespace LiDIA { 33 # define IN_NAMESPACE_LIDIA 34 #endif 35 36 37 // different modi are as follow 38 // ecpp_order_mode 0: first try prime_list, then try factorizing (default) 39 // ecpp_order_mode 1: try only prime_list, if there is no good_discriminant compute the next primelist and start ove 40 // ecpp_order_mode 2: try only factorization 41 // the downstep will be activated 42 is_good_order(bigint & t,bigint & y)43 bool prime_proof::is_good_order(bigint & t, bigint & y) 44 { 45 // m_{\pm} = n + 1 \pm t; 46 // try for both m if there is a divisor in the primelist 47 bigint m_plus_t = n + 1 + t; 48 bigint m_minus_t = n + 1 - t; 49 50 // the following orders are only for D=-3 and D=-4 51 bigint m_3,m_4,m_5,m_6; 52 // D = -4 53 if(D==-4){ 54 m_3 = n + 1 + 2*y; 55 m_4 = n + 1 - 2*y; 56 } 57 if(D==-3){ 58 m_3 = n + 1 + t + 3*y; 59 m_4 = n + 1 - t - 3*y; 60 m_5 = n + 1 + t - 3*y; 61 m_6 = n + 1 - t + 3*y; 62 } 63 int i = 0; 64 int jj; 65 if(ecpp_order_mode==0 || ecpp_order_mode==1){ 66 prime_factor = start_list; 67 bigint rest_1; 68 bigint rest_2; 69 bigint rest_3; 70 bigint rest_4; 71 bigint rest_5; 72 bigint rest_6; 73 while(i < pl_length) 74 { 75 remainder(rest_1,m_plus_t,prime_factor); 76 remainder(rest_2,m_minus_t,prime_factor); 77 if(D==-4){ 78 remainder(rest_3,m_3,prime_factor); 79 remainder(rest_4,m_4,prime_factor); 80 if(rest_3 == 0 || rest_4 == 0) 81 { 82 if(rest_3 == 0)order = m_3; 83 if(rest_4 == 0)order = m_4; 84 if(prove_downstep(prime_factor))return prove_n_with_curve(); 85 } 86 87 } 88 if(D==-3){ 89 remainder(rest_3,m_3,prime_factor); 90 remainder(rest_4,m_4,prime_factor); 91 remainder(rest_5,m_5,prime_factor); 92 remainder(rest_6,m_6,prime_factor); 93 if(rest_3 == 0 || rest_4 == 0 || rest_5 == 0 || rest_6 == 0) 94 { 95 if(rest_3 == 0)order = m_3; 96 if(rest_4 == 0)order = m_4; 97 if(rest_5 == 0)order = m_5; 98 if(rest_6 == 0)order = m_6; 99 if(prove_downstep(prime_factor))return prove_n_with_curve(); 100 } 101 } 102 if(rest_1 == 0 || rest_2 == 0) 103 { 104 if(rest_1==0)order = m_plus_t; 105 if(rest_2==0)order = m_minus_t; 106 if(prove_downstep(prime_factor))return prove_n_with_curve(); 107 } 108 prime_factor = prime_factor + prime_list[i]; 109 i++; 110 111 } 112 } 113 if(ecpp_order_mode==0 || ecpp_order_mode==2 || mode_one_tried){ 114 if(verbose) { 115 std::cout<<"ecpp: Begin factorization"<<std::endl; 116 } 117 118 static char const env_var_name[] = "LIDIA_PRIME_DIFFS"; 119 120 char const* env_lidia_primes = getenv(env_var_name); 121 std::string in_file; 122 if(env_lidia_primes) { 123 in_file = env_lidia_primes; 124 } 125 if(in_file.empty()) { 126 in_file = LIDIA_PRIME_DIFFS; 127 } 128 129 std::ifstream in; 130 in.open(in_file.c_str()); 131 if(!in.good()) { 132 std::string msg("Can't open file "); 133 msg += in_file; 134 lidia_error_handler("prime_proof::is_good_order()", 135 msg.c_str()); 136 } 137 138 bigint n_plus_one = n + 1; 139 bigint rem_t,rem; 140 141 bigint prime = 0; 142 int append; 143 // first divide the possible orders by the stored primes 144 while(in.good()) 145 { 146 in >> append; 147 if(in.fail() && in.eof()) { 148 break; 149 } 150 else if(in.fail()) { 151 std::string msg("Error while reading from file "); 152 msg += in_file; 153 lidia_error_handler("prime_proof::is_good_order()", 154 msg.c_str()); 155 } 156 157 add(prime,prime,append); 158 if(prime > (m_minus_t)) { 159 break; 160 } 161 remainder(rem,n_plus_one,prime); 162 remainder(rem_t,t,prime); 163 if(rem==rem_t) { 164 while((m_minus_t%prime)==0) { 165 m_minus_t=m_minus_t/prime; 166 } 167 } 168 rem.negate(); 169 add(rem,rem,prime); 170 if(rem==rem_t) { 171 while((m_plus_t%prime)==0) { 172 m_plus_t=m_plus_t/prime; 173 } 174 } 175 if(D==-4 || D==-3) 176 { 177 while((m_3%prime)==0) { 178 m_3=m_3/prime; 179 } 180 while((m_4%prime)==0) { 181 m_4=m_4/prime; 182 } 183 if(D==-3) 184 { 185 while((m_5%prime)==0) { 186 m_5=m_5/prime; 187 } 188 while((m_6%prime)==0) { 189 m_6=m_6/prime; 190 } 191 } 192 } 193 } 194 in.clear(); 195 in.close(); 196 if(!in.good()) { 197 std::string msg("Error while closing file "); 198 msg += in_file; 199 lidia_error_handler("prime_proof::is_good_order()", 200 msg.c_str()); 201 } 202 203 if(!m_minus_t.is_prime()) { 204 m_minus_t = pollard_rho(m_minus_t); 205 } 206 if(!m_plus_t.is_prime()) { 207 m_plus_t = pollard_rho(m_plus_t); 208 } 209 if(D==-4 || D==-3) 210 { 211 if(!m_3.is_prime()) { 212 m_3 = pollard_rho(m_3); 213 } 214 if(!m_4.is_prime()) { 215 m_4 = pollard_rho(m_4); 216 } 217 if(D==-3) 218 { 219 if(!m_5.is_prime()) { 220 m_5 = pollard_rho(m_5); 221 } 222 if(!m_6.is_prime()) { 223 m_6 = pollard_rho(m_6); 224 } 225 } 226 } 227 if(m_plus_t.is_prime() && m_plus_t > s) 228 { 229 order = n + 1 + t; 230 prime_factor = m_plus_t; 231 if(order!=prime_factor && prove_downstep(prime_factor)) 232 { 233 return prove_n_with_curve(); 234 } 235 236 237 } 238 if(m_minus_t.is_prime() && m_minus_t > s) 239 { 240 order = n + 1 - t; 241 prime_factor = m_minus_t; 242 if(order!=prime_factor && prove_downstep(prime_factor)) 243 { 244 return prove_n_with_curve(); 245 } 246 } 247 if(D==-3) 248 { 249 if(m_3.is_prime() && m_3 > s) 250 { 251 order = n + 1 + t + 3*y; 252 prime_factor = m_3; 253 if(order!=prime_factor && prove_downstep(prime_factor)) 254 { 255 return prove_n_with_curve(); 256 } 257 } 258 if(m_4.is_prime() && m_4 > s) 259 { 260 order = n + 1 -t -3*y; 261 prime_factor = m_4; 262 if(order!=prime_factor && prove_downstep(prime_factor)) 263 { 264 return prove_n_with_curve(); 265 } 266 } 267 if(m_5.is_prime() && m_5 > s) 268 { 269 order = n + 1 + t - 3*y; 270 prime_factor = m_5; 271 if(order!=prime_factor && prove_downstep(prime_factor)) 272 { 273 return prove_n_with_curve(); 274 } 275 } 276 if(m_6.is_prime() && m_6 > s) 277 { 278 order = n + 1 -t + 3*y; 279 prime_factor = m_6; 280 if(order!=prime_factor && prove_downstep(prime_factor)) 281 { 282 return prove_n_with_curve(); 283 } 284 } 285 } 286 if(D==-4) 287 { 288 if(m_3.is_prime() && m_3 > s) 289 { 290 order = n + 1 + 2*y; 291 prime_factor = m_3; 292 if(order!=prime_factor && prove_downstep(prime_factor)) 293 { 294 return prove_n_with_curve(); 295 } 296 } 297 if(m_4.is_prime() && m_4 > s) 298 { 299 order = n + 1 - 2*y; 300 prime_factor = m_4; 301 if(order!=prime_factor && prove_downstep(prime_factor)) 302 { 303 return prove_n_with_curve(); 304 } 305 } 306 } 307 return false; 308 } 309 return false; 310 } 311 pollard_rho(bigint & t)312 bigint prime_proof::pollard_rho(bigint & t) 313 { 314 single_factor <bigint> prime_compo; 315 int expo = 0; 316 int no_prime_compo = 0; 317 int ii = 0; 318 int i = 0; 319 int l = t.decimal_length(); 320 l=l/2; 321 if(l>9) { 322 l=16; 323 } 324 factorization <bigint> f; 325 f = PollardRho(t,9); 326 no_prime_compo = f.no_of_prime_components(); 327 while(no_prime_compo > i) 328 { 329 expo=f.prime_exponent(i); 330 prime_compo = f.prime_base(i); 331 prime_factor = prime_compo.base(); 332 while( expo > ii ) 333 { 334 t = t / prime_factor; 335 ii++; 336 } 337 ii=0; 338 i++; 339 } 340 return t; 341 } 342 343 #ifdef LIDIA_NAMESPACE 344 } // end of namespace LiDIA 345 # undef IN_NAMESPACE_LIDIA 346 #endif 347