axn1,

The short answer is yes. I think R. Gerbicz already pointed this out earlier.

The long answer is: technically all we'd have to do is trial divide up to size 10^11 (not too difficult), make sure the remainder isn't a perfect power (not too difficult), and isn't prime (can be difficult, due to the size of the numbers). The nice thing about finding two factors is that we completely avoid all of those computations. Further, nobody has to just trust that we actually did the trial divisions. They can *see* the actual claimed factors.

There are other methods (which Pascal pointed out) by which we can further reduce the computations in the case we are looking at odd perfect numbers with exactly 9 factors.

Best,
Pace

I've hacked up a trial division program for a^b-1 numbers, seeing that I'd need one for these numbers. It's something I wanted to do for a long time, anyway. It does a couple of passes for residues coprime to some small primes, and sieves out composite candidate divisors divisible by other small primes. It's far from being properly optimised but appears to work (not guarantees, though!)

It assumes 64 bit long int so it probably won't work on non-AMD64/EMT64 machines. It uses GMP for the modular powering, I'm planning to write a small binary powering ladder with x86-64 asm for mulq/divq, and perhaps REDC. I'll see when I get around to it.

Try it if you like, but beware of bugs.

Alex

[QUOTE=akruppa;87240]I've hacked up a trial division program for a^b-1 numbers, seeing that I'd need one for these numbers. It's something I wanted to do for a long time, anyway. It does a couple of passes for residues coprime to some small primes, and sieves out composite candidate divisors divisible by other small primes. It's far from being properly optimised but appears to work (not guarantees, though!)

It assumes 64 bit long int so it probably won't work on non-AMD64/EMT64 machines. It uses GMP for the modular powering, I'm planning to write a small binary powering ladder with x86-64 asm for mulq/divq, and perhaps REDC. I'll see when I get around to it.

Try it if you like, but beware of bugs.

Alex[/QUOTE]Thanks. I'll take a look. I'll also try writing my own to see whether I can find any optimizations you missed (or miss any you found!)

Paul

62199604679 divides 929^31099802339-1 or is that not helpful?

[QUOTE=rogue;87246]62199604679 divides 929^31099802339-1 or is that not helpful?[/QUOTE]

It appears that 62199604679 divides 929^31099802339+1

Rogue,

We are looking for factors >10^11.

[QUOTE=akruppa;87240]I've hacked up a trial division program for a^b-1 numbers, seeing that I'd need one for these numbers. It's something I wanted to do for a long time, anyway. It does a couple of passes for residues coprime to some small primes, and sieves out composite candidate divisors divisible by other small primes.[/QUOTE]

I don't have a 64 bit processor, so I haven't looked at the code. But I'm wondering if you thought of the following:

We are often interested in cases where b is {small number} * {large prime}. The small number sometimes has several small factors, like 12 or 18. In these cases I think it makes sense to filter for 2k*{large prime} but do the powermod trial division on a^b-1.

[QUOTE=alpertron;87248]It appears that 62199604679 divides 929^31099802339+1[/QUOTE]

Twice! That's why it's on the list of Vanishing Fermat Quotients. As Zeta-Flux points out, it's less than 10[sup]11[/sup], though.

When performing a program to trial divide [tex]a^b - 1[/tex], where the prime a<1000 and b is odd, it is useful to note that the number [tex]a[/tex] is a quadratic residue modulo all prime factors p.

[tex]x^2 \,\equiv\, a \,\pmod p[/tex]

Using the Quadratic Reciprocity Law we could precompute the values [tex]0\,\le x\,<\,4a[/tex] for which the Legendre symbol (x\a) is 1 or -1 (depending on the values of [tex]x[/tex] and [tex]a \bmod 4[/tex]).

This could double the speed of the trial factor, since we can check in this table whether the number [tex]p[/tex] is a factor candidate or not by looking at the element [tex]p \bmod {4a}[/tex] of the table.

[QUOTE=Zeta-Flux;87252]Rogue,

We are looking for factors >10^11.[/QUOTE]

I missed that. I'll also play with Alex's code to see if it is faster than mine. I should be able to do about 1e12 a day on a single CPU for one a/b pair with my code, but could probably do better with Alex's once I eliminate GMP. I believe I can do even better if I modify my code to handle multiple a/b pairs.

[QUOTE=alpertron;87257]When performing a program to trial divide [tex]a^b - 1[/tex], where the prime a<1000 and b is odd, it is useful to note that the number [tex]a[/tex] is a quadratic residue modulo all prime factors p.

[tex]x^2 \,\equiv\, a \,\pmod p[/tex]

Using the Quadratic Reciprocity Law we could precompute the values [tex]0\,\le x\,<\,4a[/tex] for which the Legendre symbol (x\a) is 1 or -1 (depending on the values of [tex]x[/tex] and [tex]a \bmod 4[/tex]).

This could double the speed of the trial factor, since we can check in this table whether the number [tex]p[/tex] is a factor candidate or not by looking at the element [tex]p \bmod {4a}[/tex] of the table.[/QUOTE]

For example, in the case a=491, if we have a candidate prime factor p, we compute k = p mod 4*a.

If k or 4*491-k are not in the following list, the candidate cannot be a factor of 491^odd-1.

[code] 1 - 5 - 7 - 9 - 13 - 17 - 19 - 23 - 25 - 33 - 35 - 37 - 41 - 45 - 47 - 49 - 59 - 61 - 63 - 65 - 67 - 81 - 85 - 87 - 91 - 93 - 95 - 97 - 101 - 103 - 115 - 117 - 119 - 121 - 125 - 129 - 133 - 151 - 153 - 159 - 161 - 165 - 167 - 169 - 171 - 175 - 181 - 185 - 191 - 197 - 205 - 207 - 211 - 213 - 219 - 221 - 225 - 229 - 231 - 233 - 235 - 237 - 241 - 245 - 247 - 249 - 251 - 257 - 259 - 267 - 269 - 271 - 277 - 283 - 287 - 289 - 293 - 295 - 297 - 299 - 305 - 307 - 311 - 315 - 319 - 321 - 323 - 325 - 327 - 329 - 333 - 335 - 339 - 341 - 343 - 347 - 349 - 359 - 361 - 367 - 369 - 381 - 383 - 389 - 391 - 393 - 401 - 405 - 409 - 411 - 413 - 417 - 423 - 425 - 427 - 429 - 431 - 435 - 437 - 439 - 441 - 443 - 447 - 455 - 457 - 461 - 465 - 469 - 471 - 473 - 475 - 479 - 481 - 485 - 487 - 489 - 499 - 505 - 515 - 519 - 523 - 529 - 531 - 533 - 537 - 549 - 561 - 563 - 567 - 575 - 579 - 583 - 585 - 587 - 595 - 597 - 603 - 605 - 607 - 609 - 611 - 617 - 619 - 625 - 627 - 629 - 631 - 637 - 645 - 651 - 665 - 669 - 673 - 679 - 681 - 691 - 697 - 701 - 703 - 707 - 709 - 717 - 719 - 721 - 727 - 729 - 739 - 743 - 755 - 759 - 765 - 767 - 773 - 779 - 781 - 783 - 787 - 789 - 793 - 795 - 799 - 803 - 805 - 809 - 819 - 825 - 827 - 833 - 835 - 837 - 839 - 841 - 843 - 845 - 847 - 851 - 855 - 859 - 869 - 871 - 873 - 875 - 877 - 883 - 893 - 899 - 903 - 905 - 907 - 909 - 911 - 913 - 925 - 927 - 929 - 931 - 939 - 943 - 951 - 953 - 955 - 961 - 967 - 971 - 979[/code]