{VERSION 5 0 "SGI MIPS UNIX" "5.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 23 "Courier" 1 10 0 0 0 0 0 0 0 0 0 0 3 0 0 1 }{CSTYLE " " -1 256 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 "Courie r" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 261 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 262 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 263 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 264 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 265 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 266 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 267 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 268 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 269 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 270 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 271 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 272 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 273 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 274 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 275 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 276 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 277 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 278 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 279 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 280 "" 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 281 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 282 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 283 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 284 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 285 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 286 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 287 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 288 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 289 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 290 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 291 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 292 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 293 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 294 "" 0 14 0 0 255 1 1 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 295 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 296 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 297 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 298 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 299 "" 0 1 0 0 255 1 1 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 300 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 301 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 302 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 303 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 304 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 305 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 306 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 307 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 308 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 309 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 310 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 311 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 312 "Courier" 1 10 0 0 0 0 1 0 0 0 0 0 3 0 0 1 }{CSTYLE "" -1 313 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 314 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 315 "" 1 24 0 0 255 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 316 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 317 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 318 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 319 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 320 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 321 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 322 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 323 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 324 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 325 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 326 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 327 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 328 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 329 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 330 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 331 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 332 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 333 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 334 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 335 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 336 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 337 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 338 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 339 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 340 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 341 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 342 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 343 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 344 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 345 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 346 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 347 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 348 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 349 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 350 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 351 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 352 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 353 "" 0 1 0 0 255 1 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 354 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 355 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 356 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 357 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 358 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 359 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 360 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 361 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 362 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 363 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 364 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 365 "Courier" 0 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 366 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 367 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 368 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 369 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 370 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 371 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 372 "" 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 373 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 374 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 375 "" 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 376 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 377 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 378 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 379 "" 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 380 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 381 "" 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 382 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 383 "" 0 1 128 0 0 1 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 384 "" 0 1 128 0 0 1 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 385 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 407 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 408 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 409 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 410 "" 1 14 0 128 0 1 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 411 "" 1 14 0 128 0 1 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 412 "" 1 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 413 "" 1 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 414 "" 1 14 0 128 0 1 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 415 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 416 "Times New Roman CE" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 417 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 418 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 419 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 420 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 421 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 422 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 423 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 424 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 425 "" 0 1 0 0 255 1 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 440 "Courier" 1 10 0 128 0 1 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 441 "Times New Roman CE" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 442 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 443 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 444 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" 18 445 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 446 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" 18 447 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 448 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" 18 449 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 450 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" 18 451 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 452 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" 18 453 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 454 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" 18 455 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 456 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" 18 457 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 458 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 459 "" 0 1 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 460 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 461 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 462 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 463 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 464 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 465 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 466 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 467 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 468 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 469 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 470 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 471 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 472 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 473 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 474 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 475 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 476 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 477 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 478 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 479 "" 0 1 255 0 255 1 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 480 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 481 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 482 "" 0 12 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 483 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 484 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 485 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 486 "" 1 10 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 487 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 488 "" 1 10 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 489 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 490 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 492 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 493 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 494 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 495 "" 1 14 0 128 0 1 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 496 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 497 "Times New Roman CE" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" 18 498 "" 0 1 255 0 0 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" 18 499 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" 18 500 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" 20 501 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" 18 502 "" 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 503 "" 0 1 255 0 0 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" 18 504 "" 0 1 255 0 0 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 505 "" 0 1 255 0 0 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" 18 506 "" 0 1 255 0 0 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 507 "" 0 1 255 0 0 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 508 "" 1 14 128 0 0 1 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 509 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 510 "" 0 1 128 0 0 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE " " 18 511 "" 0 1 255 0 0 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 512 "" 0 1 255 0 0 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" 18 513 "" 0 1 255 0 0 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 514 "" 0 1 255 0 0 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" 18 515 "" 0 1 255 0 0 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE " " -1 516 "" 0 1 255 0 0 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" 18 517 "" 0 1 255 0 0 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 518 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 519 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" 18 520 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE " " -1 521 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" 18 522 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 523 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 524 "" 0 1 0 0 255 1 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 525 "" 0 1 0 0 255 1 0 1 0 0 0 0 0 0 0 0 }{CSTYLE " " -1 526 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 527 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 528 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 529 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 530 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 531 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 532 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 533 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 534 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 535 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 536 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 537 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 538 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 539 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 540 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 541 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 542 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 543 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 544 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 545 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 546 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 547 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 548 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 549 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 550 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 551 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 552 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 553 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 554 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 555 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 556 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 557 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 558 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 559 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 560 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 561 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 562 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 563 "" 0 1 255 0 0 1 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 564 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 565 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 566 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 567 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 568 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 569 "" 1 10 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 570 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 571 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 572 "" 0 1 0 128 0 1 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 573 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 574 "" 1 10 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 575 "" 1 10 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 576 "" 1 10 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 577 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 578 "" 1 10 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 579 "" 1 10 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 580 "" 1 10 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 581 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 582 "" 1 10 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 583 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 584 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 585 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 586 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 587 "" 1 10 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 588 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 589 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 590 "" 1 10 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 591 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 592 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 593 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 594 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 595 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 596 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 597 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 598 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 599 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 600 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 601 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 602 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 603 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 604 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 605 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 606 "" 0 1 0 128 0 1 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 607 "" 0 1 0 128 0 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 608 "" 0 1 0 128 0 1 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 609 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 610 "" 0 1 0 128 0 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 611 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 612 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "T imes" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 } {PSTYLE "Heading 1" -1 3 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8 4 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 2" -1 4 1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8 2 1 0 1 0 2 2 0 1 }{PSTYLE "Text Output" -1 6 1 {CSTYLE "" -1 -1 " Courier" 1 10 0 0 255 1 2 2 2 2 2 1 2 1 3 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Warning" -1 7 1 {CSTYLE "" -1 -1 "Courier" 1 10 0 0 255 1 2 2 2 2 2 1 1 1 3 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Maple Out put" -1 11 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 3 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Maple Output" -1 12 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 3 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Author" -1 19 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 1 0 0 8 8 1 0 1 0 2 2 0 1 } {PSTYLE "Heading 1" -1 256 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }3 1 0 0 8 4 1 0 1 0 2 2 0 1 }{PSTYLE "Normal" -1 257 1 {CSTYLE "" -1 -1 "Helonia" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Normal" -1 258 1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }} {SECT 0 {EXCHG {PARA 256 "" 0 "" {TEXT -1 1 "\n" }}{PARA 256 "" 0 "" {TEXT 443 16 "Polynomial GCD C" }{TEXT 315 0 "" }{TEXT 444 20 "omputat ion: \nFrom Z[" }{XPPEDIT 445 0 "x[1];" "6#&%\"xG6#\"\"\"" }{TEXT 446 7 ", ..., " }{XPPEDIT 447 0 "x[n];" "6#&%\"xG6#%\"nG" }{TEXT 448 7 "] \+ to Q(" }{XPPEDIT 449 0 "alpha;" "6#%&alphaG" }{TEXT 450 1 "(" } {XPPEDIT 451 0 "t[1];" "6#&%\"tG6#\"\"\"" }{TEXT 452 7 ", ..., " } {XPPEDIT 453 0 "t[k];" "6#&%\"tG6#%\"kG" }{TEXT 454 3 "))[" }{XPPEDIT 455 0 "x[1];" "6#&%\"xG6#\"\"\"" }{TEXT 456 7 ", ..., " }{XPPEDIT 457 0 "x[n];" "6#&%\"xG6#%\"nG" }{TEXT 458 2 "]." }{TEXT 459 1 " " }}} {EXCHG {PARA 19 "" 0 "" {TEXT -1 1 "\n" }{TEXT 416 16 "Michael Monagan " }}{PARA 19 "" 0 "" {TEXT 441 77 "Centre for Experimental & Construc tive Mathematics \nSimon Fraser University.\n" }{TEXT 497 38 "MOCAA, M ay 6, Waterloo, Ontario, 2004." }{TEXT -1 41 "\n\nJoint work with Mark van Hoeij (FSU).\n\n" }{TEXT 440 46 "Preprint: http://www.cecm.sfu.ca /CAG/preprints" }{TEXT -1 1 "\n" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 11 "An example." }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 9 "Let D = " } {TEXT 415 1 "Z" }{TEXT -1 1 "[" }{XPPEDIT 18 0 "t[1],`...`,t[k];" "6%& %\"tG6#\"\"\"%$...G&F$6#%\"kG" }{TEXT -1 10 "], F = Q(" }{XPPEDIT 18 0 "t[1],`...`,t[k];" "6%&%\"tG6#\"\"\"%$...G&F$6#%\"kG" }{TEXT -1 3 ") , " }{XPPEDIT 18 0 "alpha;" "6#%&alphaG" }{TEXT -1 23 " algebraic over F.\nLet " }{TEXT 318 2 " m" }{TEXT -1 6 " in F[" }{TEXT 317 1 "z" } {TEXT -1 30 "] the minimal polynomial for " }{XPPEDIT 18 0 "alpha;" " 6#%&alphaG" }{TEXT -1 12 " and L = F[" }{TEXT 319 1 "z" }{TEXT -1 3 " ]/(" }{TEXT 320 1 "m" }{TEXT -1 10 ").\nSo if " }{XPPEDIT 18 0 "k = 0 ;" "6#/%\"kG\"\"!" }{TEXT -1 44 " then L is a number field.\nGiven no n-zero " }{XPPEDIT 18 0 "f[1];" "6#&%\"fG6#\"\"\"" }{TEXT -1 2 ", " } {XPPEDIT 18 0 "f[2];" "6#&%\"fG6#\"\"#" }{TEXT -1 7 " in L[" }{TEXT 322 1 "x" }{TEXT -1 21 "] compute their gcd " }{TEXT 321 1 "g" } {TEXT -1 2 " ." }}}{EXCHG {PARA 0 "" 0 "" {TEXT 460 7 "Example" } {TEXT -1 8 ": F = Q(" }{TEXT 323 3 "s,t" }{TEXT -1 3 "), " }{XPPEDIT 18 0 "alpha = ``^3*sqrt(`(2 t + 1) / s`);" "6#/%&alphaG*&%!G\"\"$-%%sq rtG6#%.(2~t~+~1)~/~sG\"\"\"" }{TEXT -1 2 " ." }}}{EXCHG {PARA 11 "" 1 "" {XPPMATH 20 "6#/-%\"mG6#%\"zG,(*&%\"sG\"\"\")F'\"\"$F+F+*&\"\"#F+% \"tGF+!\"\"F+F1" }}}{EXCHG {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"eG,,*&% \"tG\"\"\"%\"xGF(F(*&)%&alphaG\"\"#F(%\"sGF(!\"\"*(\"\"&F(F'F(F,F(F(*& \"\"'F(F.F(F/F-F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fG,,%\"xG\"\" $*&%&alphaG\"\"\"F&F*F**(F'F*%\"sGF*%\"tGF*!\"\"*(\"\"(F*F)F*)F,\"\"#F *F*F0F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"hG,.%\"xG\"\"&*&%\"tG\" \"\"%&alphaGF*!\"\"*&%\"sGF*F)F,F*F.F**&\"#6F*F)F*F*F+F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 138 "st := time():\ng := collect(evala( Expand(e^2)),x);\nf1 := collect(evala(Expand(f^2*g)),x):\nf2 := collec t(evala(Expand(h^2*g)),x):\ntime()-st;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"gG,<*&)%\"tG\"\"#\"\"\")%\"xGF)F*F**&,**(F(F*)%&alphaGF)F*% \"sGF*!\"#*(\"#7F*F2F*F(F*!\"\"*&\"\"%F*F(F*F**(\"#5F*F'F*F1F*F*F*F,F* F*F8F**&\"#CF*F2F*F6*&\"#OF*)F2F)F*F***\"#eF*F(F*F1F*F2F*F6*&\"#?F*F'F *F6*&F:F*F(F*F6*&F2F*F1F*F**(F8F*F0F*F2F*F6*(FCF*F(F*F1F*F**(F5F*F0F*F ?F*F**(\"#DF*F'F*F0F*F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"#!)!\"$ " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 70 "st := time():\nevala( D ivide(f1,g) );\nevala( Divide(f2,g) );\ntime()-st;" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#%%trueG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"$+#!\"$" }}}{EXCHG {PARA 0 "" 0 " " {TEXT 411 34 "Maple's subresultant PRS algorithm" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "st := time():\nevala( Gcd(f1,f2) );" }} {PARA 7 "" 1 "" {TEXT -1 33 "Warning, computation interrupted\n" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "time()-st;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"&3l*!\"$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 410 38 "A primititive fraction free algorithm." }{TEXT -1 42 "\nBased on idea s of Moreno Maza and Rioboo." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 55 "I nstead of computing the monic remainder sequence in F[" }{TEXT 461 1 " z" }{TEXT -1 2 "][" }{TEXT 462 1 "x" }{TEXT -1 15 "] compute in D[" } {TEXT 463 1 "z" }{TEXT -1 2 "][" }{TEXT 464 1 "x" }{TEXT -1 86 "] usin g pseudo-division and make pseudo-remainders primitive. Instead of mu ltiplying " }{XPPEDIT 18 0 "r[i];" "6#&%\"rG6#%\"iG" }{TEXT -1 4 " by \+ " }{XPPEDIT 18 0 "u = lc(r[i])^(-1*1);" "6#/%\"uG)-%#lcG6#&%\"rG6#%\"i G,$*&\"\"\"F/F/F/!\"\"" }{TEXT -1 31 " to make it monic, multiply by \+ " }{XPPEDIT 18 0 "numer(u);" "6#-%&numerG6#%\"uG" }{TEXT -1 23 ", a qu asi-inverse in D[" }{TEXT 465 1 "z" }{TEXT -1 32 "] and make the resul t primitive." }}}{SECT 1 {PARA 4 "" 0 "" {TEXT 412 35 "quasi Inverse u sing the reduced PRS" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 345 "qua siInverse := proc(m,u,z)\nlocal r0,r1,t0,t1,mu,q,g,beta;\nr0,r1 := m,u ;\nt0,t1 := 0,1;\nbeta := 1;\nwhile degree(r1,z)>0 do\n r0,r1 := r1, prem(r0,r1,z,'mu','q');\n t0,t1 := t1,expand(mu*t0-q*t1);\n if r1= 0 then ERROR(\"zero divisor\",r0) fi;\n divide(r1,beta,'r1');\n di vide(t1,beta,'t1');\n beta := mu;\nod;\ndivide(t1,gcd(r1,t1),'t1');t 1;\nend:" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT 413 33 "primitive fraction free algorithm" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 480 "PFFGCD : = proc(f1,f2,x,m,z)\nlocal r1,r2,qi,r3;\nr1 := primpart(f1,[x,z]);\nr2 := primpart(f2,[x,z]);\nwhile r2 <> 0 do\n lprint(PR,seq(v=degre e(r2,v),v=[x,z,s,t]),\n HEIGHT=length(maxnorm(r2)));\n qi \+ := quasiInverse(m,lcoeff(r2,x),z);\n lprint(QI,seq(v=degree(qi,v) ,v=[s,t]),\n HEIGHT=length(maxnorm(qi)));\n r2 := primpart ( prem(qi*r2,m,z), [x,z] );\n r3 := prem( prem(r1,r2,x), m, z );\n \+ r3 := primpart( r3, [x,z] );\n r1,r2 := r2,r3;\nod:\nr1;\nend:" }}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 78 "st := time():\nPFFGCD(su bs(alpha=z,f1),subs(alpha=z,f2),x,m,z);\ntime=time()-st;" }}{PARA 6 " " 1 "" {TEXT -1 42 "PR, x = 4, z = 2, s = 5, t = 7, HEIGHT = 4" }} {PARA 6 "" 1 "" {TEXT -1 28 "QI, s = 0, t = 0, HEIGHT = 1" }}{PARA 6 " " 1 "" {TEXT -1 42 "PR, x = 3, z = 2, s = 8, t = 8, HEIGHT = 6" }} {PARA 6 "" 1 "" {TEXT -1 28 "QI, s = 6, t = 6, HEIGHT = 5" }}{PARA 6 " " 1 "" {TEXT -1 42 "PR, x = 2, z = 2, s = 9, t = 9, HEIGHT = 8" }} {PARA 6 "" 1 "" {TEXT -1 30 "QI, s = 10, t = 11, HEIGHT = 8" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,B*$)%\"sG\"\"#\"\"\"\"#O*&\"#CF(F&F(!\"\"*& \"#?F()%\"tGF'F(F,*&\"#5F(F0F(F,\"\"%F(*&F/F()%\"xGF'F(F(**F2F(F/F(%\" zGF(F6F(F(*(\"#7F()F8F'F(F%F(F(*(F3F(F;F(F&F(F,*(\"#DF(F/F(F;F(F(*,F'F (F6F(F0F(F;F(F&F(F,**\"#eF(F0F(F8F(F&F(F,*&F&F(F8F(F(*(F.F(F0F(F8F(F(* *F:F(F6F(F&F(F0F(F,*(F3F(F0F(F6F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #/%%timeG$\"%EP!\"$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 414 21 "Our modul ar algorithm" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 70 "currentdir( \"c:/documents and settings/administrator/desktop/monagan\");" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "read AFGCD;" }}{PARA 6 "" 1 "" {TEXT -1 13 "\"loading ...\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 59 "st := time(): \nalgfungcd(f1,f2,x,A,[s,t]); \ntime=time()-st; " }}{PARA 6 "" 1 "" {TEXT -1 19 "MGCD: prime = 46327" }}{PARA 6 "" 1 " " {TEXT -1 18 "MGCD: LM = t^2*x^2" }}{PARA 6 "" 1 "" {TEXT -1 37 "MGCD : Rational reconstruction failed." }}{PARA 6 "" 1 "" {TEXT -1 19 "MGCD : prime = 46309" }}{PARA 6 "" 1 "" {TEXT -1 18 "MGCD: LM = t^2*x^2" }} {PARA 6 "" 1 "" {TEXT -1 45 "MGCD: CRT trial divisions starting over Z ..." }}{PARA 12 "" 1 "" {TEXT -1 0 "" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,B*$)%\"tG\"\"#\"\"\"!#?*&\"#5F(F&F(!\"\"\"\"%F(*&F%F()%\"xGF'F(F(* *\"#7F(F0F(%\"sGF(F&F(F,*(F2F()%&alphaGF'F()F3F'F(F(**F+F(F%F(F0F(F6F( F(*&\"#OF(F7F(F(*(\"#?F(F&F(F6F(F(*&\"#CF(F3F(F,*(F-F(F&F(F0F(F(*(F-F( F5F(F3F(F,**\"#eF(F&F(F6F(F3F(F,*&F3F(F6F(F(*,F'F(F0F(F&F(F5F(F3F(F,*( \"#DF(F%F(F5F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%%timeG$\"%\"3\"! \"$" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 26 "The modular GCD algorith m." }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 261 1 "Z" }{TEXT -1 1 "[" }{XPPEDIT 18 0 "x[1],`...`,x[n]; " "6%&%\"xG6#\"\"\"%$...G&F$6#%\"nG" }{TEXT -1 17 "] Brown (1971)" }}{PARA 0 "" 0 "" {TEXT -1 1 "\n" }{TEXT 263 1 "Z" }{TEXT -1 1 "[" } {XPPEDIT 18 0 "alpha;" "6#%&alphaG" }{TEXT -1 2 "][" }{TEXT 262 1 "x" }{TEXT -1 34 "] Langemyr & MacCallum (1976)\n\n" }{TEXT 266 1 "Z" } {TEXT -1 1 "[" }{XPPEDIT 18 0 "alpha[1];" "6#&%&alphaG6#\"\"\"" } {TEXT -1 7 ", ..., " }{XPPEDIT 18 0 "alpha[n];" "6#&%&alphaG6#%\"nG" } {TEXT -1 3 " ][" }{TEXT 265 1 "x" }{TEXT -1 25 "] Langemyr (1979) \n\nQ(" }{XPPEDIT 18 0 "alpha;" "6#%&alphaG" }{TEXT -1 2 ")[" } {XPPEDIT 18 0 "x[1],`...`,x[n];" "6%&%\"xG6#\"\"\"%$...G&F$6#%\"nG" } {TEXT -1 41 "] Geddes, Gonnet & Smedley (1987)\n\nQ(" }{XPPEDIT 18 0 "alpha;" "6#%&alphaG" }{TEXT -1 2 ")[" }{TEXT 316 1 "x" }{TEXT -1 28 "] Encarnacion (1994)\n\nQ(" }{XPPEDIT 18 0 "alpha[1];" "6#& %&alphaG6#\"\"\"" }{TEXT -1 7 ", ..., " }{XPPEDIT 18 0 "alpha[n];" "6# &%&alphaG6#%\"nG" }{TEXT -1 2 ")[" }{TEXT 264 1 "x" }{TEXT -1 36 "] \+ van Hoeij & Monagan (2002)\n\nQ(" }{XPPEDIT 18 0 "alpha;" "6#%&alpha G" }{TEXT -1 1 "(" }{XPPEDIT 18 0 "t[1];" "6#&%\"tG6#\"\"\"" }{TEXT -1 7 ", ..., " }{XPPEDIT 18 0 "t[k];" "6#&%\"tG6#%\"kG" }{TEXT -1 3 ") )[" }{XPPEDIT 18 0 "x[1];" "6#&%\"xG6#\"\"\"" }{TEXT -1 7 ", ..., " } {XPPEDIT 18 0 "x[n];" "6#&%\"xG6#%\"nG" }{TEXT -1 33 "] van Hoeij \+ & Monagan (2004)\n" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 24 "Brown's a lgorithm for Z[" }{TEXT 313 1 "x" }{TEXT -1 1 "]" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 7 "Let " }{XPPEDIT 18 0 "f[1];" "6#&%\"fG6#\"\"\"" }{TEXT -1 3 " = " }{XPPEDIT 500 0 "a[m ]*x^m;" "6#*&&%\"aG6#%\"mG\"\"\")%\"xGF'F(" }{TEXT -1 9 " + ... + " } {XPPEDIT 18 0 "a[0];" "6#&%\"aG6#\"\"!" }{TEXT -1 16 " where gcd( " }{XPPEDIT 18 0 "a[m];" "6#&%\"aG6#%\"mG" }{TEXT -1 7 ", ..., " } {XPPEDIT 18 0 "a[0];" "6#&%\"aG6#\"\"!" }{TEXT -1 12 ") = 1\nand " } {XPPEDIT 18 0 "f[2];" "6#&%\"fG6#\"\"#" }{TEXT -1 3 " = " }{XPPEDIT 499 0 "b[n]*x^n;" "6#*&&%\"bG6#%\"nG\"\"\")%\"xGF'F(" }{TEXT -1 9 " + \+ ... + " }{XPPEDIT 18 0 "b[0];" "6#&%\"bG6#\"\"!" }{TEXT -1 15 " wher e gcd(" }{XPPEDIT 18 0 "b[m];" "6#&%\"bG6#%\"mG" }{TEXT -1 7 ", ..., " }{XPPEDIT 18 0 "b[0];" "6#&%\"bG6#\"\"!" }{TEXT -1 14 ") = 1.\nLet \+ " }{XPPEDIT 18 0 "g;" "6#%\"gG" }{TEXT -1 9 " = gcd(" }{XPPEDIT 18 0 "f[1],f[2];" "6$&%\"fG6#\"\"\"&F$6#\"\"#" }{TEXT -1 6 ") = " } {XPPEDIT 498 0 "c[l]*x^l;" "6#*&&%\"cG6#%\"lG\"\"\")%\"xGF'F(" }{TEXT -1 9 " + ... + " }{XPPEDIT 18 0 "c[0];" "6#&%\"cG6#\"\"!" }{TEXT -1 8 " .\n\nLet " }{XPPEDIT 18 0 "gamma;" "6#%&gammaG" }{TEXT -1 29 " be an y non-zero multiple of " }{XPPEDIT 18 0 "c[l];" "6#&%\"cG6#%\"lG" } {TEXT -1 10 ". Can use" }{TEXT 329 1 " " }{TEXT -1 0 "" }{XPPEDIT 18 0 "gamma = a[m];" "6#/%&gammaG&%\"aG6#%\"mG" }{TEXT -1 6 " or " } {XPPEDIT 18 0 "gamma = b[n];" "6#/%&gammaG&%\"bG6#%\"nG" }{TEXT -1 11 " best is " }{XPPEDIT 18 0 "gamma = gcd(a[m],b[n]);" "6#/%&gammaG-%$ gcdG6$&%\"aG6#%\"mG&%\"bG6#%\"nG" }{TEXT -1 7 ".\n\nLet " }{TEXT 330 1 "p" }{TEXT -1 16 " be a prime and " }{TEXT 338 1 "e" }{TEXT -1 3 " = " }{XPPEDIT 18 0 "gcd(`mod`(f[1],p),`mod`(f[2],p));" "6#-%$gcdG6$-%$m odG6$&%\"fG6#\"\"\"%\"pG-F'6$&F*6#\"\"#F-" }{TEXT -1 1 "." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 1 "\n" }{TEXT 335 11 "Definition:" }{TEXT -1 9 " A prime " }{TEXT 279 1 "p" }{TEXT -1 4 " is " }{TEXT 280 4 "good" }{TEXT -1 5 " if " }{TEXT 278 1 "e" }{TEXT -1 3 " ~ " }{TEXT 276 1 "g " }{TEXT -1 5 " mod " }{TEXT 277 1 "p" }{TEXT -1 4 " .\n\n" }{TEXT 336 11 "Definition:" }{TEXT -1 9 " A prime " }{TEXT 268 1 "p" }{TEXT -1 4 " is " }{TEXT 269 6 "lc-bad" }{TEXT -1 4 " if " }{XPPEDIT 18 0 "p ;" "6#%\"pG" }{TEXT -1 3 " | " }{XPPEDIT 18 0 "c[l];" "6#&%\"cG6#%\"lG " }{TEXT -1 12 " . \n If " }{TEXT 267 1 "p" }{TEXT -1 17 " does no t divide " }{XPPEDIT 18 0 "gamma;" "6#%&gammaG" }{TEXT -1 25 " then it is not lc-bad.\n\n" }{TEXT 337 11 "Definition:" }{TEXT -1 12 " A prim e is " }{TEXT 270 7 "unlucky" }{TEXT -1 8 " if deg(" }{TEXT 339 1 "e" }{TEXT -1 8 ") > deg(" }{TEXT 340 1 "g" }{TEXT -1 17 ").\n E.g. take " }{XPPEDIT 18 0 "f[1] = (x+1)*x;" "6#/&%\"fG6#\"\"\"*&,&%\"xGF'F'F' F'F*F'" }{TEXT -1 3 ", " }{XPPEDIT 18 0 "f[2] = (x+1)*(x+5);" "6#/&% \"fG6#\"\"#*&,&%\"xG\"\"\"F+F+F+,&F*F+\"\"&F+F+" }{TEXT -1 9 " . Then " }{XPPEDIT 18 0 "g = x+1;" "6#/%\"gG,&%\"xG\"\"\"F'F'" }{TEXT -1 5 " and " }{XPPEDIT 18 0 "p = 5;" "6#/%\"pG\"\"&" }{TEXT -1 13 " is unluc ky.\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 1 "\n" }{TEXT 331 6 "Lemma: " }{TEXT -1 4 " if " }{TEXT 271 1 "p" }{TEXT -1 49 " is not lc-bad the n it's either unlucky or good.\n" }{TEXT 332 6 "Lemma:" }{TEXT -1 97 " the number of unlucky and lc-bad primes is finite.\n\nGood primes are not good enough !\nConsider " }{XPPEDIT 18 0 "f[1] = 5*x+3;" "6#/&% \"fG6#\"\"\",&*&\"\"&F'%\"xGF'F'\"\"$F'" }{TEXT -1 3 ", " }{XPPEDIT 18 0 "f[2] = 5*x+3;" "6#/&%\"fG6#\"\"#,&*&\"\"&\"\"\"%\"xGF+F+\"\"$F+ " }{TEXT -1 6 ". So " }{TEXT 417 1 "g" }{TEXT -1 5 " = 5 " }{TEXT 328 1 "x" }{TEXT -1 10 " + 3.\n " }{TEXT 272 1 "p" }{TEXT -1 17 " = 5 is good but " }{TEXT 341 1 "e" }{TEXT -1 16 " = 1 not 3.\n " } {TEXT 273 1 "p" }{TEXT -1 17 " = 7 is good but " }{TEXT 342 1 "e" } {TEXT -1 3 " = " }{TEXT 418 1 "x" }{TEXT -1 7 " + 2.\n\n" }{TEXT 333 6 "Lemma:" }{TEXT -1 4 " if " }{TEXT 281 1 "p" }{TEXT -1 40 " is not l c-bad and not unlucky then\n " }{XPPEDIT 18 0 "gamma;" "6#%&gammaG " }{TEXT -1 2 " (" }{TEXT 343 1 "e" }{TEXT -1 6 " / lc(" }{TEXT 344 1 "e" }{TEXT -1 12 ")) mod p = (" }{XPPEDIT 18 0 "gamma;" "6#%&gammaG" } {TEXT -1 6 " / lc(" }{TEXT 275 1 "g" }{TEXT -1 3 ")) " }{TEXT 345 1 "g " }{TEXT -1 5 " mod " }{TEXT 274 3 "p\n\n" }{TEXT 334 10 "Algorithm:" }{TEXT -1 60 " \n Choose primes which are not lc-bad,\n Keep only \+ those " }{TEXT 419 1 "e" }{TEXT -1 36 " of least degree, \n Reconstr uct (" }{XPPEDIT 18 0 "gamma;" "6#%&gammaG" }{TEXT -1 6 " / lc(" } {TEXT 282 1 "g" }{TEXT -1 3 ")) " }{TEXT 284 1 "g" }{TEXT -1 6 " from \+ " }{XPPEDIT 18 0 "gamma;" "6#%&gammaG" }{TEXT -1 2 " (" }{TEXT 346 1 " e" }{TEXT -1 6 " / lc(" }{TEXT 347 1 "e" }{TEXT -1 7 ")) mod " }{TEXT 283 3 "p.\n" }{TEXT -1 41 " Brown also reconstructs the cofactors " }{XPPEDIT 18 0 "f[1];" "6#&%\"fG6#\"\"\"" }{TEXT -1 2 "/ " }{TEXT 289 1 "g" }{TEXT -1 5 " and " }{XPPEDIT 18 0 "f[2];" "6#&%\"fG6#\"\"#" } {TEXT -1 3 " / " }{TEXT 288 1 "g" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 1 "\n" }{TEXT 348 11 "Complexity:" }{TEXT -1 46 " # primes is based on bounds on the height of " }{TEXT 285 2 "g " }{TEXT -1 4 "and " }{XPPEDIT 18 0 "f[1];" "6#&%\"fG6#\"\"\"" }{TEXT -1 2 "/ " }{TEXT 287 1 "g" }{TEXT -1 5 " and " }{XPPEDIT 18 0 "f[2];" "6#&%\"fG6#\"\"# " }{TEXT -1 3 " / " }{TEXT 286 1 "g" }{TEXT -1 1 "." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 22 " ^g, monic(g) and ~ g." }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 11 "Recall D = " }{TEXT 324 1 "Z" }{TEXT -1 1 "[" }{XPPEDIT 18 0 "t[1],`...`,t[k];" "6%&%\"tG6 #\"\"\"%$...G&F$6#%\"kG" }{TEXT -1 9 "], F = Q(" }{XPPEDIT 18 0 "t[1], `...`,t[k];" "6%&%\"tG6#\"\"\"%$...G&F$6#%\"kG" }{TEXT -1 3 "), " } {XPPEDIT 18 0 "alpha;" "6#%&alphaG" }{TEXT -1 21 " algebraic over F, \+ \n" }{TEXT 292 1 "m" }{TEXT -1 30 " is the minimal polynomial of " } {XPPEDIT 18 0 "alpha;" "6#%&alphaG" }{TEXT -1 6 " in F[" }{TEXT 291 1 "z" }{TEXT -1 13 "], and L = F[" }{TEXT 349 1 "z" }{TEXT -1 3 "]/(" } {TEXT 350 1 "m" }{TEXT -1 30 ").\n \nLet g be non-zero in L[" } {TEXT 293 1 "x" }{TEXT -1 10 "].\nDefine " }{TEXT 294 2 "^g" }{TEXT -1 3 " = " }{TEXT 295 3 "s g" }{TEXT -1 7 " where " }{TEXT 296 1 "s" } {TEXT -1 30 " is the scalar in F such that " }{TEXT 297 3 "^ g" } {TEXT -1 20 " is primitive in D[" }{TEXT 298 3 "z,x" }{TEXT -1 10 "]. \nDefine " }{TEXT 524 6 "monic(" }{TEXT 353 1 "g" }{TEXT 525 1 ")" } {TEXT -1 3 " = " }{TEXT 351 1 "g" }{TEXT -1 7 " / lc( " }{TEXT 352 1 " g" }{TEXT -1 11 " )\nDefine " }{TEXT 299 2 "~g" }{TEXT -1 12 " = ^ mo nic( " }{TEXT 354 1 "g" }{TEXT -1 4 " ).\n" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 34 "g := 6*sqrt(3)*x-2*sqrt(3)/5+4/15;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,(*&-%%sqrtG6#\"\"$\"\"\"%\"xGF+\"\"'*&#\"\" #\"\"&F+*$F'F+F+!\"\"#\"\"%\"#:F+" }}}{EXCHG {PARA 11 "" 1 "" {XPPMATH 20 "6#/%#^gG,(*&-%%sqrtG6#\"\"$\"\"\"%\"xGF+\"#X*&F*F+F'F+!\" \"\"\"#F+" }}}{EXCHG {PARA 11 "" 1 "" {XPPMATH 20 "6#>-%&monicG6#%\"gG ,(%\"xG\"\"\"#F*\"#:!\"\"*&#\"\"#\"$N\"F*-%%sqrtG6#\"\"$F*F*" }}} {EXCHG {PARA 11 "" 1 "" {XPPMATH 501 "6#>%#|irgG,(%\"xG\"$N\"\"\"*!\" \"*&\"\"#\"\"\"-%%sqrtG6#\"\"$F,F," }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 35 "Langemyr and MacCallum's algorithm." }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 5 "\nLet " }{XPPEDIT 18 0 "alpha;" "6#%&alphaG" }{TEXT -1 7 " be an " }{TEXT 300 17 "algebraic integer" }{TEXT -1 25 " with mimimal polynomial " }{TEXT 355 1 "m" }{TEXT -1 12 ".\nLet L = Q(" }{XPPEDIT 18 0 "alpha;" "6#%&alphaG" }{TEXT -1 6 ") and " }{XPPEDIT 18 0 "f[1]; " "6#&%\"fG6#\"\"\"" }{TEXT -1 5 " and " }{XPPEDIT 18 0 "f[2];" "6#&% \"fG6#\"\"#" }{TEXT -1 18 " be non-zero in L[" }{TEXT 290 1 "x" } {TEXT -1 6 "] and " }{TEXT 301 1 "g" }{TEXT -1 10 " be their " }{TEXT 356 5 "monic" }{TEXT -1 37 " gcd.\nLangemyr's algorithm computes ~" } {XPPEDIT 18 0 "f[1];" "6#&%\"fG6#\"\"\"" }{TEXT -1 6 " and ~" } {XPPEDIT 18 0 "f[2];" "6#&%\"fG6#\"\"#" }{TEXT -1 14 " and outputs ~" }{XPPEDIT 18 0 "g;" "6#%\"gG" }{TEXT -1 2 " ." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 11 "\nConsider " }{TEXT 420 1 "m" }{TEXT -1 3 " = " } {XPPEDIT 18 0 "z^2-2;" "6#,&*$%\"zG\"\"#\"\"\"F&!\"\"" }{TEXT -1 3 ", \+ " }{XPPEDIT 18 0 "f[1] = x^3+`...`;" "6#/&%\"fG6#\"\"\",&*$%\"xG\"\"$ F'%$...GF'" }{TEXT -1 7 " and " }{XPPEDIT 18 0 "f[2] = (z+6)*x^2+`.. .`;" "6#/&%\"fG6#\"\"#,&*&,&%\"zG\"\"\"\"\"'F,F,*$%\"xGF'F,F,%$...GF, " }{TEXT -1 2 " ." }}{PARA 0 "" 0 "" {TEXT -1 4 "For " }{TEXT 363 1 "p " }{TEXT -1 14 " = 17 we have " }{XPPEDIT 18 0 "z^2-2 = (z-6)*(z+6);" "6#/,&*$%\"zG\"\"#\"\"\"F'!\"\"*&,&F&F(\"\"'F)F(,&F&F(F,F(F(" }{TEXT -1 23 " mod 17. \nHence L mod " }{TEXT 364 1 "p" }{TEXT -1 53 " may b e a finite ring with zero divisors and the EA( " }{XPPEDIT 18 0 "`mod` (f[1],p);" "6#-%$modG6$&%\"fG6#\"\"\"%\"pG" }{TEXT -1 3 ", " } {XPPEDIT 18 0 "`mod`(f[2],p);" "6#-%$modG6$&%\"fG6#\"\"#%\"pG" }{TEXT -1 12 " ) may fail." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 6 "\nLet ~" } {XPPEDIT 18 0 "f[1];" "6#&%\"fG6#\"\"\"" }{TEXT -1 3 " = " }{XPPEDIT 502 0 "a[m]*x^m+a[m-1](alpha)*x^(m-1)+`...`;" "6#,(*&&%\"aG6#%\"mG\"\" \")%\"xGF(F)F)*&-&F&6#,&F(F)F)!\"\"6#%&alphaGF))F+,&F(F)F)F1F)F)%$...G F)" }{TEXT -1 3 " + " }{XPPEDIT 18 0 "a[0](alpha);" "6#-&%\"aG6#\"\"!6 #%&alphaG" }{TEXT -1 8 ", where " }{XPPEDIT 18 0 "a[i];" "6#&%\"aG6#% \"iG" }{TEXT -1 8 " are in " }{TEXT 325 1 "Z" }{TEXT -1 7 "\nand ~" } {XPPEDIT 18 0 "f[2];" "6#&%\"fG6#\"\"#" }{TEXT -1 3 " = " }{XPPEDIT 18 0 "b[n]*x^n+b[n-1](alpha)*x^(m-1)+`...`+b[0](alpha);" "6#,**&&%\"bG 6#%\"nG\"\"\")%\"xGF(F)F)*&-&F&6#,&F(F)F)!\"\"6#%&alphaGF))F+,&%\"mGF) F)F1F)F)%$...GF)-&F&6#\"\"!6#F3F)" }{TEXT -1 8 " where " }{XPPEDIT 18 0 "b[i];" "6#&%\"bG6#%\"iG" }{TEXT -1 8 " are in " }{TEXT 326 1 "Z " }{TEXT -1 8 ".\nLet ~" }{TEXT 357 1 "g" }{TEXT -1 4 " = " } {XPPEDIT 18 0 "c[l]*x^l+c[l-1](alpha)*x^(l-1)+`...`+c[0](alpha);" "6#, **&&%\"cG6#%\"lG\"\"\")%\"xGF(F)F)*&-&F&6#,&F(F)F)!\"\"6#%&alphaGF))F+ ,&F(F)F)F1F)F)%$...GF)-&F&6#\"\"!6#F3F)" }{TEXT -1 7 " where " } {XPPEDIT 18 0 "c[i];" "6#&%\"cG6#%\"iG" }{TEXT -1 8 " are in " }{TEXT 327 1 "Z" }{TEXT -1 3 ".\n\n" }{TEXT 503 5 "Does " }{XPPEDIT 504 0 "c[ l];" "6#&%\"cG6#%\"lG" }{TEXT 505 3 " | " }{XPPEDIT 506 0 "a[m];" "6#& %\"aG6#%\"mG" }{TEXT 507 2 " ?" }{TEXT -1 15 " Not always !\n" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 3 " ~" }{XPPEDIT 18 0 "f[1];" "6#&%\" fG6#\"\"\"" }{TEXT -1 5 " = " }{XPPEDIT 18 0 "3*x^3-x^2*sqrt(5)-3*x^ 2+x*sqrt(5)-3*x+sqrt(5);" "6#,.*&\"\"$\"\"\"*$%\"xGF%F&F&*&F(\"\"#-%%s qrtG6#\"\"&F&!\"\"*&F%F&*$F(F*F&F/*&F(F&-F,6#F.F&F&*&F%F&F(F&F/-F,6#F. F&" }{TEXT -1 6 " = " }{XPPEDIT 18 0 "(3*x-sqrt(5))*(2*x-1+sqrt(5)) *(2*x-1-sqrt(5))/4;" "6#**,&*&\"\"$\"\"\"%\"xGF'F'-%%sqrtG6#\"\"&!\"\" F',(*&\"\"#F'F(F'F'F'F--F*6#F,F'F',(*&F0F'F(F'F'F'F--F*6#F,F-F'\"\"%F- " }}}{EXCHG {PARA 0 "" 0 "" {TEXT 311 1 "\n" }{TEXT 508 7 "Theorem" } {TEXT 509 32 " (Rothschild, Weinberger, 1976)." }{TEXT -1 5 "\nLet " } {XPPEDIT 18 0 "Delta;" "6#%&DeltaG" }{TEXT -1 7 " = res(" }{TEXT 302 4 "m,m'" }{TEXT -1 32 " ) be the discriminant of L and " }{TEXT 303 1 "d" }{TEXT -1 34 " be the largest integer such that " }{XPPEDIT 18 0 " d^2;" "6#*$%\"dG\"\"#" }{TEXT -1 3 " | " }{XPPEDIT 18 0 "Delta;" "6#%& DeltaG" }{TEXT -1 7 ".\nLet " }{TEXT 382 4 "f, g" }{TEXT -1 18 " be n on-zero in L[" }{TEXT 408 1 "x" }{TEXT -1 9 "]. If ~" }{TEXT 304 1 " g" }{TEXT -1 4 " | ~" }{TEXT 305 1 "f" }{TEXT -1 12 " then lc(~" } {TEXT 306 1 "g" }{TEXT -1 4 ") | " }{TEXT 307 1 "d" }{TEXT -1 5 " lc(~ " }{TEXT 308 1 "f" }{TEXT -1 3 ") ." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 10 "\nThus if " }{TEXT 409 1 "g" }{TEXT -1 8 " = gcd( " }{XPPEDIT 18 0 "f[1],f[2];" "6$&%\"fG6#\"\"\"&F$6#\"\"#" }{TEXT -1 13 ") then \+ lc(~" }{TEXT 309 1 "g" }{TEXT -1 4 ") | " }{TEXT 310 1 "d" }{TEXT -1 10 " gcd( lc(~" }{XPPEDIT 18 0 "f[1];" "6#&%\"fG6#\"\"\"" }{TEXT -1 7 "), lc(~" }{XPPEDIT 18 0 "f[2];" "6#&%\"fG6#\"\"#" }{TEXT -1 16 ") ) . \nSo take " }{XPPEDIT 18 0 "gamma;" "6#%&gammaG" }{TEXT -1 3 " = " } {XPPEDIT 18 0 "Delta;" "6#%&DeltaG" }{TEXT -1 10 " gcd( lc(~" } {XPPEDIT 18 0 "f[1];" "6#&%\"fG6#\"\"\"" }{TEXT -1 7 "), lc(~" } {XPPEDIT 18 0 "f[2];" "6#&%\"fG6#\"\"#" }{TEXT -1 5 ") ).\n" }{TEXT 358 7 "Remark:" }{TEXT -1 12 " computing ~" }{XPPEDIT 18 0 "f[1];" "6# &%\"fG6#\"\"\"" }{TEXT -1 7 ", and ~" }{XPPEDIT 18 0 "f[2];" "6#&%\"fG 6#\"\"#" }{TEXT -1 18 " is expensive and " }{XPPEDIT 18 0 "gamma;" "6# %&gammaG" }{TEXT -1 28 " might be a lot bigger than " }{XPPEDIT 18 0 " c[l];" "6#&%\"cG6#%\"lG" }{TEXT -1 3 " .\n" }{TEXT 423 8 "Problem:" } {TEXT -1 23 " inefficient for gcd( " }{TEXT 422 6 "f, f '" }{TEXT -1 13 " ) because " }{XPPEDIT 18 0 "gamma;" "6#%&gammaG" }{TEXT -1 3 " \+ = " }{XPPEDIT 18 0 "Delta;" "6#%&DeltaG" }{TEXT -1 6 " lc( ~" }{TEXT 421 1 "f" }{TEXT -1 4 " ) ." }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 24 " Encarnacion's algorithm." }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 29 "\nDrop 's the restriction that " }{XPPEDIT 18 0 "alpha;" "6#%&alphaG" }{TEXT -1 86 " be an algebraic integer.\nUses rational reconstruction to reco ver the coefficients of " }{TEXT 359 1 "g" }{TEXT -1 80 " and trial di vision.\n Algorithm is output senstive: the #primes depends on H(" }{TEXT 360 1 "g" }{TEXT -1 28 ").\n It's sufficient that " }{TEXT 362 1 "p" }{TEXT -1 12 " not divide " }{XPPEDIT 18 0 "Delta;" "6#%&Del taG" }{TEXT -1 10 " and lc( ^" }{XPPEDIT 18 0 "f[1];" "6#&%\"fG6#\"\" \"" }{TEXT -1 7 ") lc( ^" }{XPPEDIT 18 0 "f[2];" "6#&%\"fG6#\"\"#" } {TEXT -1 17 " ) are not 0 mod " }{TEXT 361 1 "p" }{TEXT -1 1 "." } {TEXT 312 1 " " }{TEXT 23 2 " " }{TEXT -1 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 20 "Our algorithm fo r Q(" }{XPPEDIT 18 0 "alpha;" "6#%&alphaG" }{TEXT -1 1 "(" }{XPPEDIT 18 0 "t[1];" "6#&%\"tG6#\"\"\"" }{TEXT -1 7 ", ..., " }{XPPEDIT 18 0 " t[k];" "6#&%\"tG6#%\"kG" }{TEXT -1 3 "))[" }{TEXT 314 1 "x" }{TEXT -1 1 "]" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 11 "Let F = Q(" }{XPPEDIT 18 0 "t[1];" "6#&%\"tG6#\"\"\"" }{TEXT -1 7 ", ..., " }{XPPEDIT 18 0 "t[k ];" "6#&%\"tG6#%\"kG" }{TEXT -1 4 "), " }{TEXT 366 1 "m" }{TEXT -1 32 " be monic and irreducible in F[" }{TEXT 369 1 "z" }{TEXT -1 12 "] and L = F[" }{TEXT 367 1 "z" }{TEXT -1 3 "]/(" }{TEXT 368 1 "m" } {TEXT -1 7 ").\nLet " }{XPPEDIT 18 0 "f[1];" "6#&%\"fG6#\"\"\"" } {TEXT -1 5 " and " }{XPPEDIT 18 0 "f[2];" "6#&%\"fG6#\"\"#" }{TEXT -1 18 " be non-zero in L[" }{TEXT 370 1 "x" }{TEXT -1 10 "] and let " } {TEXT 371 1 "g" }{TEXT -1 73 " be their monic gcd.\nWe could avoid pri mes/evaluation points that divide " }{XPPEDIT 511 0 "gamma = Delta;" " 6#/%&gammaG%&DeltaG" }{TEXT 512 6 " lc( ~" }{XPPEDIT 513 0 "f[1];" "6# &%\"fG6#\"\"\"" }{TEXT 514 8 " ) lc( ~" }{XPPEDIT 515 0 "f[2];" "6#&% \"fG6#\"\"#" }{TEXT 516 3 " ) " }{TEXT -1 1 "." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 33 "\nLet I be a maximal ideal in D = " }{TEXT 424 1 "Z " }{TEXT -1 1 "[" }{XPPEDIT 18 0 "t[1];" "6#&%\"tG6#\"\"\"" }{TEXT -1 7 ", ..., " }{XPPEDIT 18 0 "t[k];" "6#&%\"tG6#%\"kG" }{TEXT -1 38 "]. \n We will use ideals of the form " }{XPPEDIT 517 0 ";" "6#-%7rtable/ConstructColumnG6$%\"pG6%,&&%\" tG6#\"\"\"F,&%%betaG6#F,!\"\"%$...G,&&F*6#%\"kGF,&F.6#F5F0" }{TEXT -1 6 ".\nLet " }{TEXT 385 1 "e" }{TEXT -1 26 " be the output of the EA( \+ " }{XPPEDIT 18 0 "`mod`(f[1],I);" "6#-%$modG6$&%\"fG6#\"\"\"%\"IG" } {TEXT -1 3 " , " }{XPPEDIT 18 0 "`mod`(f[2],I);" "6#-%$modG6$&%\"fG6# \"\"#%\"IG" }{TEXT -1 64 " ).\n The EA may output \"failed\" if it h it's a zero divisor. \n\n" }{TEXT 373 12 " Definition:" }{TEXT -1 9 " \+ I is " }{TEXT 372 6 "lc-bad" }{TEXT -1 7 " if " }{TEXT 518 4 "lc (^" }{TEXT 425 1 "m" }{TEXT 519 6 ") lc(^" }{XPPEDIT 520 0 "f[1];" "6# &%\"fG6#\"\"\"" }{TEXT 521 6 ") lc(^" }{XPPEDIT 522 0 "f[2];" "6#&%\"f G6#\"\"#" }{TEXT 523 14 ") mod I = 0" }{TEXT -1 2 ".\n" }{TEXT 374 12 " Definition:" }{TEXT -1 5 " I " }{TEXT 375 5 "fails" }{TEXT -1 13 " if the EA( " }{XPPEDIT 18 0 "`mod`(f[1],I);" "6#-%$modG6$&%\"fG6 #\"\"\"%\"IG" }{TEXT -1 3 " , " }{XPPEDIT 18 0 "`mod`(f[2],I);" "6#-%$ modG6$&%\"fG6#\"\"#%\"IG" }{TEXT -1 30 " ) encounters a zero divisor. \n" }{TEXT 378 13 " Definition: " }{TEXT -1 8 " I is " }{TEXT 379 7 "unlucky" }{TEXT -1 29 " if I does not fail and deg(" }{TEXT 376 1 "e " }{TEXT -1 8 ") > deg(" }{TEXT 377 1 "g" }{TEXT -1 3 ").\n" }{TEXT 380 12 " Definition:" }{TEXT -1 9 " I is " }{TEXT 381 4 "good" } {TEXT -1 25 " if I does not fail and" }{TEXT 407 6 " e ~ g" }{TEXT -1 8 " mod I ." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 1 "\n" }{TEXT 383 8 "Theorem:" }{TEXT -1 75 " If I is not lc-bad and does not fail the n it is either unlucky or good.\n" }{TEXT 384 8 "Theorem:" }{TEXT 510 1 " " }{TEXT -1 65 " The number of lc-bad, fail and unlucky ideals is \+ finite.\n No " }{XPPEDIT 18 0 "Delta;" "6#%&DeltaG" }{TEXT -1 27 " \+ and no need to invert lc( " }{XPPEDIT 18 0 "f[1];" "6#&%\"fG6#\"\"\"" }{TEXT -1 11 " ) and lc( " }{XPPEDIT 18 0 "f[2];" "6#&%\"fG6#\"\"#" } {TEXT -1 25 " ). lc-bad test costs 0." }}}{SECT 1 {PARA 4 "" 0 "" {TEXT 482 16 "Repeated failure" }{TEXT -1 0 "" }}{EXCHG {PARA 0 "" 0 " " {TEXT 473 1 "\n" }{TEXT -1 3 "I =" }{TEXT 481 1 " " }{XPPEDIT 18 0 " " "6#-%7rtable/ConstructColumnG6$ %\"pG6%,&&%\"tG6#\"\"\"F,&%%betaG6#F,!\"\"%$...G,&&F*6#%\"kGF,&F.6#F5F 0" }{TEXT 480 2 "\n " }}{PARA 0 "" 0 "" {TEXT -1 12 "Let m(z) = " } {XPPEDIT 18 0 "z^2-7*s*t;" "6#,&*$%\"zG\"\"#\"\"\"*(\"\"(F'%\"sGF'%\"t GF'!\"\"" }{TEXT -1 5 " , " }{XPPEDIT 18 0 "f[1] = x^3+`...`;" "6#/& %\"fG6#\"\"\",&*$%\"xG\"\"$F'%$...GF'" }{TEXT -1 5 " and " }{XPPEDIT 18 0 "f[2] = z*x^2+`...`;" "6#/&%\"fG6#\"\"#,&*&%\"zG\"\"\"*$%\"xGF'F+ F+%$...GF+" }{TEXT -1 10 "\nConsider " }{TEXT 475 1 "p" }{TEXT -1 15 " = 7.\nConsider " }{TEXT 474 1 "p" }{TEXT -1 7 " = 11, " }{TEXT 476 1 "s" }{TEXT -1 6 " = 3, " }{TEXT 477 1 "s" }{TEXT -1 6 " = 4, " }{TEXT 478 1 "s" }{TEXT -1 17 " = 0, ...\n\nCount " }{TEXT 471 2 "d " }{TEXT -1 30 "the number of fail ideals and " }{TEXT 472 1 "n" }{TEXT -1 63 " the number which don't fail.\nAbort this prime (evaluation) if " } {TEXT 469 1 "d" }{TEXT -1 3 " > " }{TEXT 470 1 "n" }{TEXT -1 2 ".\n" } {TEXT 479 43 "Evaluation points must be chosen at random;" }{TEXT -1 17 " always choosing " }{XPPEDIT 18 0 "s = 0;" "6#/%\"sG\"\"!" }{TEXT -1 22 " will fail repeatedly." }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT 467 28 "Consistent leading monomials" }{TEXT 468 1 "." }{TEXT -1 0 "" }} {EXCHG {PARA 0 "" 0 "" {TEXT -1 10 "\nSuppose ^" }{TEXT 466 1 "g" } {TEXT -1 3 " = " }{XPPEDIT 18 0 "t*x-5+t*z;" "6#,(*&%\"tG\"\"\"%\"xGF& F&\"\"&!\"\"*&F%F&%\"zGF&F&" }{TEXT -1 3 ", " }{XPPEDIT 18 0 "f[1] = \+ g*(x+7*t);" "6#/&%\"fG6#\"\"\"*&%\"gGF',&%\"xGF'*&\"\"(F'%\"tGF'F'F'" }{TEXT -1 7 " and " }{XPPEDIT 18 0 "f[1] = g*x;" "6#/&%\"fG6#\"\"\"* &%\"gGF'%\"xGF'" }{TEXT -1 7 " .\n\n " }{XPPEDIT 18 0 "p = 3;" "6#/% \"pG\"\"$" }{TEXT -1 10 " we get " }{XPPEDIT 18 0 "e = t*x+1+t*z;" " 6#/%\"eG,(*&%\"tG\"\"\"%\"xGF(F(F(F(*&F'F(%\"zGF(F(" }{TEXT -1 5 " \n \+ " }{XPPEDIT 18 0 "p = 5;" "6#/%\"pG\"\"&" }{TEXT -1 10 " we get " }{XPPEDIT 18 0 "e = x+z;" "6#/%\"eG,&%\"xG\"\"\"%\"zGF'" }{TEXT -1 25 " (content vanished)\n " }{XPPEDIT 18 0 "p = 7;" "6#/%\"pG\"\"(" } {TEXT -1 10 " we get " }{XPPEDIT 18 0 "e = t*x^2+2*x+t*z*x;" "6#/%\" eG,(*&%\"tG\"\"\"*$%\"xG\"\"#F(F(*&F+F(F*F(F(*(F'F(%\"zGF(F*F(F(" } {TEXT -1 20 " (unlucky prime)\n " }{XPPEDIT 18 0 "p = 11;" "6#/%\"pG \"#6" }{TEXT -1 9 " we get " }{XPPEDIT 18 0 "e = t*x-5+t*z;" "6#/%\"e G,(*&%\"tG\"\"\"%\"xGF(F(\"\"&!\"\"*&F'F(%\"zGF(F(" }{TEXT -1 148 " . \n\nAfter each prime (evaluation point) combine images with same leadi ng monomial.\nDon't need explicit tests or unlucky primes (evaluation \+ points).\n" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT 490 52 "Variable at a ti me Rational Function Reconstruction." }{TEXT -1 0 "" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 8 "Suppose " }{XPPEDIT 18 0 "g = x+s/(1+s*t)*alpha+13 *t/(1+s*t);" "6#/%\"gG,(%\"xG\"\"\"*(%\"sGF',&F'F'*&F)F'%\"tGF'F'!\"\" %&alphaGF'F'*(\"#8F'F,F',&F'F'*&F)F'F,F'F'F-F'" }{TEXT -1 22 " . \n\n We will output ^" }{TEXT 483 2 "g " }{TEXT -1 2 "= " }{XPPEDIT 18 0 "( 1+s*t)*x+s*alpha+13*t;" "6#,(*&,&\"\"\"F&*&%\"sGF&%\"tGF&F&F&%\"xGF&F& *&F(F&%&alphaGF&F&*&\"#8F&F)F&F&" }{TEXT -1 30 " .\n\nWe get images of the form " }{XPPEDIT 18 0 "(1*s+`.`)*x+`.`*s*alpha+`.`;" "6#,(*&,&*& \"\"\"F'%\"sGF'F'%\".GF'F'%\"xGF'F'*(F)F'F(F'%&alphaGF'F'F)F'" }{TEXT -1 43 " \n\nRational function reconstruction gives " }{XPPEDIT 18 0 " (1*s+1/t)*x;" "6#*&,&*&\"\"\"F&%\"sGF&F&*&F&F&%\"tG!\"\"F&F&%\"xGF&" } {TEXT -1 3 " + " }{XPPEDIT 18 0 "1/t;" "6#*&\"\"\"F$%\"tG!\"\"" } {TEXT -1 1 " " }{XPPEDIT 18 0 "s;" "6#%\"sG" }{TEXT -1 1 " " } {XPPEDIT 18 0 "alpha;" "6#%&alphaG" }{TEXT -1 3 " + " }{XPPEDIT 18 0 " 13/1;" "6#*&\"#8\"\"\"F%!\"\"" }{TEXT -1 31 " .\n\nWe clear fractions: ^g = (" }{XPPEDIT 18 0 "s*t+1;" "6#,&*&%\"sG\"\"\"%\"tGF&F&F&F&" } {TEXT -1 2 ") " }{TEXT 484 1 "x" }{TEXT -1 3 " + " }{XPPEDIT 18 0 "s*a lpha+13*t;" "6#,&*&%\"sG\"\"\"%&alphaGF&F&*&\"#8F&%\"tGF&F&" }{TEXT -1 64 " .\n\nRequires only univariate rational function reconstruction in" }{TEXT 489 2 " Z" }{TEXT 488 1 "p" }{TEXT -1 27 "(t) and gcd comp utation in " }{TEXT 487 1 "Z" }{TEXT 486 1 "p" }{TEXT -1 1 "[" }{TEXT 485 1 "t" }{TEXT -1 2 "]." }}}}}{SECT 1 {PARA 4 "" 0 "" {TEXT 528 15 " Algorithm AFGCD" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 7 "Input: " }{TEXT 526 1 "m" }{TEXT -1 6 " in F[" }{TEXT 529 1 "z" }{TEXT -1 33 "], monic , irreducible, where F=Q(" }{XPPEDIT 18 0 "t[1],`...`,t[k];" "6%&%\"tG 6#\"\"\"%$...G&F$6#%\"kG" }{TEXT -1 28 "), \n and non-zero \+ " }{XPPEDIT 18 0 "f[1],f[2];" "6$&%\"fG6#\"\"\"&F$6#\"\"#" }{TEXT -1 6 " in L[" }{TEXT 547 1 "x" }{TEXT -1 12 "] where L=F[" }{TEXT 527 1 " z" }{TEXT -1 3 "]/(" }{TEXT 585 1 "m" }{TEXT -1 11 ")\nOutput: ^" } {TEXT 595 1 "g" }{TEXT -1 7 " where " }{TEXT 596 1 "g" }{TEXT -1 19 " \+ is the monic gcd( " }{XPPEDIT 18 0 "f[1];" "6#&%\"fG6#\"\"\"" }{TEXT -1 2 ", " }{XPPEDIT 18 0 "f[2];" "6#&%\"fG6#\"\"#" }{TEXT -1 39 " ) or \"failed\".\nCall subroutine MGCD( ^" }{TEXT 594 1 "m" }{TEXT -1 3 ", ^" }{XPPEDIT 18 0 "f[1];" "6#&%\"fG6#\"\"\"" }{TEXT -1 3 ", ^" } {XPPEDIT 18 0 "f[2];" "6#&%\"fG6#\"\"#" }{TEXT -1 2 " )" }}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 15 "Subroutine MGCD" }}{EXCHG {PARA 0 "" 0 " " {TEXT -1 7 "Input: " }{TEXT 543 1 "m" }{TEXT -1 6 " in D[" }{TEXT 548 1 "z" }{TEXT -1 10 "] where D=" }{TEXT 544 1 "Z" }{TEXT -1 1 "[" } {XPPEDIT 18 0 "t[1],`...`,t[k];" "6%&%\"tG6#\"\"\"%$...G&F$6#%\"kG" } {TEXT -1 5 "], " }{XPPEDIT 18 0 "f[1],f[2];" "6$&%\"fG6#\"\"\"&F$6# \"\"#" }{TEXT -1 19 " in R[x] where R=D[" }{TEXT 545 1 "z" }{TEXT -1 43 "]/(m)\nOutput: ^g where g is the monic gcd( " }{XPPEDIT 18 0 "f[1] ;" "6#&%\"fG6#\"\"\"" }{TEXT -1 2 ", " }{XPPEDIT 18 0 "f[2];" "6#&%\"f G6#\"\"#" }{TEXT -1 20 " ) or \"failed\".\nSet " }{TEXT 538 1 "n" } {TEXT -1 30 " = 1.\nLoop: Take a new prime " }{TEXT 549 1 "p" }{TEXT -1 39 " which is not lc-bad.\n Set " }{TEXT 533 2 "e " } {TEXT -1 2 "= " }{TEXT 546 4 "PGCD" }{TEXT -1 4 "( m(" }{XPPEDIT 18 0 "z;" "6#%\"zG" }{TEXT -1 6 ") mod " }{TEXT 550 1 "p" }{TEXT -1 3 ", \+ " }{XPPEDIT 18 0 "`mod`(f[1],p);" "6#-%$modG6$&%\"fG6#\"\"\"%\"pG" } {TEXT -1 3 ", " }{XPPEDIT 18 0 "`mod`(f[2],p);" "6#-%$modG6$&%\"fG6# \"\"#%\"pG" }{TEXT -1 19 " )\n If " }{TEXT 534 1 "e" } {TEXT -1 44 " = \"failed\" then goto Loop \n If " }{TEXT 532 1 "e" }{TEXT -1 28 " = 1 then output 1 else set " }{TEXT 539 1 "n " }{TEXT -1 3 " = " }{TEXT 540 1 "n" }{TEXT -1 83 " + 1.\n \+ Apply the CRT to all images with leading monomial = LM(e) to get " } {TEXT 541 1 "C" }{TEXT -1 7 " mod M(" }{XPPEDIT 18 0 "t[k];" "6#&%\"tG 6#%\"kG" }{TEXT -1 19 ") \n Set " }{TEXT 535 2 "h " }{TEXT -1 7 "= RFR( " }{XPPEDIT 18 0 "`mod`(C,M(t[k]));" "6#-%$modG6$%\"CG-% \"MG6#&%\"tG6#%\"kG" }{TEXT -1 74 " ). If this fails then goto Loop. \n Clear fractions in Q: Set " }{TEXT 537 1 "g" }{TEXT -1 4 " = ^" }{TEXT 536 1 "h" }{TEXT -1 19 " .\n If " }{TEXT 530 4 "g | " }{XPPEDIT 18 0 "f[1];" "6#&%\"fG6#\"\"\"" }{TEXT -1 5 " a nd " }{TEXT 531 2 "g " }{TEXT -1 2 "| " }{XPPEDIT 18 0 "f[2];" "6#&%\" fG6#\"\"#" }{TEXT -1 13 " then output " }{TEXT 542 2 "g " }{TEXT -1 15 "else goto Loop." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 42 "Optimizati on: replace trial divisons in F[" }{TEXT 551 1 "x" }{TEXT -1 46 "] wit h primitive fraction free divisions in R[" }{TEXT 552 1 "x" }{TEXT -1 2 "]." }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 15 "Subroutine PGCD" }} {EXCHG {PARA 0 "" 0 "" {TEXT 604 6 "Input:" }{TEXT -1 1 " " }{TEXT 573 1 "m" }{TEXT -1 5 " in D" }{TEXT 574 1 "p" }{TEXT -1 1 "[" }{TEXT 592 1 "z" }{TEXT -1 9 "] where D" }{TEXT 575 1 "p" }{TEXT -1 1 "=" } {TEXT 577 1 "Z" }{TEXT 576 1 "p" }{TEXT -1 1 "[" }{XPPEDIT 18 0 "t[1], `...`,t[k];" "6%&%\"tG6#\"\"\"%$...G&F$6#%\"kG" }{TEXT -1 5 "], " } {XPPEDIT 18 0 "f[1],f[2];" "6$&%\"fG6#\"\"\"&F$6#\"\"#" }{TEXT -1 5 " \+ in R" }{TEXT 578 1 "p" }{TEXT -1 11 "[x] where R" }{TEXT 579 1 "p" } {TEXT -1 2 "=D" }{TEXT 580 1 "p" }{TEXT -1 1 "[" }{TEXT 581 1 "z" } {TEXT -1 6 "]/(m)\n" }{TEXT 605 7 "Output:" }{TEXT -1 30 " ^g where g \+ is the monic gcd( " }{XPPEDIT 18 0 "f[1];" "6#&%\"fG6#\"\"\"" }{TEXT -1 2 ", " }{XPPEDIT 18 0 "f[2];" "6#&%\"fG6#\"\"#" }{TEXT -1 15 " ) or \"failed\"." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 3 "If " }{XPPEDIT 18 0 "k = 0;" "6#/%\"kG\"\"!" }{TEXT -1 14 " the n output " }{TEXT 612 2 "EA" }{TEXT -1 2 "( " }{XPPEDIT 18 0 "f[1],f[2 ];" "6$&%\"fG6#\"\"\"&F$6#\"\"#" }{TEXT -1 64 " ) -- which outputs \"f ailed\" if it enounters a zero divisor\nSet " }{TEXT 561 1 "n" }{TEXT -1 6 " = 1, " }{TEXT 562 2 "d " }{TEXT -1 23 "= 1.\nLoop: Take a new \+ " }{XPPEDIT 18 0 "beta;" "6#%%betaG" }{TEXT -1 4 " in " }{TEXT 593 1 " Z" }{TEXT 569 1 "p" }{TEXT -1 1 " " }{TEXT 563 9 "at random" }{TEXT 586 1 " " }{TEXT -1 38 "which is not lc-bad.\n Set " } {TEXT 556 2 "e " }{TEXT -1 2 "= " }{TEXT 584 4 "PGCD" }{TEXT -1 5 "( m ( " }{XPPEDIT 18 0 "t[k] = beta;" "6#/&%\"tG6#%\"kG%%betaG" }{TEXT -1 4 "), " }{XPPEDIT 18 0 "f[1](t[k] = beta);" "6#-&%\"fG6#\"\"\"6#/&%\" tG6#%\"kG%%betaG" }{TEXT -1 3 ", " }{XPPEDIT 18 0 "f[2](t[k],beta);" "6#-&%\"fG6#\"\"#6$&%\"tG6#%\"kG%%betaG" }{TEXT -1 19 " )\n \+ If " }{TEXT 557 1 "e" }{TEXT -1 40 " = \"failed\" then \n \+ Set " }{TEXT 564 1 "d" }{TEXT -1 3 " = " }{TEXT 565 1 "d" } {TEXT -1 10 " + 1; If " }{TEXT 570 1 "d" }{TEXT -1 3 " > " }{TEXT 571 1 "n" }{TEXT -1 59 " then output \"failed\" otherwise goto Loop.\n If " }{TEXT 555 1 "e" }{TEXT -1 10 " = 1 then " }{TEXT 606 6 "output" }{TEXT 607 2 " 1" }{TEXT -1 10 " else set " }{TEXT 566 1 "n" }{TEXT -1 3 " = " }{TEXT 567 1 "n" }{TEXT -1 83 " + 1.\n \+ Apply the CRT to all images with leading monomial = LM(e) to get \+ " }{TEXT 568 1 "C" }{TEXT -1 7 " mod M(" }{XPPEDIT 18 0 "t[k];" "6#&% \"tG6#%\"kG" }{TEXT -1 19 ") \n Set " }{TEXT 558 2 "h " } {TEXT -1 7 "= RFR( " }{XPPEDIT 18 0 "`mod`(C,M(t[k]));" "6#-%$modG6$% \"CG-%\"MG6#&%\"tG6#%\"kG" }{TEXT -1 66 " ). If this fails then goto \+ Loop.\n Clear fractions in " }{TEXT 583 1 "Z" }{TEXT 582 1 "p" }{TEXT -1 1 "(" }{XPPEDIT 18 0 "t[k];" "6#&%\"tG6#%\"kG" }{TEXT -1 8 "): Set " }{TEXT 560 1 "g" }{TEXT -1 4 " = ^" }{TEXT 559 1 "h" } {TEXT -1 19 " .\n If " }{TEXT 553 4 "g | " }{XPPEDIT 18 0 "f[1];" "6#&%\"fG6#\"\"\"" }{TEXT -1 5 " and " }{TEXT 554 2 "g " } {TEXT -1 2 "| " }{XPPEDIT 18 0 "f[2];" "6#&%\"fG6#\"\"#" }{TEXT -1 6 " then " }{TEXT 608 6 "output" }{TEXT 610 1 " " }{TEXT 572 1 "g" } {TEXT 609 1 " " }{TEXT -1 15 "else goto Loop." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 41 "Optimization: replace trial divisons in R" }{TEXT 587 1 "p" }{TEXT -1 1 "[" }{TEXT 611 1 "x" }{TEXT -1 28 "] with univariate ones over " }{TEXT 591 1 "Z" }{TEXT 590 1 "p" }{TEXT -1 1 "[" }{TEXT 588 1 "z" }{TEXT -1 3 "]/(" }{TEXT 589 1 "m" }{TEXT -1 20 ") \nby eval uating at " }{XPPEDIT 18 0 "f[1],f[2];" "6$&%\"fG6#\"\"\"&F$6#\"\"#" } {TEXT -1 5 " and " }{XPPEDIT 18 0 "h;" "6#%\"hG" }{TEXT -1 4 " at " } {XPPEDIT 18 0 "t[1] = beta[1],`...`,t[k] = beta[k];" "6%/&%\"tG6#\"\" \"&%%betaG6#F'%$...G/&F%6#%\"kG&F)6#F/" }{TEXT -1 12 " for random " } {XPPEDIT 18 0 "beta[i];" "6#&%%betaG6#%\"iG" }{TEXT -1 89 " , periodic ally.\nAssumes rational reconstruction outputs fail with high probabil ity if M(" }{XPPEDIT 18 0 "t[k];" "6#&%\"tG6#%\"kG" }{TEXT -1 24 ") is not big enough yet." }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 25 "The Mul tivariate case: L[" }{XPPEDIT 18 0 "x[1];" "6#&%\"xG6#\"\"\"" }{TEXT -1 7 ", ..., " }{XPPEDIT 18 0 "x[n];" "6#&%\"xG6#%\"nG" }{TEXT -1 1 "] " }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 6 "Write " }{XPPEDIT 18 0 "f[1],f[ 2];" "6$&%\"fG6#\"\"\"&F$6#\"\"#" }{TEXT -1 6 " in L[" }{XPPEDIT 18 0 "x[2];" "6#&%\"xG6#\"\"#" }{TEXT -1 7 ", ..., " }{XPPEDIT 18 0 "x[n]; " "6#&%\"xG6#%\"nG" }{TEXT -1 2 "][" }{XPPEDIT 18 0 "x[1];" "6#&%\"xG6 #\"\"\"" }{TEXT -1 14 "] and compute " }{TEXT 599 1 "c" }{TEXT -1 18 " = gcd( coeffs of " }{XPPEDIT 18 0 "f[1];" "6#&%\"fG6#\"\"\"" }{TEXT -1 5 " and " }{XPPEDIT 18 0 "f[2];" "6#&%\"fG6#\"\"#" }{TEXT -1 4 " in " }{XPPEDIT 18 0 "x[1];" "6#&%\"xG6#\"\"\"" }{TEXT -1 9 " )\nWrite " }{XPPEDIT 18 0 "f[1],f[2];" "6$&%\"fG6#\"\"\"&F$6#\"\"#" }{TEXT -1 6 " in G[" }{XPPEDIT 18 0 "x[1];" "6#&%\"xG6#\"\"\"" }{TEXT -1 14 "] wher e G = K[" }{TEXT 602 1 "z" }{TEXT -1 3 "]/(" }{TEXT 603 1 "m" }{TEXT -1 12 ") and K = Q(" }{XPPEDIT 18 0 "t[1],`...`,t[k];" "6%&%\"tG6#\"\" \"%$...G&F$6#%\"kG" }{TEXT -1 2 ", " }{XPPEDIT 18 0 "x[2],`...`,x[n]; " "6%&%\"xG6#\"\"#%$...G&F$6#%\"nG" }{TEXT -1 22 ").\nCompute their gc d ^" }{TEXT 601 1 "h" }{TEXT -1 6 " in G[" }{XPPEDIT 18 0 "x[1];" "6#& %\"xG6#\"\"\"" }{TEXT -1 41 "] using AFGCD and make it primitive in L[ " }{XPPEDIT 18 0 "x[2];" "6#&%\"xG6#\"\"#" }{TEXT -1 7 ", ..., " } {XPPEDIT 18 0 "x[n];" "6#&%\"xG6#%\"nG" }{TEXT -1 2 "][" }{XPPEDIT 18 0 "x[1];" "6#&%\"xG6#\"\"\"" }{TEXT -1 11 "].\nOutput ^" }{TEXT 597 1 "g" }{TEXT -1 3 " = " }{TEXT 598 1 "c" }{TEXT -1 2 " ^" }{TEXT 600 1 " h" }{TEXT -1 2 " ." }}}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 30 "Timings \+ for GCD problems in Q(" }{XPPEDIT 18 0 "alpha(t);" "6#-%&alphaG6#%\"tG " }{TEXT -1 5 ")[x] " }}{EXCHG {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"mG, ,*$)%\"zG\"\"$\"\"\"F**&,&\"\"&F*%\"tG!\"\"F*)F(\"\"#F*F/*&,&\"\"(F**$ )F.F1F*F/F*F(F*F*\"\"*F/*$)F.F)F*F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #>%\"gG,2*&,&\"#5\"\"\"*&\"\"%F)%\"tGF)!\"\"F))%\"xG\"\"#F)F)*&,.\"#6F )%\"zGF)*&\"\"*F)F,F)F)*&\"\"&F))F4F0F)F-*(F+F)F4F)F,F)F)*&\"#F)F9F)F-*(\"\"(F )F4F)F,F)F-*&F3F)F=F)F-" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"aG,2*&, &\"#=\"\"\"*&\"#5F)%\"tGF)F)F))%\"xG\"\"#F)F)*&,.F/F)*&F/F)%\"zGF)F)*& \"\")F)F,F)F)*&F+F))F3F/F)F)*(\"#%\"bG,2*&,&!\")\"\"\"*&\"#6 F)%\"tGF)!\"\"F))%\"xG\"\"#F)F)*&,.!#F)F,F) F)*&\"#9F))F6F0F)F-*(\"\")F)F6F)F,F)F)*&\"\"&F))F,F0F)F-F)F/F)F)F0F-*& F5F)F6F)F-*&F8F)F,F)F-*&F+F)F;F)F-*(\"#